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.

Answer 2

If the number of duplicate bodies isn't that high compared to the others, one option might be to just push all your bodies into the vector and remove the duplicates afterwards. But this will require a std::sort followed by an erase(std::unique, end).

But it may be worth a try, considering that your vector seems to outplay a std::unordered_set anyway, which doesn't have the same memory locality and trivial access like a std::vector.