Search code examples
c++data-structuresstlequivalent

Data structures equivalents of STL containers

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

for example

  • 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 = ?
Solution

  • Concering the C++ standard library containers, the standard itself tries not to say too much about implementation. However, the very specific constraints on complexity of insertion, removal, look-up, range insertion and so on, mean that most implementations use the same types of data structures for the containers. Concerning some of your examples:

    • std::list : doubly linked list
    • std::set, std::multiset, std::map, std::multimap: self-balancing binary trees, typically red-blacktrees.
    • 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.