C++ map:将对添加到地图的末尾

Question

我试图找到一种更快的方法来将对添加到地图的末尾.目前,我在地图的末尾添加了对,因为我使用的键是for循环的索引,默认排序.所以我有:

#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));

        }

}

当我计时时,大约需要10秒钟.但是,当我注释掉该行时temp.insert(temp.end(), std::pair<int, std::set<int> >(i, temp4)),程序执行大约需要4秒钟.我想知道为什么将这对添加到地图需要花费很多时间.我是以最好的方式做到的吗？

Answer 1

对于初学者来说,这不仅仅是一些微不足道的小配对.它是一对包含整个容器的.

虽然是一个小容器.但它已经填充,并且将其插入另一个容器的行为意味着需要复制整个容器.

但更重要的std::map是,a 不是一个累积常数插入复杂度的向量.它通常是平衡树的一些变体,通常是大多数C++实现上的红黑树.

这意味着insert()无论是否暗示,在地图最末端重复的s通常都需要重新平衡整个树.这不是一个便宜的操作.并且,通过重复插入始终在键空间末端排序的键,可怜的地图必须一遍又一遍地保持自我重新平衡.