Container selection guide: vector, deque, list, array

The default answer

Use std::vector. It’s the right container for the vast majority of use cases. Pick something else only when you have a specific reason.

This is not a cop-out — it’s the result of how CPU caches work. A vector stores elements contiguously in memory. Iterating a vector of N elements touches N cache lines in order. Every other standard container scatters elements in memory, increasing cache misses.

1std::vector<float> vec(1000);     // 1000 floats, one allocation, sequential access
2std::list<float>   lst(1000);     // 1000 nodes, 1000 allocations, random access pattern

On a modern CPU, iterating lst can be 10–50× slower than iterating vec for the same number of elements, purely due to cache effects.

std::array — fixed-size, stack-allocated

std::array<T, N> is a zero-overhead wrapper around a C array. Size is fixed at compile time; no heap allocation.

1#include <array>
2
3std::array<uint8_t, 64> buf{};   // 64 bytes on the stack
4buf[0] = 0xAA;
5buf.fill(0);
6
7// Range-for, iterators, size() — all work like vector
8for (auto b : buf) process(b);

Use when:

• Size is known at compile time and won’t change
• You want no heap allocation (embedded, ISR contexts)
• You want the std::vector API without the overhead

Don’t use when:

• Size varies at runtime

std::array is the embedded default for buffers. Prefer it over raw T arr[N] because it carries size information, supports copy/move/compare, and works with spans.

1void process(std::span<const uint8_t> data);
2
3std::array<uint8_t, 8> frame = {0x01, 0x02, 0x03};
4process(frame);  // implicit conversion to span — no copy

std::vector — dynamic, contiguous

std::vector<T> is the workhorse. Contiguous memory, O(1) amortised push_back, O(1) random access.

1std::vector<SensorSample> samples;
2samples.reserve(1000);              // pre-allocate — avoids reallocations
3
4samples.push_back({tick, voltage});
5samples.emplace_back(tick, voltage);  // construct in place — avoids a copy
6
7float third = samples[2].voltage;   // O(1)

Key operations and costs:

reserve is not optional for performance-sensitive code. Without it, vector doubles its capacity on each overflow — correct, but causes repeated heap allocations and copies.

1// Build a vector from known-size data — always reserve
2std::vector<Frame> frames;
3frames.reserve(messageCount);
4for (auto& msg : messages)
5    frames.push_back(parseFrame(msg));

Erase-remove idiom — removing elements by value without a second allocation:

1// Remove all expired samples
2auto now = HAL_GetTick();
3auto it = std::remove_if(samples.begin(), samples.end(),
4    [now](const SensorSample& s) { return now - s.tick > 5000; });
5samples.erase(it, samples.end());

std::deque — double-ended queue

std::deque<T> supports O(1) push/pop at both ends and O(1) random access. Internally it’s a segmented array — not fully contiguous, but more cache-friendly than a list.

1std::deque<Command> queue;
2queue.push_back(cmd1);   // add to back
3queue.push_front(cmd2);  // add to front
4auto c = queue.front();
5queue.pop_front();        // O(1)

Use when:

• You need O(1) insertion at both ends
• You need random access (unlike list)
• The working set is small enough that cache misses from segmentation don’t matter

Don’t use when:

• You need contiguous memory (span, DMA, C APIs)
• You’re iterating heavily — vector is faster for sequential access

In practice, std::deque is used for BFS queues, undo stacks with front access, and task queues where items arrive at both ends. For a simple FIFO, it’s cleaner than std::queue (which defaults to deque anyway).

std::list — doubly linked list

std::list<T> is a doubly linked list. Each element is a separate heap allocation. O(1) insert/erase anywhere if you have an iterator to the position.

 1std::list<Task> tasks;
 2tasks.push_back(t1);
 3tasks.push_front(t2);
 4
 5// Splice — O(1) transfer between lists, no copy
 6std::list<Task> pending;
 7auto it = tasks.begin();
 8pending.splice(pending.end(), tasks, it);  // moves *it to pending, O(1)
 9
10// Erase by iterator — O(1)
11auto pos = std::find(tasks.begin(), tasks.end(), target);
12if (pos != tasks.end()) tasks.erase(pos);  // O(1) erase, O(n) find

Use when:

• Iterator stability under insertion/erasure is required (iterators to other elements remain valid)
• You need O(1) splice (moving ranges between lists without copying)
• You’re implementing a data structure that inherently requires linked nodes (e.g., a timer wheel)

Don’t use for: anything where you iterate the whole container. Cache miss per element makes std::list iteration drastically slower than std::vector.

A vector with erase-remove is almost always faster than a list for typical use cases where you thought you needed a list.

std::set / std::map — sorted tree

std::set<T> and std::map<K, V> are red-black trees. O(log n) insert, erase, find. Sorted order. Every node is a heap allocation — same cache penalty as list.

1std::map<std::string, Config> settings;
2settings["baud"] = Config{115200};
3auto it = settings.find("baud");  // O(log n)

Use when:

• You need sorted order and O(log n) operations
• You need iterator stability (iterators survive insert/erase of other elements)

Prefer std::unordered_map when you only need O(1) average lookup and don’t care about order:

1std::unordered_map<std::string, Config> settings;
2settings["baud"] = Config{115200};
3auto it = settings.find("baud");  // O(1) average

For small fixed-size key-value stores (under ~20 entries), a sorted vector of pairs with std::lower_bound is often faster than either — no heap node overhead, cache-friendly, binary search in O(log n).

Decision guide

Do you know the size at compile time?
  Yes → std::array<T, N>

Is the size dynamic?
  Do you need O(1) at both ends?
    Yes → std::deque
    No  → std::vector  ← default

Do you need O(1) insert/erase in the middle with iterator stability?
  Yes → std::list (and profile — it's rarely worth it)

Do you need sorted key lookup?
  O(log n), ordered, stable → std::map / std::set
  O(1) average, unordered   → std::unordered_map / std::unordered_set

Embedded containers

On MCUs without heap or with strict memory constraints, standard containers that allocate are often banned. Alternatives:

Embedded Template Library (ETL) provides heap-free versions of most STL containers with fixed compile-time capacity.

Summary

• std::array — compile-time size, stack, zero overhead — embedded default for fixed buffers
• std::vector — dynamic, contiguous, cache-friendly — the default for everything else
• std::deque — O(1) at both ends, random access — task queues, BFS
• std::list — O(1) insert/erase anywhere, stable iterators, splice — rarely worth the cache cost
• std::map/set — sorted tree, O(log n) — when sorted order or iterator stability matter
• std::unordered_map — hash table, O(1) average — when lookup speed matters, order doesn’t

What’s next

• std::variant and std::optional — type-safe alternatives to void* and sentinel values
• std::span and string_view — non-owning views into any contiguous container
• Smart pointers and ownership — owning containers of dynamically typed objects