#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;
}