Boost C++ Libraries of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards


Obtaining iterators from values

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_;

   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;