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?
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.