2

文字列の const リストからテキスト ファイルを書き込みますが、重複を避ける必要があります (リストには重複が含まれます)。これらのデータ構造のうち、既に書き込まれた文字列を追跡するために使用するのに (パフォーマンスの点で) 優れているのはどれですか?

map<string,bool>
set<string>

これをどうするかというと、

foreach(string in list)
    if(not found in map/set)
       write to file
       insert to map/set
    endif
end

または、これを行う別の方法はありますか？

4

4 に答える 4

3

マップには重複キーを持つエントリが含まれていないため、 を使用しても意味がありませんmap<string,bool>。これは、パフォーマンスに関係なくです。std::set<std::string>またはstd::unordered_set<std::string>仕事をするでしょう。次に例を示します。

std::vector<std::string> word_list = ....;
std::set<std::string> word_set;

for (const auto& s : work_list) // loop over words in word_list
{
  if(word_set.insert(s).second) // attempt to insert: fails if s already in set
  {
    // insertion succeeded: write to file
  }
}
于 2013-06-26T07:48:01.600 に答える
1

c++11 を使用するオプションがある場合は、unordered_setよりも漸近的に優れたパフォーマンスを発揮するはずなので、使用することをお勧めしますset。これがオプションでない場合は、 を使用しますset。map<string, bool>このタスクに を使用する理由はありません。

于 2013-06-26T07:59:48.357 に答える
1

少なくともサイズ 1 の追加の bool 値を格納する必要があるため、パフォーマンスが向上する可能性があります。アロケータと std::string の実装方法によっては、メモリ消費量が大きくなり (アラインメントを考えてください)、キャッシュ ミスが発生する可能性がありset<string>ます。の検索と挿入map<string,bool>については、こちらを参照してください。

于 2013-06-26T07:56:47.780 に答える
0

別のコンテナは実際には必要ありません。アルゴリズムを使用してください。

std::vector<std::string> list = ...
std::sort(list.begin(), list.end());
std::unique(list.begin(), list.end());

// alternatively, copy to your file without changing source vector
std::unique_copy(list.begin(), list.end(), std::ostream_iterator(out_stream));

何をしても、操作の複雑さはn.logになります (マップ/セット * n アイテムへの挿入)。map/set ソリューションは、 2.nメモリの2.n.log操作を取得します。アルゴリズムを使用すると、n+n.log操作と1.nメモリでジョブを完了できます。

于 2013-06-26T10:52:35.547 に答える