c++ - std::vector 比 std::unordered_set 更快？

Question

在我的自定义物理引擎中，最大的瓶颈是从空间分区(二维网格)获取所有物体并返回仅包含指向物体的唯一指针的集合的方法。

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

使用分析器显示瓶颈在“包含”方法中。

显然，std::unordered_set 将是这里的“理想”解决方案。但是，它比当前的解决方案慢很多。我也试过 google::dense_hash_set，它比 std::unordered_set 快，但仍然比当前的解决方案慢。

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

为什么“正确的”容器比 std::vector 慢？

有什么办法可以进一步加快此方法的速度吗？

Answer 1

我能想到的有两种可能:

1. 您的数据元素数量足够少，因此线性搜索比散列加比较查找更快。
2. 您正在使用相同的 contains 函数在 unordered_set 中查找元素，而不是使用成员函数 find。<