c++ - 检查到目前为止我在 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 是存储在向量中的值的类型

Answer 2

您可以使用 astd::unordered_set检查重复项，从而为您提供O(1) 摊销查找。

如果您知道 的最大大小a并且它相当小，您可以使用bool数组来存储是否元素x并且您将进行真正的O(n)查找。

Answer 3

您想使用其他具有内置唯一性的 STL 容器，例如set或map；http://www.cplusplus.com/reference/map/map/。例如，由地图建模的哈希表适合您的用例。

<map>
using namespace std;

int insert_and_update(int key_val,map<int,int> hash_map) {
map<int,int>::iterator it;
it = hash_map.find(key_val);
  if( it != hash_map::end() ) {
     it->second += 1; //contains the associated value.
     return 1;
  }
 hash_map(key_val) = 1; //else insert new key into map
 return 0;      
}