SimplifyC++ Article
A Deeper Dive into C++ STL Containers
A Deeper Dive into C++ STL Containers
Sequence Containers
vector
Internal implementation: Dynamically resizable array.
Key operations:
push_back: Efficiently adds an element to the end.pop_back: Efficiently removes the last element.front,back: Accesses the first and last elements.size: Returns the current size.capacity: Returns the maximum size without reallocation.resize: Resizes the vector to a specified size.
deque
Internal implementation: Double-ended queue.
Key operations:
push_front,push_back: Efficiently adds elements to the beginning or end.pop_front,pop_back: Efficiently removes elements from the beginning or end.front,back: Accesses the first and last elements.size,capacity: Similar tovector.
list
Internal implementation: Doubly linked list.
Key operations:
insert: Efficiently inserts elements anywhere.erase: Efficiently removes elements anywhere.begin,end: Iterators to access the beginning and end.front,back: Accesses the first and last elements.size: Returns the current size.
array
Internal implementation: Fixed-size array.
Key operations:
at: Accesses elements by index.size: Returns the fixed size.data: Returns a pointer to the underlying array.
Associative Containers
map
Internal implementation: Red-black tree.
Key operations:
insert: Inserts a key-value pair.find: Searches for an element by key.erase: Removes an element by key.count: Checks if a key exists.begin,end: Iterators to access the beginning and end.
unordered_map
Internal implementation: Hash table.
Key operations:
Similar to
map,
but unordered.
bucket_count: Returns the number of buckets.bucket_size: Returns the size of a specific bucket.
set
Internal implementation: Red-black tree (similar to
map).Key operations: Similar to
map, but stores only unique elements.
unordered_set
Internal implementation: Hash table (similar to
unordered_map).Key operations: Similar to
unordered_map, but stores only unique elements.
Other Containers
stack
Internal implementation: Typically implemented using
vectorordeque.Key operations:
push: Adds an element to the top.pop: Removes the top element.top: Accesses the top element.empty: Checks if the stack is empty.
queue
Internal implementation: Typically implemented using
deque.Key operations:
push: Adds an element to the back.pop: Removes the front element.front: Accesses the front element.back: Accesses the back element.empty: Checks if the queue is empty.
priority_queue
Internal implementation: Typically implemented using a heap.
Key operations:
push: Adds an element to the queue.pop: Removes the element with the highest priority.top: Accesses the element with the highest priority.size: Returns the current size.
Remember to choose the appropriate container based on your specific use case and performance requirements. For example, if you need efficient random access and frequent insertions/deletions at the end, vector is a good choice. If you need efficient insertions/deletions anywhere in the container, list is a better option.