7

私はデータ構造を研究していて、STLコンテナに相当するものは何かを尋ねたいと思います。

例えば

  • ベクトル=動的配列
  • キュー=キュー
  • スタック=スタック
  • priority_queue=ヒープ
  • リスト=リンクリスト
  • セット=ツリー
  • slist=単一のリンクリスト
  • bit_vector = vector bool
  • マップ=ペア
  • deque =？
  • マルチセット=？
  • マルチマップ=？
  • hash_set =？
  • hash_map =？
  • hash_multiset =？
  • hash_multimap =？
  • ハッシュ=？
  • bit_set =？
4

4 に答える 4

7

C++ 標準ライブラリ コンテナーに関しては、標準自体が実装についてあまり言及しないようにしています。ただし、挿入、削除、ルックアップ、範囲挿入などの複雑さに関する非常に具体的な制約は、ほとんどの実装がコンテナーに対して同じタイプのデータ構造を使用することを意味します。あなたの例のいくつかに関して：

  • std::list :二重連結リスト
  • std::set、std::multiset、std::map、std::multimap: 自己均衡二分木、通常は赤黒木。
  • hash_*: C++11 は、unordered_set、unordered_map、および複数の兄弟を提供します。これらはハッシュ テーブルです。
  • ビットセット: 固定サイズの配列

STL はこれらの実装に従っていると思います。

于 2012-06-16T17:18:11.563 に答える
2

std::map<> を単なる「ペア」として修飾することは正しいとは思いません。実際には、std::pair<> という名前のユーティリティがありますが、これは単なるペアです。std::map<> は、一意のキーと一意でない値を格納します。これにより、数値型または非数値型のインデックスを持つ配列と同様の構文を使用できるようになります。

編集: juanchopanzaのおかげで、「コンテナ」を「ユーティリティ」に修正しました。

于 2012-06-16T15:27:48.113 に答える
1

セットおよびマルチセット-二分探索木

マップとマルチマップ-二分探索木

deque-deque

コンテナは、hash*ハッシュテーブルとして実装されたハッシュ化された連想コンテナです。例えば。ハッシュテーブルを使用して検索されるものがhash_map含まれます。pair<key,value>

ビットセットで

the individual elements are accessed as special references which mimic bool elements

于 2012-06-16T15:24:07.490 に答える
0 
vector = dynamic array  

queue = queue

stack = stack

priority_queue = priority queue based on binary heap 
                 priority_queue can be implemented using 
                 1. sorted array
                 2. sorted list ( unrolled list, skip list etc)
                 3. any other heap like Fibonacci heap, binomial heap

list = doubly linked list 

set = set based on AVL Tree ( usually ) 
      can implemented using any other binary balancing tree like 
      1. Binary Search Tree
      2. Red black Tree
      3. Splay Tree

slist = single linked list

map = map based on Red Black Tree ( usually ) 
      where every node is 'pair' structure
      can implemented using any other binary balancing tree like 
      1. Binary Search Tree
      2. AVL Tree
      3. Splay Tree

deque = deque

hash_set = set implemented using hash

hash_map = hash table

hash = 'Not Available', used as functor
于 2015-08-18T09:21:22.053 に答える