5

簡単な使用例を示すことから始めます。

  • 社会保障 ID データベースの問題を考えてみましょう。C++ コードでは としてモデル化されておりstd::unordered_map、そのキーは個人の社会保障 ID であり、その値はその個人std::stringのフルネーム (例: std::unordered_map<int, std::string> DB;) です。

  • std::unordered_mapまた、個人の ID (つまりのキー)に基づいて昇順に並べ替えられたこのデータベースを印刷する要求があることも考慮してください。

  • 単純に、以下のコード例のように、要求された基準に従ってstd::sortをソートしてから印刷するために使用することを考えるでしょう:std::unordered_map

   std::sort(DB.begin(), DB.end());
   for(auto p : DB) std::cout << "ID(" << p.first
                              << ") - " 
                              << p.second 
                              << std::endl;
  • ただし、 aまたは astd::sortのいずれかの範囲で を使用するとコンパイラ エラーが発生するため、これは当てはまりません。std::unordered_mapstd::unordered_set

質問:

  1. STL の順序付けられていないコンテナーを並べ替えできないのはなぜstd::sortですか?
  2. std::unordered_mapaまたは aをソートする正当で効率的な方法はありますかstd::unordered_set?
4

3 に答える 3

5

並べ替えは、要素がコンテナーに追加された順序によって決定されるコンテナーであるシーケンスコンテナーに対してのみ意味があります。標準ライブラリの動的シーケンス コンテナーは、vector、deque、list、および forward_list です。

一方、マップとセットは連想コンテナーであり、要素はその値によって識別されます。したがって、コンテナー要素はどのような順序でも配置されていないため、「順序付け」を要求しても意味がありません。(順序付けされたマップをキーの比較順序で反復できることは事実ですが、その順序はコンテナーから出てきます。ユーザーによって提供されるわけではありません。)

于 2014-06-13T19:38:17.653 に答える
2

1.なぜ STL の順序付けされていないコンテナを並べ替えることができないのstd::sortですか?

順序付けられていないコンテナーは、キーによって直接ではなく、(通常) ( としてもアクセス可能) によって、既に"ソート" されているためです。この「ソート」順序は表面的なものではありません。これは、ハッシュ テーブルが要素をすばやく見つけるための全体的な基礎です。代わりに要素をキーで並べ替えることが許可されている場合、コンテナーはハッシュ テーブルとして機能できなくなります。要素を確実に見つけたり消去したりできず、挿入によってコンテナーに重複が入る可能性があります。hash_function(key) % bucket_count()bucket(key)std::sort

std::unordered_map2. aまたは a のいずれかをソートする正当で効率的な方法はありますかstd::unordered_set?

std::vector一般的なケースでは、最初に要素をorなどのソート可能またはソート済みコンテナーにコピーするだけですstd::set(前者は通常より高速ですが、本当に気にする場合は両方をベンチマークします)。

std::unordered_set<T> my_set = ...;
std::vector<T> my_vec{my_set.begin(), my_set.end(), my_set.size()};
std::sort(my_vec.begin(), my_vec.end());

の場合、ソートのためにキーstd::unordered_map<int, std::string> DB;のみを a にコピーし、反復中に : 内の各キーを検索することをお勧めします。これにより、多くのコピーが回避されます。intvectorunordered_mapstring

（キーによる順序付けで順序付けされていないコンテナを調整できる場合があります（たとえば、ハッシュ関数がキーを返し、コンテナが事前にサイズ設定されているため、最大バケット インデックス >= 最大キー値）、そのような悪用を検討している人は、 を使用した方がよいでしょうvector。）

于 2015-06-22T03:56:13.637 に答える