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.