Choosing STL containers by operations and complexity

Prerequisites and outcomes

Know arrays, vector, iterators, and Big-O notation. You will compare common containers, understand average versus worst-case hash lookup, and select a container from a workload.

Start with the operations

Ask what the program does most: index by position, insert at both ends, keep keys sorted, find by key, or process items in priority order. Container choice follows these requirements.

Container	Useful strengths	Typical costs
vector	Contiguous storage, fast indexing, cache-friendly traversal	Index O(1); append amortized O(1); middle insert/erase O(n)
deque	Efficient insertion/removal at both ends	End operations O(1); indexed access O(1); middle changes O(n)
list	Stable iterators/references except erased elements; splice	Search O(n); insertion/erase at known iterator O(1)
map/set	Sorted keys and ordered traversal	Search/insert/erase O(log n)
unordered_map/unordered_set	Hash-based key lookup	Average O(1), worst-case O(n) lookup/insert/erase
priority_queue	Repeatedly access highest-priority item	top O(1); push/pop O(log n)

Sequence containers

Use vector as the default general-purpose sequence when you need a resizable array. Its contiguous elements make traversal efficient and allow direct indexing. Choose deque when frequent insertion/removal at both ends is central. A list is not automatically faster for insertion: you must already have the iterator to the insertion position, and finding that position still takes O(n).

Ordered associative containers

#include <map>
std::map<int, std::string> names;
names.emplace(42, "Asha");
auto it = names.find(42);

std::map keeps keys ordered and supports lower/upper-bound style queries. Its logarithmic operations are useful when sorted iteration or range queries matter.

Hash containers

#include <unordered_map>
std::unordered_map<std::string, int> frequency;
++frequency["apple"];

Hash containers use a hash function to choose buckets. Lookup is average constant time under suitable distribution and load, but worst-case linear. Rehashing may invalidate iterators; do not assume iteration order is stable or sorted.

Worked choice

Suppose a program stores 50,000 student IDs and repeatedly asks whether a particular ID exists. If sorted output is unnecessary, an unordered_set is a reasonable candidate. If the program must display IDs in sorted order or answer range queries, set may be better. If records are mostly traversed sequentially and indexed by position, a vector may be the simplest structure.

Complexity is not the only factor

• Memory overhead and cache locality matter.
• Iterator and reference invalidation rules affect correctness.
• Ordering requirements may rule out hash containers.
• Small data sets may not benefit from a more complicated structure.
• Benchmark representative workloads before making performance claims.

Prerequisites: vectors, associative containers, iterators, and Big-O notation. Review std::vector, Maps and sets, and Iterator categories first.

Common mistakes

• Claiming unordered lookup is always O(1); the worst case is O(n).
• Choosing list because insertion is O(1) while ignoring the search needed to find the position.
• Depending on unordered-container iteration order.
• Keeping iterators across a rehash or vector reallocation.

Practice

1. Which container naturally maintains sorted keys?
2. Which is the usual default for a resizable sequence?
3. What is the worst-case lookup complexity of unordered_map?

Show reasoned answers

1. map or set.
2. vector, unless the workload requires something else.
3. O(n), because many keys can land in one bucket.

Summary and next step

Choose containers from required operations, ordering, invalidation, memory use, and measured workload. Big-O is a model, not a stopwatch guarantee. Next, build robust interactive programs that validate user input before changing state.

References

• cppreference: C++ language reference
• C++ Core Guidelines