c++ - C ++のマップデータ構造は何ですか

Question

C++ の次のコード行に使用されるデータ構造は何ですか?

map <char, int> dict;

ハッシュテーブルですか？

Answer 1

std::unordered_mapハッシュを使用してオブジェクトを格納します。

Answer 2

この規格は、 に特定の実装を課していませんstd::map。必要な操作とその複雑さのみを示します。これらの要因は、通常、赤黒の Treeである実際の実装の選択につながります。

の要件をリストした章std::mapは 23.2.4 Associative ContainersC++11 にあります。

Answer 3

通常、自己平衡型 BST を使用して実装されます。実装は実際にはコンパイラ固有です。

std::map<char, int> dict;

Acharはキーで、 anintは対応する値です。

Answer 4

Red-Black Tree を使用して、キーを順番に整理します。

そのため、昇順で繰り返すことができ、キー オブジェクトには operator< をオーバーロードする必要があります。