Re: [Boost-users] multi_index:iterator_to complexity

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); the following does not: multi_index_container m; ... int x=*(m.find(...)); auto it=m.iterator_to(x); // undefined behavior because x is a copy of a value inside m, not a reference to the value itself, which is what iterator_to requires. Joaquín M López Muñoz Telefónica