Geek Answers Handbook

Equivalents of data structures in STL containers

I am studying data structures and I want to ask what are the equivalents of STL containers.

eg

  • vector = dynamic array
  • queue = queue
  • stack = stack
  • priority_queue = heap
  • list = linked list
  • set = tree
  • slist = single linked list
  • bit_vector = vector bool
  • map = pair
  • deque =?
  • multiset =?
  • multimap =?
  • hash_set =?
  • hash_map =?
  • hash_multiset =?
  • hash_multimap =?
  • hash =?
  • bit_set =?
+7
source share
4 answers

Comparing the standard C ++ library libraries, the standard itself tries not to say too much about the implementation. However, there are very specific limitations on the complexity of inserting, deleting, searching, inserting a range, etc. Mean that most implementations use the same types of data structures for containers. As for some of your examples:

  • std :: list: doubly linked list
  • std :: set, std :: multiset, std :: map, std :: multimap: self-balancing binary trees, usually red-black trees.
  • hash_ *: C ++ 11 provides unordered_set, unordered_map and multi siblings. These are hash tables.
  • bitset: fixed size array

I believe the STL follows these implementations.

+6
source

I do not think that qualifying std :: map <> as soon as a “pair” would be correct. Actually there is a utility called std :: pair <> which is actually just a couple. std :: map <> stores unique keys and non-unique values ​​in a way that allows you to use syntax similar to array syntax with indexes that can be numerical or not.

Edit: Fixed a "container" for a "utility" thanks to juanchopanza .

+2
source

and multiple-binary search tree

map and multimap - binary search tree

deque deque

Hash hash* containers are hashed associative containers implemented as hash tables. eg. hash_map contains a pair<key,value> , which is viewed using a hash table.

in bitrate

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

+1
source 
 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
0
source

More articles:


All Articles