Cauchy Cauchy - 1 year ago 129
C++ Question

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

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 Source

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.