All Associative Containers

All Associative Containers

A compact index of ordered and unordered associative containers, lookup operations, and container-selection rules.

How to use this reference page

Use reference pages to confirm names, categories, nearby facilities, and the constraints that matter before writing or reviewing code.

Scan the top of the page first to identify the primary types, functions, or algorithm families involved.
Use the nearby-page links when your question is really about a companion header, related algorithm family, or broader subsystem.
Validate tricky behavior with a small compileable example before relying on memory for details like invalidation, ordering, allocation, or lifetime rules.

All Associative Containers

Ordered associative containers

std::map
std::multimap
std::set
std::multiset

These maintain key order and support ordered queries such as lower_bound, upper_bound, and equal_range.

Unordered associative containers

std::unordered_map
std::unordered_multimap
std::unordered_set
std::unordered_multiset

These are hash-based and optimize average lookup speed when ordering does not matter.

Common lookup and modification operations

find
contains
count
equal_range
lower_bound, upper_bound for ordered containers
insert, emplace, try_emplace, insert_or_assign
erase, extract, merge

Node handles and heterogeneous lookup

node extraction via extract
node transfer via merge
transparent comparators and hash/equality functors for heterogeneous lookup

Selection rules

Use ordered containers when sorted traversal or range queries matter.
Use unordered containers when key hashing is cheap and iteration order does not matter.
Use map when values are attached to keys; use set when the key itself is the value.

Example in practice

#include <map>
#include <string>

int main() {
    std::map<std::string, int> counts{std::pair{"Ada", 1}, std::pair{"Bjarne", 2}};
    auto [it, inserted] = counts.insert({"Grace", 3});
    return inserted ? it->second : 1;
}