挿入のための最も効率的なデータ構造と異なる条件で並べ替え

Question

テキストから異なる単語を読み込み、出現回数を減らして頻度表を作成するための最良のデータ構造が何か疑問に思っていました。

struct info { 
    string word; 
    int num; 
}; 

は私が使用する必要があると思いまして心の中でこれを持つ：

私の考えは、構造体使用した、セット、ベクトルをリスト...？ 私はベクトルで2つの実装を持っています：

1）ベクトルを並べ替えずに単語の線形検索をすると、単語がベクトルにない場合、最後に要素を追加します。私が単語を読み終えたら、頻度を減らしてベクトルをソートしました。

2）ベ​​クトルをソートし、双子葉探索を使用して、対応する位置に要素を追加するか、またはnumを1に加算します。次に、頻度を減らしてベクトルをソートしました。

あなたはどう思いますか、この種の運動をする最良の方法は何ですか？

Answer 1

std::map<std::string, unsigned int> dictionary; 

//where words is a list, vector of your words, replace this with reading from your text file word by word 
for(const auto& word : words) 
{ 
    dictionary[word]++; 
} 

//now the dictionary has your words in alphabetical order and the frequency (number of occurrences) 
std::multimap<int, std::string> histogram; 
for(const auto& elem : dictionary) 
{ 
    histogram.insert(std::make_pair(elem.second(), elem.first())); 
} 

//print the histogram 
for(const auto& elem : histogram) 
{ 
    cout << elem.first() << " : " << elem.second() << endl; 
} 

Answer 2

コメントで述べたように（申し訳ありませんが、あまりにも困難なクレジットを与えるために入力するように）あなたがstd::mapを使用することができます。地図要素がソートされ、「手作業で」行う余分な労力を節約できます。異なる2つのソート方法が必要な場合は、2つのマップまたは別のコンテナを使用して、2回ソートすることができます。例えば。ベクトルを使って：

#include <string> 
#include <vector> 
#include <algorithm> 

struct info { 
    std::string word; 
    int num; 
}; 

bool sortViaNum(const info& a,const info& b) { return a.num > b.num; } 
bool sortViaWord(const info& a,const info& b) { return a.word > b.word; } 

int main() { 

    std::vector<info> vect; 
    // fill the vector 
    std::sort(vect.begin(),vect.end(),sortViaNum); 
    std::sort(vect.begin(),vect.end(),sortViaWord); 
    return 0; 
}