CODEWITHSUNDEEP
c++data-structuresstlequivalent
demosthenes
demosthenes

Reputation: 1191

Data structures equivalents of STL containers

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

for example

Upvotes: 7

Views: 3945

Answers (5)

LoS
LoS

Reputation: 1833

The C++ Standard does not impose a specific data structure to containers, but defines a set of requirements. This means that an implementation must only satisfy the above requirements, which are mostly concerned with the time complexity of different operations, reference stability and iterator invalidation, to be considered standard-compilant.

However, the combination of certain requirements and the performance expectations force the majority of libraries (libc++, libstdc++, MSVC) to use a specific data structure for each container.

  • std::array: fixed-size array
  • std::vector: dynamic-size array
  • std::deque: hashed array tree
  • std::forward_list: singly-linked list
  • std::list: doubly-linked list
  • std::set/std::map: self-balancing BST (red-black tree)
  • std::unordered_set/std::unordered_map: hash table (separate-chaining hash table)

Upvotes: 0

Jai
Jai

Reputation: 1332

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

Upvotes: 0

ApplePie
ApplePie

Reputation: 8942

I don't think qualifying std::map<> as just a "pair" would be correct. Actually, there is a utility named std::pair<> which is really only just a pair. std::map<> stores unique keys and non-unique values in a way that makes it possible to use a syntax similar to that of an array with indices being of types that can be numerical or not.

Edit: Corrected "container" to "utility" thanks to juanchopanza.

Upvotes: 3

juanchopanza
juanchopanza

Reputation: 227608

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.

Upvotes: 6

nims
nims

Reputation: 3881

set and multiset- binary search tree

map and multimap - binary search tree

deque - deque

the hash* containers are hashed associative containers implemented as hash tables. eg. hash_map contains pair<key,value> which is looked up using hash table.

in bitset

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

Upvotes: 1

Related Questions