C++ std :: map创建耗时太长了？

Question

更新:

我正在开发一个性能非常关键的程序.我有一个未排序的结构矢量.我需要在这个向量中执行许多搜索操作.所以我决定将矢量数据缓存到这样的地图中:

        std::map<long, int> myMap;

        for (int i = 0; i < myVector.size(); ++i)
        {
            const Type& theType = myVector[i];
            myMap[theType.key] = i;
        }

当我搜索地图时,程序其余部分的结果要快得多.然而,剩下的瓶颈是地图本身的创建(平均花费大约0.8毫秒来插入约1,500个元素).我需要想办法减少这个时间.我只是插入一个long作为键和一个int作为值.我不明白为什么这么久.

我的另一个想法是创建一个向量的副本(不能触及原始的一个),并以某种方式执行比std :: sort更快的排序(它需要太长时间才能对它进行排序).

编辑:

对不起大家.我的意思是说我正在创建一个std :: map,其中键是long,值是int.long值是struct的键值,int是向量中相应元素的索引.

此外,我做了一些调试,并意识到矢量根本没有排序.这完全是随机的.所以做一些像stable_sort这样的东西是行不通的.

另一个更新:

谢谢大家的回复.我最终创建了一个对的向量(std :: vector of std :: pair(long,int)).然后我按长值对矢量进行排序.我创建了一个自定义比较器,仅查看该对的第一部分.然后我使用lower_bound来搜索该对.这就是我做到这一切的方式:

  typedef std::pair<long,int> Key2VectorIndexPairT;
  typedef std::vector<Key2VectorIndexPairT> Key2VectorIndexPairVectorT;

  bool Key2VectorIndexPairComparator(const Key2VectorIndexPairT& pair1, const Key2VectorIndexPairT& pair2)
  {
      return pair1.first < pair2.first;
  }

  ...

  Key2VectorIndexPairVectorT sortedVector;
  sortedVector.reserve(originalVector.capacity());

  // Assume "original" vector contains unsorted elements.
  for (int i = 0; i < originalVector.size(); ++i)
  {
      const TheStruct& theStruct = originalVector[i];
      sortedVector.insert(Key2VectorIndexPairT(theStruct.key, i));
  }

  std::sort(sortedVector.begin(), sortedVector.end(), Key2VectorIndexPairComparator);

  ...

  const long keyToSearchFor = 20;

  const Key2VectorIndexPairVectorT::const_iterator cItorKey2VectorIndexPairVector = std::lower_bound(sortedVector.begin(), sortedVector.end(), Key2VectorIndexPairT(keyToSearchFor, 0 /* Provide dummy index value for search */), Key2VectorIndexPairComparator);

  if (cItorKey2VectorIndexPairVector->first == keyToSearchFor)
  {
      const int vectorIndex = cItorKey2VectorIndexPairVector->second;
      const TheStruct& theStruct = originalVector[vectorIndex];

      // Now do whatever you want...
  }
  else
  {
      // Could not find element...
  }

这为我带来了适度的性能提升.在我计算的总时间为3.75毫秒之前,现在它下降到2.5毫秒.

Answer 1

std :: map和std :: set都是在二叉树上构建的,因此添加项会进行动态内存分配.如果您的地图基本上是静态的(即在开始时初始化一次,然后很少或从未添加或删除新项目),您可能最好使用排序向量和std :: lower_bound来使用二进制搜索查找项目.