std :: vector比std :: unordered_set更快？

Question

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

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。