Re: [Boost-users] multi_index:iterator_to complexity

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> gmail.com> 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
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?

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<
container_value_type,
                boost::multi_index::indexed_by<
                        boost::multi_index::random_access<>,
                        boost::multi_index::hashed_unique<
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() ) {
                 map_.get<0>().iterator_to(*it)-map_.get<0>().begin();
// unique number from 0 to map_.size()-1
        }