Associative containers (C++)
| C++ Standard Library |
|---|
| Containers |
| C standard library |
In C++, associative containers are class templates in the standard library that maintain their elements in an order determined by their keys and provide key-based lookup. They reside in namespace std and are parameterized by a key type, a comparison function, and an allocator; maps also have a mapped-value type.
The standard specifies four basic associative containers:
std::set<T>std::map<K, V>std::multiset<T>std::multimap<K, V>
set and map store at most one element for each equivalent key, whereas multiset and multimap permit multiple elements with equivalent keys. Maps store a mapped value with each key; sets store keys alone.
Since C++17, alias templates for these containers have also been provided in namespace std::pmr; they use std::pmr::polymorphic_allocator as the allocator type.
std::set and std::multiset are declared in header <set>, while std::map and std::multimap are declared in header <map>.
Unlike the unordered associative containers, which organize elements into hash-table buckets and do not specify an overall iteration order, associative containers traverse their elements in non-descending key order. The two groups also provide different complexity guarantees.
std::map and std::set are commonly implemented as red-black trees, although the standard does not require that representation. Comparable ordered map and set types include java.util.TreeMap and java.util.TreeSet in Java, System.Collections.Generic.SortedDictionary and System.Collections.Generic.SortedSet in .NET, and std::collections::BTreeMap and std::collections::BTreeSet in Rust.