頻出文字カウントプログラム

C++での単語の出現頻度順に出力するプログラムで，ちょっと躓いた部分があったのでWebを眺めていると，どう書く？orgβ：コード中の文字の頻度分析と言うページを見つけました．面白そうだったので，私もC++でどこまで短く書けるか挑戦．“頻出単語”だとちょっとプログラムが長くなるので，お題の通り頻出文字で．

#include <algorithm>
#include <map>
#include <vector>
#include <string>
#include <iostream>
#include <iterator>
#include <cctype>

bool greater_count(const std::pair<char, int>& x, const std::pair<char, int>& y) {
    return x.second > y.second;
}

int main(int argc, char* argv[]) {
    std::istream_iterator<char> input(std::cin);
    std::istream_iterator<char> last;
    
    std::map<char, int> v;
    while (input != last) v[*input++]++;
    
    std::vector<std::pair<char, int> > tmp(v.begin(), v.end());
    std::sort(tmp.begin(), tmp.end(), greater_count);
    for (size_t i = 0; i < tmp.size(); i++) {
        if (std::isprint(tmp[i].first)) {
            std::cout << tmp[i].first << ": " << tmp[i].second << std::endl;
        }
    }
    
    return 0;
}

今の所，この辺りが限界（何となく書いたら上記のようになっただけなので，言うほど考えてはいませんが）．標準入力からガンガン文字列が流されてくる事を想定したプログラムです．空白文字，タブ文字，改行文字は読み飛ばし．

awkのプログラムの短さに感動．そう言えば，以前FizzBuzz問題のワンライナープログラムコンテストが開かれてましたけど，これもワンライナーでいける言語あるのかな．ちょっとC++では無理そうですが．

調査は，boostが手元にあったのでそれで実施．ただし，ちょっと量が多かったので，boostディレクトリ直下のhppファイルに限定しています．

$ cat `ls ../boost_1_35_0/boost/*.hpp` | ./test > result.txt

e: 41887
t: 36679
a: 25011
r: 22817
s: 22136
n: 21827
i: 21617
o: 21410
_: 18978
p: 16365
...

上位10文字は上記の通り．記号だとアンダースコアが唯一ランクイン．これは，C++のクラスや変数の命名習慣がラクダ型（単語の最初を大文字にする）ではなくヘビ型（単語どうしをアンダースコアで繋ぐ）だからでしょう．後は，型を書かなければならない言語らしく，int, iteratorみたいな型を表す単語に含まれる文字が多いですね．ちなみに，括弧は24位と25位で“): 6311”，“(: 6297”でした．括弧の対応があってないってどういうこと・・・？boostのプログラムも傾向的には，どう書く？orgβ：コード中の文字の頻度分析での結果と同じようです．

ちなみに，肝心の探していた問題ですが，今の所スマートな回答が見つからず．何かと言うと，出現頻度順に表示するためにソートする必要があるのですがstd::mapはソート不可（キーを基にした二分木でソートして管理されているので崩せない）なのでどうしたものか，と言うものでした．

std::vector<std::pair<char, int> > tmp(v.begin(), v.end());

と，一旦std::vectorにコピーした後でソートすると言う方法に逃げたのですが，このコピーが気に入らない．

追記

boost::bimaps::bimap*1を使ってみては？と言う指摘を頂きました．

#include <iostream>
#include <iterator>
#include <string>
#include <functional>
#include <cctype>
#include <boost/bimap.hpp>
#include <boost/bimap/vector_of.hpp>

class pair_printer {
public:
    template <class Pair>
    void operator()(const Pair& x) {
        if (std::isprint(x.second)) {
            std::cout << x.second << ": " << x.first << std::endl;
        }
    }
};

int main(int argc, char* argv[]) {
    std::istream_iterator<char> input(std::cin);
    std::istream_iterator<char> last;
    
    using namespace boost::bimaps;
    bimap<char, vector_of<int> > v;
    while (input != last) v.left[*input++]++;
    
    v.right.sort();
    std::for_each(v.right.rbegin(), v.right.rend(), pair_printer());
    return 0;
}

キーと値どちらでもソート可能なmap（と言う認識でいいのかな？）．これを使えば，ソートのために一旦vectorにコピーしなくても良くなるのでしょうか．

*1:bidirectional mapの略だそうです．