...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
Boost.Intrusive offers another useful feature
that's not present in STL containers: it's possible to obtain an iterator to
a value from the value itself. This feature is implemented in Boost.Intrusive
containers by a function called iterator_to
:
iterator iterator_to(reference value); const_iterator iterator_to(const_reference value);
For Boost.Intrusive containers that have local iterators, like unordered associative containers, we can also obtain local iterators:
local_iterator local_iterator_to(reference value); const_local_iterator local_iterator_to(const_reference value) const;
For most Boost.Intrusive containers (list
, slist
,
set
, multiset
)
we have an alternative static s_iterator_to
function.
For unordered associative containers (unordered_set
,
multiset
), iterator_to
has no static alternative function.
On the other hand, local_iterator_to
functions have their s_local_iterator_to
static alternatives.
Alternative static functions are available under certain circunstances explained in the Stateful value traits section, but the programmer uses hooks provided by Boost.Intrusive, those functions will be available.
Let's see an small function that shows the use of iterator_to
and local_iterator_to
:
#include <boost/intrusive/list.hpp> #include <boost/intrusive/unordered_set.hpp> #include <boost/functional/hash.hpp> #include <vector> using namespace boost::intrusive; class intrusive_data { int data_id_; public: void set(int id) { data_id_ = id; } //This class can be inserted in an intrusive list list_member_hook<> list_hook_; //This class can be inserted in an intrusive unordered_set unordered_set_member_hook<> unordered_set_hook_; //Comparison operators friend bool operator==(const intrusive_data &a, const intrusive_data &b) { return a.data_id_ == b.data_id_; } friend bool operator!=(const intrusive_data &a, const intrusive_data &b) { return a.data_id_ != b.data_id_; } //The hash function friend std::size_t hash_value(const intrusive_data &i) { return boost::hash<int>()(i.data_id_); } }; //Definition of the intrusive list that will hold intrusive_data typedef member_hook<intrusive_data, list_member_hook<> , &intrusive_data::list_hook_> MemberListOption; typedef list<intrusive_data, MemberListOption> list_t; //Definition of the intrusive unordered_set that will hold intrusive_data typedef member_hook < intrusive_data, unordered_set_member_hook<> , &intrusive_data::unordered_set_hook_> MemberUsetOption; typedef boost::intrusive::unordered_set < intrusive_data, MemberUsetOption> unordered_set_t; int main() { //Create MaxElem objects const int MaxElem = 100; std::vector<intrusive_data> nodes(MaxElem); //Declare the intrusive containers list_t list; unordered_set_t::bucket_type buckets[MaxElem]; unordered_set_t unordered_set (unordered_set_t::bucket_traits(buckets, MaxElem)); //Initialize all the nodes for(int i = 0; i < MaxElem; ++i) nodes[i].set(i); //Now insert them in both intrusive containers list.insert(list.end(), nodes.begin(), nodes.end()); unordered_set.insert(nodes.begin(), nodes.end()); //Now check the iterator_to function list_t::iterator list_it(list.begin()); for(int i = 0; i < MaxElem; ++i, ++list_it) if(list.iterator_to(nodes[i]) != list_it || list_t::s_iterator_to(nodes[i]) != list_it) return 1; //Now check unordered_set::s_iterator_to (which is a member function) //and unordered_set::s_local_iterator_to (which is an static member function) unordered_set_t::iterator unordered_set_it(unordered_set.begin()); for(int i = 0; i < MaxElem; ++i){ unordered_set_it = unordered_set.find(nodes[i]); if(unordered_set.iterator_to(nodes[i]) != unordered_set_it) return 1; if(*unordered_set.local_iterator_to(nodes[i]) != *unordered_set_it || *unordered_set_t::s_local_iterator_to(nodes[i]) != *unordered_set_it ) return 1; } return 0; }