Re: [Boost-users] multi_index:iterator_to complexity

09.03.2015 10:02, Joaquin M Lopez Munoz пишет:

Matwey V. Kornilov 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 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 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 }