标准容器中 std::find() 的计时

Question

我正在尝试std::find()为std::unordered_set、std::set、 和计时该函数std::vector。但结果对我来说很奇怪。

unordered_set在an 中查找元素比在 a 中查找元素需要更多时间vector。

理论上，搜索的时间复杂度应该为O(1)forunordered_set和O(n)for vector。

那么，在 an 中查找元素应该unordered_set比更快吗vector？我做错什么了吗？

这是我的代码：

#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <random>
#include <numeric>
#include <chrono>

using namespace std;

int main(int argc, char** argv)
{
  int size = 10000;
  vector<int> items(size);
  iota(items.begin(), items.end(), 0);
  auto rng = default_random_engine {};
  shuffle(items.begin(), items.end(), rng);
  
  chrono::steady_clock::time_point begin, end;  
  unordered_set<int> unsetInt;
  set<int> setInt;
  vector<int> vecInt;

  // add element
  for(auto it = items.begin(); it != items.end(); it++)
  {
    unsetInt.insert(*it);
    setInt.insert(*it);
    vecInt.push_back(*it);
  }
  
  // lookup time for unordered_set<int>
  begin = chrono::steady_clock::now();
  for(int i = 0; i < size; i++)
  {
    find(unsetInt.begin(), unsetInt.end(), i);
  }
  end = chrono::steady_clock::now();
  cout << "lookup time for unordered_set<int>: " << 
  chrono::duration_cast<chrono::milliseconds>(end-begin).count() << "ms" << endl;
  
  // lookup time for set<int>
  begin = chrono::steady_clock::now();
  for(int i = 0; i < size; i++)
  {
    find(setInt.begin(), setInt.end(), i);
  }
  end = chrono::steady_clock::now();
  cout << "lookup time for set<int>: " << 
  chrono::duration_cast<chrono::milliseconds>(end-begin).count() << "ms" << endl;
  
  // lookup time for vector<int>
  begin = chrono::steady_clock::now();
  for(int i = 0; i < size; i++)
  {
    find(vecInt.begin(), vecInt.end(), i);
  }
  end = chrono::steady_clock::now();
  cout << "lookup time for vector<int>: " << 
  chrono::duration_cast<chrono::milliseconds>(end-begin).count() << "ms" << endl;

  return 0;
}

这是我的结果：

lookup time for unordered_set<int>: 2293ms
lookup time for set<int>: 3080ms
lookup time for vector<int>: 1311ms

Answer 1

我做错什么了吗？

你做到了。

std::find通过迭代所有元素来执行搜索。它没有任何关于std::[unordered_]set其他容器的特殊知识。

为了正确地在集合中搜索，您需要使用它自己的.find()成员函数。