Slow performance using std::distance to get std::map index

Question

I have a std::map and I need all its key, value and index for some process.
My code works correctly. The only issue is: it's too slow.
Below is an example:

void run(const std::map <key, value>& myMap) {
    std::map <key, value>::const_iterator iter;
    for (iter = myMap.begin(); iter != myMap.end(); ++iter) {
        const auto& myKey = iter->first;
        const auto& myValue = iter->second;
        const auto index = std::distance(myMap.begin(), iter);
        // then some process here
    }
}

I use IgProf to profile the performance.

Rank    % total       Self       Self / Children   Function
[39]        8.2       9.06       0.69 / 8.37       run(const std::map <key, value>& myMap)
            5.6  .........       6.16 / 6.17         std::_Rb_tree_increment(std::_Rb_tree_node_base*) [clone .localalias.2] [54]
            1.4  .........       1.50 / 1.50         some process here [175]
            0.3  .........       0.36 / 0.36         std::_Rb_tree_increment(std::_Rb_tree_node_base const*) [428] 
            0.3  .........       0.34 / 0.83         _init [232] 

Here std::_Rb_tree_increment costs too much time.
In this example code, I can manually calculate the index:
replacing const auto index = std::distance(myMap.begin(), iter); by ++index;
I got a much faster performance

Rank    % total       Self       Self / Children   Function
[148]       2.3       2.42       0.60 / 1.81       run(const std::map <key, value>& myMap)
            1.7  .........       1.77 / 1.77         some process here [165]
            0.0  .........       0.03 / 0.04         std::_Rb_tree_increment(std::_Rb_tree_node_base*) [clone .localalias.2] [1268]
            0.0  .........       0.01 / 0.37         _init [420]

But in reality, I do need std::distance or something equivalent to get the index.
So I would really appreciate it if you could help me understand the reason of its slow performance.
Thanks in advance :)

Answer 1

std::map is a tree structure. It's not random access, and elements don't have indices, and the only way to advance through the tree is to follow the links, one at a time. Because of this, std::map::iterator is a BidirectionalIterator. That means it only supports increment and decrement operations. It doesn't support any sort of difference operation. To get the difference between two of them you have to repeatedly increment the start iterator until it's equal to the end iterator. Something like this:

template <typename Iterator>
size_t distance(Iterator start, Iterator end)
{
    size_t dist = 0;
    while (start != end) {
        ++dist;
        ++start;
    }
    return dist;
}

Looking at that function, you can probably see why your loop is slow. Every time through the loop, std::distance has to walk through the tree and count how far from the beginning it is. If you really need an index to go with your map, you'll need to maintain it yourself. std::map doesn't seem like the right structure in that case though, since the indices will change as new elements are added.