Cauchy Cauchy - 1 year ago 142
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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download