cppintermediate
C++ STL
Containers, algorithms and iterators
7 questions
By EZ4Code Team
1. What are the characteristics of std::vector?
Dynamic array, contiguous storage, supports random access, amortized O(1) insertion/removal at the back
Linked list
Fixed size
No random access
Explanation: vector is a dynamic array with contiguous memory, supports O(1) subscript random access, amortized O(1) push_back at the back, and O(n) insertion in the middle.
2. What is the difference between std::map and std::unordered_map?
map is based on a red-black tree, ordered, O(log n); unordered_map is hash-based, unordered, average O(1)
They are exactly the same
map is hash-based
unordered_map is ordered
Explanation: map is an ordered associative container (red-black tree) with O(log n) lookup; unordered_map is hash-based with average O(1) but unordered.
3. What is the default sort order of std::sort?
Ascending
Descending
Random
Insertion order
Explanation: std::sort defaults to ascending order (using operator<); for descending order pass std::greater<T>() or a custom comparison function.
4. What is a common scenario for iterator invalidation?
After a vector grows capacity, all iterators, references, and pointers are invalidated
Iterators never invalidate
Only end() is not invalidated
list iterators are invalidated after insertion
Explanation: Vector growth reallocates memory, invalidating all iterators/pointers/references; list/map iterators usually remain valid after insertion/erasure (except erasing the element itself).
5. What is the complexity of std::find?
O(n) linear search
O(log n)
O(1)
O(n log n)
Explanation: std::find performs a linear search over an unsorted range in O(n); for sorted ranges use std::binary_search O(log n); associative containers have their own member find.
6. What are the characteristics of std::list?
Doubly linked list, O(1) insertion/removal anywhere (given an iterator), no random access
Dynamic array
Supports random access
Contiguous storage
Explanation: std::list is a doubly linked list with O(1) insertion/removal (given an iterator to the position), but does not support random access (no operator[]).
7. How do STL algorithms typically access containers?
Iterators
Subscripts
The container itself
Pointers
Explanation: STL algorithms are generic functions that operate on containers via iterator ranges [first, last), decoupling algorithms from containers.