Most efficient way to get the index of an iterator for a map? C++

Question

Similar to this thread, I'm trying to get the integer index from an iterator but for a map instead of an vector. Atm its causing a large bottle neck in my code and I was wondering if there was a more efficient way to get the index other that what I'm doing currently...

auto itTail = nodesMap.find(tail);
tailNodePos = distance(nodesMap.begin(), itTail);

Answer 1

I would say it is impossible to get the index for an arbitrary iterator for a map faster than O(container size)(according to map specification in C++ standard). If it is very important to do it much faster, I would try using custom balanced binary search tree(because it is possible to get an index for a node in a tree in O(log(container size)) if each node in a tree maintains sub tree size).
And if there are no inserts and deletes performed, it is easy to use sorted vector and lower_bound instead of map and find(this approach allows to get the index in O(1) because vector iterator is a random access iterator).

Answer 2

If you want a container with fast indexing (nth element, and index-of-element) and fast sort-ordered insert/delete, you will have to write your own, or find one outside of std.

It is not that tricky a design -- a b-tree or rb-tree where each node also keeps count of how many nodes are under it has only a modest overhead over a 'naked' one. Writing the rest of the interface to match std::map is a slog, as is writing raw tree manipulation code.

I tried to find one in boost a few years ago and failed. Maybe something with multi-index container: but there, the sequence is order of insertion, not order-in-map component.