为什么在我的应用程序中，stl::map 中的查找比 stl::vector 中的查找慢？

Question

我有点震惊，尤其是在阅读这个之后。

我使用

template <class T>
int GetPosition(vector<T> mVec, T element)
{
    return find(mVec.begin(), mVec.end(), element) - mVec.begin();
}

和

template <class T>
int GetPosition(map<T, int> mMap, T element)
{
    return mMap.find(element)->second;
}

作为模板函数来获取向量列表中特定元素的索引。

元素是指向对象的唯一指针，我想检索其中的索引。

然后，我在 for 循环中使用此模板，例如

for(int i = 0; i < myCount; i++)
{
  index = GetPosition(myVector, elements[i]) //or GetPosition(myMap, elements[i])
}

虽然我收集的所有信息都建议使用地图，但地图实现速度慢了几个数量级：使用矢量变体 57 毫秒，相比之下使用地图 70000 毫秒。

这里有些东西严重堵塞，但我不知道是什么。你？

开发平台为MS VS 2008 Standard sp1，Windows XP

Answer 1

由于您是按值传递它们，因此您在每次调用时都会处理 vector 和 map 。我认为这使得结果毫无意义。

将它们作为引用或 const 引用传递，然后再次运行测试。

template <class T>
int GetPosition(const vector<T>& mVec, T element)
{
    return find(mVec.begin(), mVec.end(), element) - mVec.begin();
}

template <class T>
int GetPosition(const map<T, int>& mMap, T element)
{
    return mMap.find(element)->second;
}

Answer 2

请注意，当您的代码写在这里时，您将按值传递向量和映射，即，您将在每次调用时重建每个向量和映射的新副本。这显然压垮了搜索时间。

尝试：

template <class T> 
int GetPosition(const map<T, int> &mMap, T element) 

Answer 3

除了像其他答案提到的那样使用引用来避免复制之外，这里的算法复杂性也存在差异。

在大小为 n 的（未排序）向量中查找的时间复杂度为 O(n)，而在映射上执行相同操作的时间复杂度为 O(log n)。

简单解释一下，这意味着在向量中查找对象需要时间 K1*n，而在映射中查找对象需要 K2*log(n) 时间，其中 K1 和 K2 是一些取决于向量和映射实现的常量。

在实践中哪个更快取决于您的容器的大小和常量是什么（我认为可以肯定地说 K1 会更快。

缓存一致性之类的东西也会在这里发挥作用，如果您的容器很小，所有内容都将在缓存中对于向量而不是地图（使用缓存，常量也不会真正保持不变，但那是另一个故事了......）