#include <algorithm>
#include <iterator>
#include <vector>

template<class iterator> auto structure_dereference_operator(const iterator& r) -> typename std::iterator_traits<iterator>::pointer {return r.operator->();}
template<class type> typename std::iterator_traits<type*>::pointer structure_dereference_operator(const type*& r) {return r;}

template <class key_, 
          class mapped_, 
          class traits_ = std::less<key_>,
		  class undertype_ = std::vector<std::pair<key_,mapped_> >
         >
class associative
{
public:
	typedef traits_ key_compare;
	typedef key_ key_type;
	typedef mapped_ mapped_type;
	typedef std::pair<const key_type, mapped_type> value_type;
	typedef typename undertype_::allocator_type allocator_type;
	typedef typename allocator_type::template rebind<value_type>::other value_allocator_type;
	typedef typename undertype_::const_iterator const_iterator;

	class value_compare {
		key_compare pred_;
	public:
		inline value_compare(key_compare pred=key_compare()) : pred_(pred) {}
		inline bool operator()(const value_type& left, const value_type& right) const {return pred_(left.first,right.first);}
		inline bool operator()(const value_type& left, const key_type& right) const {return pred_(left.first,right);}
		inline bool operator()(const key_type& left, const value_type& right) const {return pred_(left,right.first);}
		inline bool operator()(const key_type& left, const key_type& right) const {return pred_(left,right);}
		inline key_compare key_comp( ) const {return pred_;}
	};
	class iterator  {
	public:       
		typedef typename value_allocator_type::difference_type difference_type;
		typedef typename value_allocator_type::value_type value_type;
		typedef typename value_allocator_type::reference reference;
		typedef typename value_allocator_type::pointer pointer;
		typedef std::bidirectional_iterator_tag iterator_category;
		inline iterator(const typename undertype_::iterator& rhs) : data(rhs) {}
		inline pointer operator->() const {return reinterpret_cast<pointer>(structure_dereference_operator(data));}
		operator const_iterator&() const {return data;}
	protected:
		typename undertype_::iterator data;
	};

    template<class input_iterator>
    inline associative(input_iterator first, input_iterator last) : internal_(first, last), comp_() 
	{if (std::is_sorted(internal_.begin(), internal_.end())==false) std::sort(internal_.begin(), internal_.end(), comp_);}

	inline iterator find(const key_type& key) {return std::lower_bound(internal_.begin(), internal_.end(), key, comp_);}
    inline const_iterator find(const key_type& key) const {return std::lower_bound(internal_.begin(), internal_.end(), key, comp_);}

protected:
	undertype_ internal_;
	value_compare comp_;
};

#include <cstdlib>
#include <ctime>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>

#ifdef _DEBUG
#define WARMUP_TIME_MILLISECONDS 1
#define TEST_TIME_MILLISECONDS 9
#else
#define WARMUP_TIME_MILLISECONDS 10
#define TEST_TIME_MILLISECONDS 400
#endif

template<unsigned int size>
struct payload {
	int data[size/4];
	payload() {data[0]=rand()*RAND_MAX+rand();}
	bool operator==(const payload& rhs) const {return data[0]==rhs.data[0];}
	bool operator<(const payload& rhs) const {return data[0]<rhs.data[0];}
};

template<class load, class container>
void test_internal(const std::vector<std::pair<load, load>>& data, const char* classname, const char* payloadname) {
	clock_t beg,end,elapsed,freq;
	unsigned int count=0;
	bool timed=false;
	freq = CLOCKS_PER_SEC;

	std::vector<std::pair<load, load>> shuffled(data.begin(), data.end());
	std::random_shuffle(shuffled.begin(), shuffled.end());
	std::vector<std::pair<load, load>> sorted(data.begin(), data.end());
	std::sort(sorted.begin(), sorted.end());
	
	std::cout << payloadname << ' ' << std::setw(4) << data.size() << ' ' << classname << ' ';
	timed = false;
	elapsed = 0;
	{
	    container a(data.begin(), data.end());
		do {
			beg = clock();
			auto i=a.find(shuffled[count%data.size()].first);
			end = clock();
			elapsed += end-beg;
   			if (elapsed>WARMUP_TIME_MILLISECONDS && !timed) {
				elapsed =0;
				count=0;
				timed = true;
			}
			++count;
		} while(elapsed<TEST_TIME_MILLISECONDS);
	}
	std::cout << std::setw(9) << count << '\n';
}

template<class load>
void test(const std::vector<std::pair<load, load>> &data, const char* payload_name) {
	std::vector<std::pair<load, load>> use(data.begin(), data.begin()+8);
	for( ; ; ) {
		test_internal<load, std::map   <load,load>>(use, "std::map", payload_name);
		test_internal<load, associative<load,load,std::less<load>,std::vector<std::pair<load,load>>>>(use, "astv/vec", payload_name);
		if (use.size()<1024)
			use.insert(use.end(), data.begin()+use.size()*1ull, data.begin()+use.size()*2ull);
		else if (use.size() != data.size())
			use.insert(use.end(), data.begin()+use.size(), data.end());
		else break;
	}
}

int main() {
	test(std::vector<std::pair<payload<  4>,payload<  4>>>(2000), "payload<  4>");
	test(std::vector<std::pair<payload<  8>,payload<  8>>>(2000), "payload<  8>");
	test(std::vector<std::pair<payload< 16>,payload< 16>>>(2000), "payload< 16>");
	test(std::vector<std::pair<payload< 32>,payload< 32>>>(2000), "payload< 32>");
	test(std::vector<std::pair<payload< 64>,payload< 64>>>(2000), "payload< 64>");
	test(std::vector<std::pair<payload<128>,payload<128>>>(2000), "payload<128>");

	return 0;
}