C++ map: add pair to the end of the map

Question

I am trying to find a faster way to add pairs to the end of a map. Currently, I am adding the pairs at the end of the map and since the key I am using is the index of the for loop which is sorted by default. So I have:

#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>

int main()
{

        std::map<int, std::set<int> > temp;

        for(int i = 0; i < 1000000; i++){

                int first[] = {5,10,15,20,25};
                int second[] = {10,20,30,40,50};

                std::set<int> temp2;
                temp2.insert(first, first + 5);
                std::set<int> temp3;
                temp3.insert(second, second + 5);

                std::set<int> temp4;
                std::set_union(temp2.begin(), temp2.end(), temp3.begin(), temp3.end(), std::inserter(temp4, temp4.end()));

                temp.insert(temp.end(), std::pair<int, std::set<int> >(i, temp4));

        }

}

When I time this, it takes about 10 seconds. However, when I comment out the line temp.insert(temp.end(), std::pair<int, std::set<int> >(i, temp4)), the program takes about 4 seconds to execute. I am wondering why adding the pair to the map takes so much time. Am I doing it in the best way possible?

Answer 1

For starters, this is not just some puny little pair. It's a pair that contains an entire container.

Albeit a small container. But it is already populated, and the act of inserting it into another container means that this entire container will need to be copied.

But more importantly, a std::map is not a vector that has amortized constant insert complexity. It is typically some variation of a balanced tree, typically a red-black tree on most C++ implementations.

This means that repeated insert()s at the very end of the map, whether hinted or not, will often require the entire tree to be rebalanced. This is not a cheap operation. And, by repeatedly inserting keys that are always ordered at the end of the key space, the poor map has to keep rebalancing itself, over and over again.