Map and multimap-like interface for associative containers

| Home | Libraries | People | FAQ | More

## Map and multimap-like interface for associative containers

Implementing map-like intrusive containers is not a trivial task as STL's `std::map` and `std::multimap` containers store copies of a `value_type` which is defined as `std::pair<const key_type, mapped_type>`. In order to reproduce this interface in Boost.Intrusive it shall require that objects stored in the intrusive containers contain that `std::pair` member with `pair.first` hardcoded as the key part and `pair.second` hardcoded as the `mapped_type`, which is limiting and also not very useful in practice. Any intrusive associative container can be used like a map using advanced lookup and insertions and the user can change the key type in each lookup/insertion check call.

On the other hand, in many cases containers are indexed by a well-known key type, and the user is forced to write some repetitive code using advanced lookup and insertions. Boost.Intrusive associative containers offer an alternative to build a useful map-like lookup interfaces without forcing users to define `value_type`s containing `std::pair`-like classes. The option is called `boost::intrusive::key_of_value`.

If a user specifies that option when defining a `set/multiset` intrusive container, it specifies a function object that will tell the container which is the type of the key that `value_type` holds and how to obtain it. This function object must be lightweight, `DefaultConstructible`, it shall define a `type` member that defines the type of the key and a member function to obtain a const reference to the key stored inside a `value_type`. Let's see an example of how a set can be configured as a map indexed by an integer stored in the `value_type`.

    #include <boost/static_assert.hpp>
    #include <boost/type_traits/is_same.hpp>
    #include <boost/intrusive/set.hpp>
    #include <boost/intrusive/unordered_set.hpp>
    #include <vector>
    #include <cassert>

    using namespace boost::intrusive;

    class MyClass : public set_base_hook<>
                  , public unordered_set_base_hook<>
    {
       public:
       int first;
       explicit MyClass(int i) : first(i){}
    };

    //key_of_value function object, must:
    //- be default constructible (and lightweight)
    //- define the key type using "type"
    //- define an operator() taking "const value_type&" and
    //    returning "const type &"
    struct first_int_is_key
    {
       typedef int type;

       const type & operator()(const MyClass& v) const
       {  return v.first;  }
    };

    //Define omap like ordered and unordered classes
    typedef set< MyClass, key_of_value<first_int_is_key> > OrderedMap;
    typedef unordered_set< MyClass, key_of_value<first_int_is_key> > UnorderedMap;

    int main()
    {
       BOOST_STATIC_ASSERT((boost::is_same<  OrderedMap::key_type, int>::value));
       BOOST_STATIC_ASSERT((boost::is_same<UnorderedMap::key_type, int>::value));

       //Create several MyClass objects, each one with a different value
       //and insert them into the omap
       std::vector<MyClass> values;
       for(int i = 0; i < 100; ++i)  values.push_back(MyClass(i));

       //Create ordered/unordered maps and insert values
       OrderedMap   omap(values.begin(), values.end());
       UnorderedMap::bucket_type buckets[100];
       UnorderedMap umap(values.begin(), values.end(), UnorderedMap::bucket_traits(buckets, 100));

       //Test each element using the key_type (int)
       for(int i = 0; i != 100; ++i){
          assert(omap.find(i) != omap.end());
          assert(umap.find(i) != umap.end());
          assert(omap.lower_bound(i) != omap.end());
          assert(++omap.lower_bound(i) == omap.upper_bound(i));
          assert(omap.equal_range(i).first != omap.equal_range(i).second);
          assert(umap.equal_range(i).first != umap.equal_range(i).second);
       }

       //Count and erase by key
       for(int i = 0; i != 100; ++i){
          assert(1 == omap.count(i));
          assert(1 == umap.count(i));
          assert(1 == omap.erase(i));
          assert(1 == umap.erase(i));
       }
       assert(omap.empty());
       assert(umap.empty());

       return 0;
    }