Histogram in C++

C++: ヒストグラムの作成

first と last という 2つのイテレータからその範囲内の連続する値をカウントし
その個数と値の pair を vector にして返すテンプレート関数 encodeList を作成。
ソート済みのリストに対してこれを適用すれば、ヒストグラムを作成することができる。

コード

1 2 3 4 5 6 7 8 9 10 11 12 13

using namespace std;   template <typename Iterator> vector<pair<int , typename Iterator::value_type> > encodeList(Iterator first, Iterator last) {   vector<pair<int , typename Iterator::value_type> > ret;   for (Iterator i = first; i != last;) {     Iterator j = i;     while (j != last && *i == *j) ++j;     ret.push_back(make_pair(j - i, *i));     i = j;   }   return ret; }

実行例

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

#include <iostream> #include <sstream> #include <vector> #include <algorithm>   using namespace std;   template <typename Iterator> vector<pair<int , typename Iterator::value_type> > encodeList(Iterator first, Iterator last) {   vector<pair<int , typename Iterator::value_type> > ret;   for (Iterator i = first; i != last;) {     Iterator j = i;     while (j != last && *i == *j) ++j;     ret.push_back(make_pair(j - i, *i));     i = j;   }   return ret; }   template <typename T> std::ostream & operator<<(std::ostream & stream, std::vector<T> & v) {   stream << "[";   for(typeof(v.begin()) i = v.begin(); i != v.end(); ++i) {     if (i != v.begin()) { stream << ", "; }     stream << *i;   }   stream << "]";   return stream; } template <typename T, typename U> std::ostream & operator<<(std::ostream & stream, std::pair<T, U> & p) {   stream << "(" << p.first << ", " << p.second << ")";   return stream; } #define all(a) (a).begin(),(a).end() template <typename T> void printResult(T v) {   cout << v << endl;   vector<pair<int , typename T::iterator::value_type> > result = encodeList(all(v));   cout << result << endl; }   int main() {   vector<int> v1, v2;   for (int i = 1; i < 4; ++i) for (int j = 0; j < i * 2; ++j) v1.push_back(i);   printResult(v1);   // [1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3]   // [(2, 1), (4, 2), (6, 3)]     printResult(v2);   // []   // []     string s = "aabbbaac";   printResult(s);   // aabbbaac   // [(2, a), (3, b), (2, a), (1, c)]     sort(all(s));   printResult(s);   // aaaabbbc   // [(4, a), (3, b), (1, c)]     return 0; }