...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
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:
type
member that
defines the type of the key
value_type
,
either by value or by const-reference.
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 if the container constructor requires it //- define the key type using "type" //- define an operator() taking "const value_type&" and // returning "type" or "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; }