Why is there no boost :: intrusive :: map?

Question

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

Answer 1

This is because map<Key, Value> is actually set<std::pair<Key const, Value>> , and the Boost.Intrusive and Boost.MultiIndex settings allow you to use one of the value members as a key. In other words, there is no need for map if find can take a comparable key, and not the whole value for the search , which was a long incomprehensible problem with std::map and std::set :

The associative container search functions (find, lower_bound, upper_bound, equal_range) accepts only the key_type argument, which requires the user to create (either implicitly or explicitly) the key_type object to search. It can be expensive, for example. building a large object to search in the set when the comparator function looks at only one field of the object. There is a strong desire among users that they can look for other types that are comparable to the key.

Answer 2

Since version 1.59 Boost.Intrusive supports cartographic associative containers . It is significantly more flexible than standard cardboard containers, since the programmer does not need to define any std::pair structure to define key_type and mapped_type . The new key_of_value option is added to intrusive sets of interfaces that determine how much of the value should be treated as key_type and how to get it. This was done to simplify the use of cartographic use 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; }