1

我有点吃惊,尤其是在读完这篇文章之后。

我用

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 上

4

3 回答 3

3

请注意,由于您的代码是在此处编写的,因此您正在通过值传递向量和映射,即,您在每次调用时都重建每个的新副本。这显然超出了搜索的时间。

尝试:

template <class T> 
int GetPosition(const map<T, int> &mMap, T element) 
于 2010-07-07T13:47:09.917 回答
3

由于您是按值传递它们,因此您在每次调用时都要处理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;
}
于 2010-07-07T13:47:53.230 回答
1

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

在大小为 n 的(未排序的)向量中查找具有 O(n) 时间复杂度,而在地图上的相同操作具有 O(log n) 时间复杂度。

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

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

缓存一致性之类的东西也会在这里发挥作用,如果你的容器很小,所有东西都将在缓存中用于向量,但不会用于地图。(使用缓存,常量也不会真正保持不变,但这是另一回事......)

于 2010-07-07T23:13:50.217 回答