Why is lookup in stl::map slower than in stl::vector in my Application?

Question

I am kind of startled, especially after reading this.

I use

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

and

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

as template functions to get the index of a specific element in my vector respectivly list.

Elements are unique pointers to objects, of which i want to retrieve the index off.

I then use this template in a for-loop like

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

While all bits of information i gathered suggested to use a map, the map implementation is several orders of magnitude slower: 57 ms using the vector variant in comparision 70000ms using the map.

Something is severly borked here, but i do not know what. Do you?

Development plattform is MS VS 2008 Standard sp1, on windows XP

Answer 1

Note, as your code is written here, you are passing both the vector and the map by value, i.e., you are rebuilding new copies of each on every call. That's clearly overwhelming the time of the search.

try:

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

Answer 2

Since you are passing them by value, you are coping the vector and map in every call you are making. I'd sat that this makes the results pretty much meaningless.

Pass them as reference or const reference and run the test again.

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 3

Aside from using references to avoid copies as the other answers mention, there's also a difference in algorithmic complexity here.

Look-up in (non-sorted) vector of size n has O(n) time complexity, whereas the same operation on the map has O(log n) time complexity.

Simply explained, it means that looking up an object in your vector takes time K1*n while it takes K2*log(n) time for the map, where K1 and K2 are some constants that depend on the implementation of the vector and map.

Which is faster in practice depends on the size of your container and what the constants are (I think it's safe to say K1will be faster.

Things like cache coherence will also come into play here, if your container is small everything will be in the cache for the vector but not for map. (With a cache, the constants won't really be constant either, but that's another story...)