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 不是具有摊销常数插入复杂性的向量。它通常是平衡树的一些变体，typically a red-black tree 在大多数 C++ 实现中。

这意味着在地图的最后重复 insert()s，无论是否提示，通常都需要重新平衡整棵树。这不是一个便宜的操作。并且，通过重复插入始终排在键末尾的键 space，可怜的地图必须一遍又一遍地重新平衡自己。

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

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

c++

std