The “C++ standard library” isn’t defining implementation details of the data structures, it just defines their behavior. The libstdc++ is a specific implementation of The “C++ standard library” by GCC.
Sequence containers
| Container | Implementation | Usage |
|---|---|---|
| Array | Continuous chunk of memory with fixed size and its payload is on the stack. | – Access via index – Fixed Size |
| Vector | Continuous chunk of memory without fixed size and its payload is on the heap. It pre-allocates some memory and adapts the size as soon as necessary. If it can’t grow anymore it has to change its location. | – Access via index – Ins/Del at the tail |
| Deque | Possibly multiple chunks of memory with fixed size, addressed by a continous chunk of memory without fixed size called a map. The map behaves like a vector, but also keeps some unused memory at the beginning. | – Access via index – Ins/Del at the head and the tail |
| Forward_list | Each item contains of its data and a pointer to the next item. Every item can be stored at a random free location in the memory. | – Ins/Del at the head and the middle |
| List | Each item contains of its data and a pointer to the previous and the next item. Every item can be stored at a random free location in the memory. | – Ins/Del at the head, the middle and the tail |
Associative containers
| Container | Implementation | Usage |
|---|---|---|
| Set | The chosen type of a binary search tree is the red-black tree, which works self-balancing. Each node within the tree has a color (black or red), a pointer to the parent, a pointer to the left (if existing), a pointer to the right (if existing) and a value. | – Ordered Unique keys – Less memory |
| Map | Works like the set, but each node contains a key-value pair instead of just a key. It gets sorted based on the keys. | – Ordered Key-value pairs with unique keys – Less memory |
| Unordered_set | The hash map is a vector of so called buckets. Each used bucket points on a node in a forward list. New keys getting hashed to resolve the right bucket and then getting added behind the node the buckets is pointing to. Adding behind is necessary to be able to rehang the pointers, which implies each bucket points on the node before the first containing one. | – Unique keys – Access via key |
| Unordered_map | Works like the unordered_set, but each node in the forward list contains additionally to the pointer to the next node a key-value pair instead of just a key. | – Key-value pairs with unique keys – Access via key |
Container adaptors
| Adapter | Default container | Details |
|---|---|---|
| Stack | Deque | – Last In First Out |
| Queue | Deque | – First In First Out |
| Priority_queue | Vector | – Binary heap |