std::vector faster than std::unordered_set?

Question

In my custom physics engine, the biggest bottleneck is a method that gets all bodies from the spatial partitioning (a 2D grid), and returns a collection containing only unique pointers to body.

template<typename T, typename V> bool contains(const T& mContainer, const V& mValue)
{
    return std::find(std::begin(mContainer), 
                     std::end(mContainer), mValue) != std::end(mContainer);
}

const vector<Body*>& GridInfo::getBodiesToCheck()
{
    bodiesToCheck.clear();
    for(auto& query : queries)
        for(auto& body : *query)
            if(!contains(bodiesToCheck, body)) bodiesToCheck.push_back(body);
    return bodiesToCheck;
}

Using a profiler shows that the bottleneck is in the "contains" method.

Obviously, an std::unordered_set would be the "ideal" solution here. However, it is a lot slower than the current solution. I've also tried google::dense_hash_set, which is faster than std::unordered_set, but still slower than the current solution.

const unordered_set<Body*>& GridInfo::getBodiesToCheck()
{
    bodiesToCheck.clear();
    for(auto& query : queries)
        for(auto& body : *query)
            /*if(!contains(bodiesToCheck, body))*/ bodiesToCheck.insert(body);
    return bodiesToCheck;
}

Why are the "correct" containers slower than a std::vector?

Is there any way I can speed up this method further?

Answer 1

There are two possibilities I can think of:

1. You have a small enough number of data elements that a linear search is faster than a hash-plus compare lookup.
2. You're using the same contains function to find an element in the unordered_set, instead of using the member function find.