UpdatedAug 4, 2026

Containers and Algorithms

Question Variations

"When should you choose `vector`, `list`, or `deque`?"
"How do `map` and `unordered_map` differ?"
"Why use `std::find_if` or `std::ranges` algorithms?"
"What operations invalidate vector iterators?"

Why This Is Asked

The standard library is a major part of idiomatic C++. Interviewers use this question to assess whether you choose data structures by access pattern and use expressive algorithms instead of error-prone hand-written loops where a standard operation already exists.

Key Concepts

std::vector is a contiguous dynamic array and is often the default sequence container.
std::unordered_map offers average constant-time lookup; std::map maintains ordered keys.
Algorithms accept iterator ranges and work across compatible containers.
Iterator invalidation depends on the container and operation.

Question Variations

“When should you choose vector, list, or deque?”
“How do map and unordered_map differ?”
“Why use std::find_if or std::ranges algorithms?”
“What operations invalidate vector iterators?”

Answers by Technology

+ Add Variant

C++Improve this answer ✏️

Expected Answer (C++23)

Choose a standard container from the required access and mutation pattern. std::vector is often the best default because it stores elements contiguously, supports fast indexed access, and has good cache locality. Use std::unordered_map for average constant-time key lookup when ordering is unnecessary, and std::map when ordered traversal or logarithmic worst-case lookup is needed.

Prefer standard algorithms and ranges to make intent explicit. They operate on iterator ranges, keeping an algorithm independent of the specific container.

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> values{3, 1, 4, 1, 5};

    std::ranges::sort(values);
    const auto found = std::ranges::find(values, 4);

    return found != values.end() ? 0 : 1;
}

Understand invalidation rules before holding iterators, references, or pointers into a container across mutations. In particular, a vector reallocation invalidates all of them.

Why It Matters

Appropriate container and algorithm choices affect performance, memory use, and correctness. Ignoring invalidation rules creates bugs that can surface long after a seemingly harmless container operation.

Common Mistakes

Choosing std::list by default for insertion efficiency: Its poor locality and allocation overhead often outweigh that theoretical advantage.
Assuming unordered_map preserves insertion order: It does not; iteration order is unspecified.
Keeping vector iterators across a possible reallocation: Growth may invalidate every iterator, pointer, and reference into the vector.

Follow-up Questions

What is vector::reserve useful for? (Answer: It preallocates capacity to reduce reallocations when an approximate final size is known.)
Why does std::map require an ordering? (Answer: It maintains keys in a tree ordered by its comparison function.)