3

Python では、set は文字列の 2 つのリストを比較するのに非常に便利です (このリンクを参照してください)。パフォーマンスの点で C++ に適した解決策があるかどうか疑問に思っていました。各リストには 100 万を超える文字列が含まれているためです。

大文字と小文字を区別するマッチングです。

4

3 に答える 3

9

データ型std::set<>(通常はバランス ツリーとして実装) とstd::unordered_set<>(C++11 からはハッシュとして実装) を使用できます。std::set_intersection実際の交点を計算すると呼ばれる便利なアルゴリズムもあります。

ここに例があります。

#include <iostream>
#include <vector>
#include <string>
#include <set>             // for std::set
#include <algorithm>       // for std::set_intersection

int main()
{
  std::set<std::string> s1 { "red", "green", "blue" };
  std::set<std::string> s2 { "black", "blue", "white", "green" };

  /* Collecting the results in a vector. The vector may grow quite
     large -- it may be more efficient to print the elements directly. */     
  std::vector<std::string> s_both {};

  std::set_intersection(s1.begin(),s1.end(),
                        s2.begin(),s2.end(),
                        std::back_inserter(s_both));

  /* Printing the elements collected by the vector, just to show that
     the result is correct. */
  for (const std::string &s : s_both)
    std::cout << s << ' ';
  std::cout << std::endl;

  return 0;
}

ノート。を使用したい場合、 は入力セットが順序付けられていることを想定しているため、このように使用std::unordered_set<>することはstd::set_intersectionできません。小さい方のセットを反復処理し、大きい方のセットの要素を見つけて交差点を決定する for ループの通常の手法を使用する必要があります。それでも、多数の要素 (特に文字列) の場合は、ハッシュ ベースのstd::unordered_set<>方が高速な場合があります。Boost のもの ( boost::unordered_set) や Google によって作成されたもの (sparse_hash_setおよびdense_hash_set) などの STL 互換の実装もあります。その他のさまざまな実装とベンチマーク (文字列用のものを含む) については、こちらを参照してください。

于 2012-09-12T07:09:24.950 に答える
0

あまりパフォーマンスが必要ない場合は、STL の map/set を使用することをお勧めします。

list<string> list, list2;
...
set<string> sndList;
list<string> result;

for(list<string>::iterator it = list2.begin(); it != list2.end(); ++it)
   sndList.insert(*it);

for(list<string>::iteratir it = list.begin(); it != list.end(); ++it)
    if(sndList.count(*it) > 0)
        result.push_back(*it);

それ以外の場合は、比較のためにいくつかのハッシュ関数を提案します。

于 2012-09-12T07:07:11.313 に答える
0

それが本当にstd::listあなたが持っている場合は、それらを並べ替えて使用しますset_intersection：

list<string> words1;
list<string> words2;
list<string> common_words;

words1.sort();
words2.sort();

set_intersection(words1.begin(), words1.end(),
                 words2.begin(), words2.end(),
                 back_inserter(common_words));
于 2012-09-12T13:42:28.190 に答える