代码之家 › 专栏 › 技术社区 › sum1stolemyname

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

visual-c++-2008 stl performance

1

sum1stolemyname · 技术社区 · 14 年前

我有点吃惊,尤其是在读完之后 this

我用

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(int i = 0; i < myCount; i++)
{
  index = GetPosition(myVector, elements[i]) //or GetPosition(myMap, elements[i])
}

虽然我收集的所有信息都建议使用地图,但地图的实现要慢几个数量级: 57 ms使用矢量变量进行比较70000 ms使用地图。

这里有些东西严重损坏,但我不知道是什么。你…吗?

开发平台是WindowsXP上的MS VS2008标准sp1

3 回复 | 直到 7 年前

1

3

shoosh 14 年前

vector 和 map

将它们作为引用或常量引用传递,然后再次运行测试。

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;
}

2

3

James Curran 14 年前

注意,在这里编写代码时,您将按值传递向量和映射,也就是说,您将在每次调用时重建每个映射的新副本。这显然是压倒性的搜索时间。

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

3

1

Staffan 14 年前

除了像其他答案提到的那样使用引用来避免复制之外,这里的算法复杂性也有所不同。

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

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

像缓存一致性这样的东西也会在这里发挥作用,如果你的容器很小,所有的东西都会在缓存中,用于向量,而不是地图(有了缓存,常量也不会是常量,但那是另一回事……)