Why isn't there boost::intrusive::map?

Question

The boost documentation (http://www.boost.org/doc/libs/1_55_0/doc/html/intrusive.html) states that the intrusive containers are implemented for list (both single/double linked), set and multiset. I couldn't find an implementation for the map. Is there any deeper reason for it, or is it just waiting to be implemented?

Answer 1

This is because a map<Key, Value> is actually set<std::pair<Key const, Value>> and Boost.Intrusive and Boost.MultiIndex sets allow you to use one of the value members as a key. In other words, there is no need for map if find can accept a comparable key, rather than the entire value to search for which has been a long-standing unresolved issue with std::map and std::set:

The associative container lookup functions (find, lower_bound, upper_bound, equal_range) only take an argument of key_type, requiring users to construct (either implicitly or explicitly) an object of the key_type to do the lookup. This may be expensive, e.g. constructing a large object to search in a set when the comparator function only looks at one field of the object. There is strong desire among users to be able to search using other types which are comparable with the key_type.

Answer 2

Since version 1.59 Boost.Intrusive supports map-like associative containers. It's considerably more flexible than standard map-like containers as the programmer isn't forced to define any std::pair like structure to define key_type and mapped_type. A new option key_of_value is added to intrusive set interfaces defining which part of the value shall be considered as key_type and how to obtain it. This was done to simplify map-like usage when using Boost.Intrusive. Example code taken from Boost documentation:

#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;
}