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

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 :)

CodePudding user response：

The for-loop is myMap.size() iterations. std::distance(myMap.begin(), iter); is 0 -- myMap.size() - 1 iterations. You get the complexity O(myMap.size()²).

Back to the linear complexity O(myMap.size()):

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

std::map iterator is LegacyBidirectionalIterator, that is not a random access iterator (index in your terms), and supports only a, a , --a, a-- operations (not a index, a - index in your terms).

CodePudding user response：

The class template std::map has bi-directional iterators, but not random-access iterators. So the call of std::distance() traverses all iterators between the two specified.

But in your case, the call of std::distance() is entirely redundant. You could just declare a variable of the type size_t as an index and increment it in each iteration of the loop.