An sample code to benchmark searching performance.

searching_benchmark.cpp

#include <vector>
#include <set>
#include <unordered_set>
#include <cassert>
#include <iostream>

using namespace std;

static const int tries = 10000000;
uint64_t rand64() { return (((uint64_t)rand())<<32) | (uint64_t)rand(); }

void test_vector(int n)
{
  vector<uint64_t> c;
  vector<uint64_t> key;
  // Initialization
  for (int i=0; i<n; i++){
    uint64_t x = rand64();
    c.push_back(x);
    key.push_back(x);
  }
  size_t cnt = 0;
  for (int j=0; j<tries; j++){
    auto target = key[rand()%key.size()];
    // Linear search
    for (int k=0; k<c.size(); k++){
      if (c[k] == target){
        ++cnt;
        break;
      }
    }
  }
  assert(cnt==tries);
}

void test_set(int n)
{
  set<uint64_t> c;
  vector<uint64_t> key;
  // Initialization
  for (int i=0; i<n; i++){
    uint64_t x = rand64();
    c.insert(x);
    key.push_back(x);
  }

  size_t cnt = 0;
  for (int j=0; j<tries; j++){
    auto target = key[rand()%key.size()];
    if (c.end() != c.find(target))
      ++cnt;
  }
  assert(cnt==tries);
}

void test_unordered_set(int n)
{
  unordered_set<uint64_t> c;
  vector<uint64_t> key;
  // Initialization
  for (int i=0; i<n; i++){
    uint64_t x = rand64();
    c.insert(x);
    key.push_back(x);
  }

  size_t cnt = 0;
  for (int j=0; j<tries; j++){
    auto target = key[rand()%key.size()];
    bool found = false;
    if (c.end() != c.find(target))
      ++cnt;
  }
  assert(cnt==tries);
}

int main(int argc, char* argv[])
{
#ifdef VECTOR_VERSION
  test_vector(atoi(argv[1]));
#endif
#ifdef SET_VERSION
  test_set(atoi(argv[1]));
#endif
#ifdef HASH_VERSION
  test_unordered_set(atoi(argv[1]));
#endif
  return 0;
}