Data structures equivalents of STL containers

Question

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

Answer 1

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.

Answer 2

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.