出現回数が最も多いK個の数をとる

タイトル
検索エンジンは、ユーザが検索するたびに使用するすべての検索列をログファイルで記録し、各検索列の長さは1〜255バイトである.現在1千万件のレコードがあると仮定します(これらのクエリ列の重複度は比較的高く、総数は1千万ですが、重複を除いた場合、3百万個を超えません.1つのクエリ列の重複度が高いほど、クエリを行うユーザーが多ければ多いほど、つまり人気があります.)最も人気のある10のクエリ列を集計してください.使用するメモリは1 Gを超えてはいけません.
構想
ステップ1:Hashmap(STLではunordered_map)で頻度を統計する
第2歩:出現回数が最も大きいK単語を容量Kの最小スタックで取り出す(参考http://blog.csdn.net/fuyufjh/article/details/48369801)
コード#コード#

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef pair<string, int> Record;

struct RecordComparer {
    bool operator() (const Record &r1, const Record &r2) {
        return r1.second > r2.second;
    }
};

vector TopKNumbers(vector<string> &input, int k) {
    unordered_map<string, int> stat;
    for (const string &s : input) stat[s]++;
    priority_queuevector, RecordComparer> heap;
    auto iter = stat.begin();
    for (int i = 0; i < k && iter != stat.end(); i++, iter++) {
        heap.push(*iter);
    }
    for (; iter != stat.end(); iter++) {
        if (iter->second > heap.top().second) {
            heap.pop();
            heap.push(*iter);
        }
    }
    vector result;
    while (!heap.empty()) {
        result.push_back(heap.top());
        heap.pop();
    }
    return result;
}

/********        *********/
int main() {
    clock_t cbegin, cend;
    vector<string> test;
    char buf[20];
    for (int i = 0; i < 100; i++) {
        int x = rand() % 20;
        sprintf(buf, "STR%d", x);
        test.push_back(string(buf));
    }
    auto result = TopKNumbers(test, 5);
    for (auto it = result.rbegin(); it != result.rend(); it++) {
        cout << it->first << '\t' << it->second << endl;
    }
    printf("============================
");
    sort(test.begin(), test.end());
    for (const string &s : test) {
        cout << s << endl;
    }
}

Ref

http://blog.csdn.net/v_JULY_v/article/details/6403777