Re: [Boost-users] multi_index:iterator_to complexity

9 Mar 2015

      Matwey V. Kornilov  writes:
...
09.03.2015 10:02, Joaquin M Lopez Munoz пишет:
...
iterator_to does not do any kind of search based on x, but takes a
reference to an element of the container and returns an iterator to
it (roughly speaking, converts an element pointer to a node pointer).
 [...]
As far as I understand, there should be some pointer magic, like the
following
struct node {
  T obj;
  ... // Rest
};
so given x, (node*)&x will point to the struct enveloping the object and
should provide access to index-specific data to allow iterator
incrementation and dereferencing. What kind of additional data is stored
in node?
None. The thing is done via some careful casting (careful so as to stay
within what the standard allows for): this is the key code, at lines
64-69 and 87-93 of boost/multi_index/detail/index_node_base.hpp:

static index_node_base* from_value(const value_type* p)
{
  return static_cast(
    reinterpret_cast( /* std 9.2.17 */
      const_cast(p)));
}

template
Node* node_from_value(const Value* p)
{
  typedef typename Node::allocator_type allocator_type;
  return static_cast(
    index_node_base::from_value(p));
}
...
What I want is to understand if the following code is correct and works
in O(1):
[...]
        auto it = map_.get<1>().find(key);
        if (it != map_.get<1>().end() ) {
                 map_.get<0>().iterator_to(*it)-map_.get<0>().begin();
        }
This is correct and works in O(1). Additionally, you might want
to use project, which is specifically designed for converting iterators
between indices:

        auto it = map_.get<1>().find(key);
        if (it != map_.get<1>().end() ) {
                 map_.project<0>(it)-map_.get<0>().begin();
        }

Performance is going to be the same or even better (if the optimizer's
not too good), and this is probably clearer.

Joaquín M López Muñoz
Telefónica