Histogram in C++

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

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

コード

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;
}

実行例

#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;
}