CKTIS / C++
std::map — an ordered map of unique keys
std::map stores key–value pairs in comparator order, with at most one element for each equivalent key. Learn non-mutating lookup, insertion, erasure, and node transfer, including why operator[] is not a presence check.
Version: C++23; repository compiler flag, production runtime not attested
Syntax
#include <map>
std::map<Key, T> m;
std::map<Key, T, Compare> ordered;std::map<Key, T, Compare> from <map> stores std::pair<const Key, T> elements in comparator order; the default uses std::less<Key>. Compare must define a strict weak ordering. Keys are equivalent when !comp(a, b) && !comp(b, a), not necessarily when a == b. The map allows only one such key; an iterator lets you modify the value, but not the key.
To select the single-element overload of std::map::insert, explicitly construct an element of the map's value_type: m.insert(value_type{key, value}). This overload returns an iterator–bool pair: if an equivalent key already exists, the bool is false and the stored value is not overwritten. If key and value are each implicitly convertible to value_type, m.insert({key, value}) can instead select the std::initializer_list<value_type> overload, which returns void and attempts to insert two elements. In the std::map<int, int> example, the braced call selects the single-element overload. std::map::find returns an iterator or std::map::end; end() points past the last element and must not be dereferenced. std::map::contains returns bool, while std::map::count returns 0 or 1. std::map::equal_range returns a half-open range [first, last) containing zero or one element. These lookup operations do not insert elements and take O(log n).
std::map::operator[] returns a reference to the value; if the key is missing, it inserts a new element for that key. With the default allocator, the mapped value is value-initialized (for example, to 0 for int), which requires T to be default-constructible. A custom allocator can change how the element is constructed. Do not use [] merely to check presence. std::map::erase(key) returns the number removed, while erase(it) returns the next iterator and requires a dereferenceable iterator. std::map::size returns the element count in O(1). Ordinary insertion and key-based erasure take O(log n); iterator-based erasure is amortized O(1). Insertion invalidates no iterators or references; erasure invalidates only those to erased elements.
std::map::extract detaches a node without copying or moving its element; a missing key yields an empty handle. Check empty() before key(); a detached key can be changed before reinserting the node. std::map::merge transfers type-compatible nodes without copying or moving elements; conflicting keys remain in the source. Node transfer requires equal allocators. The example uses operations available in C++23; the linked document is an evolving draft, not the frozen C++23 standard. The repository compiler flag does not attest the production runtime.
Examples
#include <iostream>
#include <map>
#include <utility>
int main() {
std::map<int, int> m{{2, 20}};
auto result = m.insert({2, 99});
std::cout << std::boolalpha << "inserted=" << result.second << '\n';
m[1] += 10;
if (auto it = m.find(2); it != m.end()) {
std::cout << "found=" << it->second << '\n';
}
auto [first, last] = m.equal_range(2);
std::cout << "contains=" << m.contains(2)
<< " count=" << m.count(2)
<< " range=" << (first != last) << '\n';
auto node = m.extract(1);
if (!node.empty()) {
node.key() = 3;
m.insert(std::move(node));
}
std::map<int, int> source{{2, 200}, {4, 40}};
m.merge(source);
std::cout << "erased=" << m.erase(2)
<< " size=" << m.size()
<< " source=" << source.size() << '\n';
for (const auto& [key, value] : m) {
std::cout << key << ':' << value << '\n';
}
}
Result
inserted=false found=20 contains=true count=1 range=true erased=1 size=2 source=1 3:10 4:40
The displayed code and declared result were verified in an isolated environment using the method recorded in the verification evidence for this exact version.