std::map & std::multimap

std::map<Key, Value> is the standard library's sorted associative container of key-value pairs. It uses the same balanced binary search tree as std::set (red-black tree in every mainstream implementation), but each node stores a std::pair<const Key, Value> instead of just a key. std::multimap<Key, Value> is the variant that lets multiple values share a key. This chapter covers the data layout, the insertion and access APIs, the famous operator[] gotcha, structured-binding iteration, and multimap differences.