检查到目前为止我在C++中使用了哪些值的最快方法是什么？

Question

一个片段

if (a<=lim){
    if(std::find(prims.begin(), prims.end(), a)==prims.end()){
        prims.push_back(a);
        count+=lim/a;
    }         
}

所以基本上我在我的代码中有这个部分,如果它不存在,我将变量添加a到此vector,然后我即时更新计数器.

但我想知道这在运行时是否不是最理想的.我能做得更快吗？

Answer 1

std::set如果您只想保留唯一值,则通常使用的容器.值在内部存储为红黑树,因此大多数操作具有对数复杂度.

这将比您的实现更快,并且与建议的二进制搜索实现一样快.

您可以通过使用新的(c ++ 11)进一步改进它std::unordered_set,它将其存储为哈希表,这将使其在平均恒定时间操作中更快.

使用set方法如下

std::set<TYPE> prims;
....
if (a<=lim){
    if(prims.insert(a).second){
        count+=lim/a;
    }         
}

其中TYPE是存储在向量中的值的类型