#include <iostream>
#include <vector>
#include <unordered_map>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <map>
typedef unsigned value;
typedef unsigned index;
#ifdef _DEBUG
const index datacount = 10000;
const index lookupcount = 10000;
#else
const index datacount = 10000000;
const index lookupcount = 100000;
#endif
int main() {
std::vector<value> a(datacount); //amount of data
for(index i=0; i<a.size(); ++i)
a[i] = 2*i+rand()%2; //values are unique and ordered, but sparse
std::random_shuffle(a.begin(), a.end()); //shuffle them
std::vector<value> findme(lookupcount); //number of finds to do
for(index i=0; i<findme.size(); ++i) //predecide which need to be found,
findme[i] = a[rand()%a.size()]; //removes so all tests are equal
{
std::cout << "unsorted vector ";
index result = 0;
clock_t begin = clock();
for(index i=0; i<findme.size(); ++i) {
auto iter = std::find(a.begin(), a.end(), findme[i]); //linear find
result += (iter-a.begin()); //add it's index
}
clock_t end = clock();
std::cout << " found " << result << " in " << (end-begin) << " ticks.\n";
}
{
std::cout << "sorted vector ";
index result = 0;
clock_t begin = clock();
std::vector<std::pair<value, index>> sorted(a.size()); //reverse lookup vector
for(index i=0; i<sorted.size(); ++i)
sorted[i] = std::pair<value, index>(a[i], i);
std::sort(sorted.begin(), sorted.end()); //that is sorted
for(index i=0; i<findme.size(); ++i) { //binary search
auto iter = std::lower_bound(sorted.begin(), sorted.end(), std::pair<value, index>(findme[i], 0));
result += iter->second; //add it's index
}
clock_t end = clock();
std::cout << " found " << result << " in " << (end-begin) << " ticks.\n";
}
{
std::cout << "unordered_map ";
index result = 0;
clock_t begin = clock();
std::unordered_map<value, index> lookup(a.size()); //reverse lookup hash
for(index i=0; i<a.size(); ++i)
lookup[a[i]] = i;
for(index i=0; i<findme.size(); ++i) {
result += lookup[findme[i]]; //add it's index
}
clock_t end = clock();
std::cout << " found " << result << " in " << (end-begin) << " ticks.\n";
}
{
std::cout << "std::map ";
index result = 0;
clock_t begin = clock();
std::map<value, index> lookup; //reverse lookup map
for(index i=0; i<a.size(); ++i)
lookup[a[i]] = i;
for(index i=0; i<findme.size(); ++i) {
result += lookup[findme[i]]; //add it's index
}
clock_t end = clock();
std::cout << " found " << result << " in " << (end-begin) << " ticks.\n";
}
return 0;
}