7

map::insert(iterator position, const value& k)通过在参数位置提供适当的值，可以显着提高效率。

如果我使用整数作为键，并且每次插入都使用比所有先前插入的键都大的数字来完成，我可以在给出映射的迭代器::insert时加快操作吗？::end()

就像是：

myMap.insert( myMap.end() , make_pair( next_number , myValue ) );

其中myMap是类型map<uint64_t,MyType>并且next_number是每递增的大整数。

编辑：

这个问题的答案可能会有所不同，具体取决于存储在其中的数据是否map密集（参见下面的讨论）。所以，让我们从两个方面来问这个问题：一旦它稠密，一旦它不稠密。还是很好奇。也许测量会回答这个问题。

4

4 回答 4

4

为了直接回答所提出的问题，C++ 规范说：

  • 在 C++03 中，a.insert(p,t)如果t在. p
  • 在 C++11 中，a.insert(p,t)如果t在. p

在这两种情况下都不p需要可取消引用。因此，在您的情况下，a.end()可能是 C++11 中的最佳提示，但不是 C++03 中的最佳提示。

于 2012-06-04T23:33:14.123 回答
2

我建议两件事：

  • 在这种情况下更喜欢std::unordered_map，总是在一端插入是红黑树的最坏情况
  • 如果被证明很麻烦，请使用自定义分配器new，从您所说的可以使用池分配策略

请注意，C++11 允许使用有状态分配器，因此提供适合并嵌入其中的分配器std::vector<T>并将其用作堆栈应该很容易。

于 2012-06-05T07:15:45.393 回答
1

任何建议都只是一个建议，是要尝试和衡量的东西。我们无法真正告诉您执行插入的最高效方式，您应该针对自己的特定用例进行衡量，看看什么是最好的。

如果您的地图紧凑且密集（从 0 到最大键的几乎所有项目都被真实数据占用）并且最大键足够低以成为合理的数组索引，您可以切换到使用 astd::vector<value>并始终插入到末尾。由于它不断增长，您有时需要重新分配向量（通常是当向量加倍时）。这可能很昂贵，但通常插入会非常便宜。您不必处理二叉树的潜在重新平衡，并且向量对于其他目的非常缓存友好。

如果您的地图的键空间不紧凑/密集，并且最大键太大以至于它不是一个可以想象的内存索引，那么带有提示的插入将是您最好的选择。

如果顺序无关紧要，您可以尝试std::unordered_map。这是一个哈希表实现。所以插入成本将与散列的质量和速度有关。获取 64 位密钥并将其转换为 size_t 散列（size_t 甚至可能是 64 位）应该是微不足道和快速的。

但不必相信我的话，测量它，然后自己看看......

于 2012-06-04T22:52:22.927 回答
1

自从我最近遇到这个问题以来，我做了一些测量。

我有一张大地图，有很多数据，很少插入数据，99% 的时间只是使用引用就地访问和修改。但是，这些数据最终必须保存到磁盘并重新加载。像“使用无序地图”这样的解决方案似乎是一种廉价的快速错误方法，有序地图对我来说是正确的方法，因为数据是有序的。唯一的问题是从文件加载。

我想知道这个操作的真正成本是多少以及如何加快它，所以我测量了：

// Example program
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <time.h>

std::vector<int> amount = {100, 1000, 10000, 100000, 1000000, 5000000};

int main()
{
  for(int j=0; j<amount.size(); j++) 
  {
    clock_t tStart = clock();

    std::map<int,int> mymap;
    for(int i=0; i<amount[j]; i++){
      mymap[i] = i;
    }

    printf("Time taken []: %.2fs\n", (double)(clock() - tStart));
  }
  for(int j=0; j<amount.size(); j++) 
  {
    clock_t tStart = clock();

    std::map<int,int> mymap;
    mymap[0] = 0;
    auto it = mymap.begin();
    for(int i=1; i<amount[j]; i++){
      it = mymap.insert(it, std::pair<int,int>(i,i));
    }

    printf("Time taken insert end()-1: %.2fns\n", (double)(clock() - tStart));
  }
  for(int j=0; j<amount.size(); j++) 
  {
    clock_t tStart = clock();

    std::map<int,int> mymap;
    for(int i=1; i<amount[j]; i++){
      mymap.insert(mymap.end(), std::pair<int,int>(i,i));
    }

    printf("Time taken insert end(): %.2fns\n", (double)(clock() - tStart));
  }
  for(int j=0; j<amount.size(); j++) 
  {
    clock_t tStart = clock();

    std::map<int,int> mymap;
    for(int i=0; i<amount[j]; i++){
      mymap.insert(mymap.begin(), std::pair<int,int>(i,i));
    }

    printf("Time taken insert begin(): %.2fs\n", (double)(clock() - tStart));
  }
  return 0;
}

结果：

Time in ns
N       end()-1 end()   begin() []
100     12      8       22      12
1000    77      54      188     97
10000   763     532     2550    1174
100000  7609    6042    23612   17164
1000000 75561   62048   270476  272099
5000000 362463  306412  1827807 1687904

在此处输入图像描述 在此处输入图像描述

概括：

  • 是的，有收获，巨大的收获，没有任何真正的缺点。对数据进行排序时，比无序地图要好得多，对于将地图保存到文件并重新创建它的情况非常有用。

  • 无论元素数量如何，如果提示正确，插入时间都是相同的。因此，无需重复使用散列无序映射来获得恒定时间。

  • 最坏的情况是，如果您的提示是最坏的提示，您可能会丢失一些提示。我认为在没有提示的情况下进行插入没有任何意义，特别是如果您知道数据将插入的位置。大多数时候你都会这样做。

于 2017-01-27T17:26:38.277 回答