STL Associative Containers Notes

A brief look at STL associative containers, primarily map, multimap, set, multiset, and unordered_map. The first four are implemented using a red-black tree with O(log n) lookup, while unordered_map — as the name suggests — is an unordered container backed by a hash table with O(1) lookup.

set, multiset, map, multimap

set stores a sorted collection of unique elements — duplicates are not allowed. It is backed by a red-black tree. multiset works the same way but allows duplicate elements.

map is an associative table that can use any type as the key, with no duplicate keys. Its implementation mirrors set, both built on a red-black tree. multimap allows duplicate keys.

template<typename _Key, typename _Compare = std::less<_Key>,typename _Alloc = std::allocator<_Key> >
class set 
public:
    typedef _Key     key_type;
    typedef _Key     value_type;    // differs from map
    typedef _Compare key_compare;
    typedef _Compare value_compare; 
    typedef _Alloc   allocator_type;

private:
    typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template rebind<_Key>::other _Key_alloc_type;
    typedef _Rb_tree<key_type, value_type, _Identity<value_type>, key_compare, _Key_alloc_type> _Rep_type;
    
    _Rep_type _M_t;  // Red-black tree representing set.

    typedef __gnu_cxx::__alloc_traits<_Key_alloc_type> _Alloc_traits;

#if __cplusplus > 201402L
      using node_type = typename _Rep_type::node_type;
      using insert_return_type = typename _Rep_type::insert_return_type;
#endif

map follows the same design as set, except each element is a std::pair.

template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>,typename _Alloc=std::allocator<std::pair<const _Key, _Tp> > >
class map {
public:
    typedef _Key key_type;
    typedef _Tp mapped_type;
    typedef std::pair<const _Key, _Tp> value_type;      // stored as key-value pairs
    typedef _Compare key_compare;                       // RB-tree needs element comparison
    typedef _Alloc allocator_type;

private:
    /// This turns a red-black tree into a [multi]map.
    typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template rebind<value_type>::other _Pair_alloc_type;
    typedef _Rb_tree<key_type, value_type, _Select1st<value_type>, key_compare, _Pair_alloc_type> _Rep_type;

    /// The actual tree structure.
    _Rep_type _M_t;     // underlying RB-tree

    typedef __gnu_cxx::__alloc_traits<_Pair_alloc_type> _Alloc_traits;

public:
    // operator[] overload
    mapped_type& operator[](const key_type& __k) {
	    // concept requirements
	    __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)
        iterator __i = lower_bound(__k);
	    // __i->first is greater than or equivalent to __k.
	    if (__i == end() || key_comp()(__k, (*__i).first))
#if __cplusplus >= 201103L
	        __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct, std::tuple<const key_type&>(__k),
std::tuple<>());
#else
	        __i = insert(__i, value_type(__k, mapped_type()));
#endif
	    return (*__i).second;
    }
}

Further implementation details are omitted; once you understand red-black trees, the rest follows easily.

unordered_map

Unlike map, unordered_map is backed by a hash table — understand hashing, and you’ll understand unordered_map.

template<class _Key, class _Tp,class _Hash = hash<_Key>,class _Pred = std::equal_to<_Key>,class _Alloc=std::allocator<std::pair<const _Key, _Tp> > >
class unordered_map {
    typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc>  _Hashtable;
    _Hashtable _M_h;    // underlying hash table implementation

public:
    // typedefs:
    //@{
    /// Public typedefs.
    typedef typename _Hashtable::key_type	key_type;
    typedef typename _Hashtable::value_type	value_type;
    typedef typename _Hashtable::mapped_type	mapped_type;
    typedef typename _Hashtable::hasher	hasher;
    typedef typename _Hashtable::key_equal	key_equal;
    typedef typename _Hashtable::allocator_type allocator_type;
    //@}

#if __cplusplus > 201402L
      using node_type = typename _Hashtable::node_type;
      using insert_return_type = typename _Hashtable::insert_return_type;
#endif