Boost logo

Boost Users :

Subject: Re: [Boost-users] multi_index:iterator_to complexity
From: Matwey V. Kornilov (matwey.kornilov_at_[hidden])
Date: 2015-03-09 08:51:53

09.03.2015 10:02, Joaquin M Lopez Munoz пишет:
> Matwey V. Kornilov <matwey.kornilov <at>> writes:
>> Hi,
>> The following two calls have constant complexity (according to docs) for
>> all indices:
>> iterator iterator_to(const value_type& x);
>> const_iterator iterator_to(const value_type& x) const;
> Correct, these are constant complexity.
>> As far as I understand, the single way to reach the constant complexity
>> in searching by pointer is to store the objects in continuous memory area.
>> Is it correct?
> No, it's not correct. In fact, elements in a multi_index_container are
> *not* stored contiguously.
> 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). So, whereas the
> following works as expected:
> multi_index_container<int,...> m;
> ...
> const int& x=*(m.find(...));
> auto it=m.iterator_to(x);

As far as I understand, there should be some pointer magic, like the

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?

What I want is to understand if the following code is correct and works
in O(1):

        typedef std::pair<const Key, Value> container_value_type;
        typedef boost::multi_index::multi_index_container<
boost::multi_index::member< container_value_type, const Key,
&container_value_type::first> >
> > container_type;

        container_type map_;

        auto it = map_.get<1>().find(key);
        if (it != map_.get<1>().end() ) {
// unique number from 0 to map_.size()-1

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at