Complexity of the projection of iterators functionality in boost::multi_index containers

Question

Does anyone know anything about the complexity of the projection of iterators within the boost::multi_index library? The documentation can be found here boost::multi_index projection of iterators but it doesn't state the complexity of the operation.

The basic idea is that you can retrieve an iterator to an object within an index and then project this into a second index and get an iterator to the same object but within the second index. If this is an O(1) operation then you can effectively maintain two indices, one that is searchable in fast time and one that is slower. The projection of iterators, as I understand it, allows me to find an object in the index that is more quickly searched and then project it into the slower-searchable index.

I'm keen to know whether it is a simple O(1) lookup for the projection of iterators or whether it effectively just kicks off a find operation in the second index and therefore is dependant on the particular index you are projecting to and is slower than O(1).

Many thanks for any help!

Answer 1

It is constant time, as specified in the documentation, and, indeed, as fast as it gets:

  template<int N,typename IteratorType>
  typename nth_index_iterator<N>::type project(IteratorType it)
  {
    typedef typename nth_index<N>::type index_type;
    ...
    return index_type::make_iterator(static_cast<node_type*>(it.get_node()));
  }

This is merely a rewrapping of the internal node pointer held by any index iterator.