Skip to content

Latest commit

 

History

History
87 lines (67 loc) · 4.15 KB

README.md

File metadata and controls

87 lines (67 loc) · 4.15 KB

Containers library

The standard containers, grouped as cppreference groups them. ✅ Complete.

Sequence containers

Elements in a linear order you control.

Container Header Since Notes
array <array> C++11 Fixed-size, stack-allocated
vector <vector> C++98 Growable contiguous array — the default choice
inplace_vector <inplace_vector> C++26 Fixed-capacity vector, no heap
hive <hive> C++26 O(1) insert/erase, stable refs, reuses erased slots
deque <deque> C++98 Fast push/pop at both ends
list <list> C++98 Doubly-linked list
forward_list <forward_list> C++11 Singly-linked list

Associative containers (ordered)

Sorted by key; balanced-tree based.

Container Header Since Notes
set <set> C++98 Unique sorted keys
multiset <set> C++98 Sorted keys, duplicates allowed
map <map> C++98 Sorted key→value, unique keys
multimap <map> C++98 Sorted key→value, duplicate keys

The sorted flat_* containers are associative in spirit but cppreference classifies them as container adaptors — see below.

Unordered associative containers (hash-based)

Average O(1) lookup; no ordering.

Container Header Since Notes
unordered_set <unordered_set> C++11 Hashed unique keys
unordered_multiset <unordered_set> C++11 Hashed keys, duplicates allowed
unordered_map <unordered_map> C++11 Hashed key→value, unique keys
unordered_multimap <unordered_map> C++11 Hashed key→value, duplicate keys

Container adaptors

Wrap one or more underlying containers to provide a restricted/different interface. cppreference groups the sorted flat_* containers here too.

Adaptor Header Since Notes
stack <stack> C++98 LIFO
queue <queue> C++98 FIFO
priority_queue <queue> C++98 Heap; largest-first by default
flat_set / flat_multiset <flat_set> C++23 Sorted set backed by a contiguous array
flat_map / flat_multimap <flat_map> C++23 Sorted map backed by two arrays

Views (related — not containers)

Non-owning windows over existing storage.

View Header Since Notes
span <span> C++20 Contiguous 1-D view
mdspan <mdspan> C++23 Multidimensional view

Which container should I use? (cheat sheet)

  • Need a resizable list of things? → vector (default). Reach for something else only when a measured need says so.
  • Fixed number of elements known at compile time? → array (or inplace_vector if the count varies up to a fixed cap, C++26).
  • Lots of insert/remove at both ends? → deque.
  • Splicing nodes / stable element addresses / O(1) middle insert with an iterator? → list (or forward_list to save memory).
  • Frequent insert/erase with stable references to survivors, order doesn't matter? → hive (C++26) — like list's stability but cache-friendly.
  • Keep keys sorted, need ordered traversal / range queries? → set / map (or flat_set / flat_map for cache-friendly read-heavy use, C++23).
  • Just fast membership / lookup, order doesn't matter? → unordered_set / unordered_map.
  • Restricted LIFO/FIFO/priority access? → stack / queue / priority_queue.
  • Pass "a contiguous block of N elements" without copying or templating on the container? → span (1-D) / mdspan (N-D).