...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 circumstances explained in the Stateful value traits section; if the programmer uses hooks provided by Boost.Intrusive, those functions will be available.
Let's see a 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 <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) { //Use your favorite hash function, like boost::hash or std::hash return std::size_t(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 std::size_t 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(std::size_t i = 0; i < MaxElem; ++i) nodes[i].set((int)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(std::size_t 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(std::size_t 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; }