Associative containers (C++)

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.