#include <ctime>
#include <algorithm>
#include <limits>
#include <map>
#include <iostream>
#include <string>

using namespace std;

inline int rand_int(int max) { return rand() % max; }

inline int rand_int(int min, int max) { return rand_int(max - min) + min; }

string rand_string()
{
	const int iterations = rand_int(100);
	string result;
	result.reserve(iterations);
	for(size_t i = 0; i < result.size(); ++i)
	{
		result[i] = char(rand_int(int(numeric_limits<char>::min()),
				          int(numeric_limits<char>::max())));
	}
	return result;
}

int main()
{
	clock_t start_m1 = clock();
	map<int, string> m1;
	for(int i = 0; i < 500000; ++i)
	{
		m1.insert(m1.end(), pair<int, string>(i, rand_string()));
		// map orders its elements according to the Key
		// The Key here is int
		// The for-loop generates sorted ints
		// hence the Keys are already sorted
	}
	clock_t stop_m1 = clock();
	cout << "The time it took to build map<int, string> is "
		<< double(stop_m1 - start_m1) / CLOCKS_PER_SEC << " seconds" << '\n';

	clock_t start_m2 = clock();
	map<string, int> m2;
	for(int i = 0; i < 500000; ++i)
	{
		m2[rand_string()] = i;
		// The Key here is string
		// Randoms strings are generated that are not sorted
		// So to build the map in a sorted order,
		// bool operator<(const string& _Left, const string& _Right)
		// has to be called a lot of times
		// to insert the elements in a sorted order
		// So many calls to that function means that
		// building m2 should take a longer time than m1
		// also considering that the Keys of m1 are already sorted
	}
	clock_t stop_m2 = clock();
	cout << "The time it took to build map<string, int> is "
		<< double(stop_m2 - start_m2) / CLOCKS_PER_SEC << " seconds" << '\n';

	cout << "Please enter a character to exit:" << "\n";
	char ch = 0;
	cin >> ch;

	return 0;
}