#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <random>
#include <chrono>

#include <tsl/robin_map.h>

/*
using KeyT = int;
using ValueT = std::string;

KeyT MakeKey(int i) {
    return i;
}

ValueT MakeValue(int i) {
    return "Value_" + std::to_string(i);
}
*/

using KeyT = std::string;
using ValueT = int;

KeyT MakeKey(int i) {
    return "Value_" + std::to_string(i);
}

ValueT MakeValue(int i) {
    return i;
}

std::vector< std::pair<KeyT, ValueT> > CreateData(int count) {
    std::vector< std::pair<KeyT, ValueT> > data;
    data.reserve(count);
    for (int i = 0; i < count; ++i) {
        data.emplace_back(MakeKey(i), MakeValue(i));
    }
    return data;
}

template<typename HashMap>
void InsertTest(HashMap& mymap,const std::vector< std::pair<KeyT, ValueT> >& data) {
    for (size_t i = 0; i < data.size(); ++i) {
        mymap.insert({ data[i].first,data[i].second });
    }
}

template<typename HashMap>
int FindTest(const HashMap& mymap, const std::vector< std::pair<KeyT, ValueT> >& data) {
    int results_count = 0;
    for (size_t i = 0; i < data.size(); ++i) {
        auto itr = mymap.find(data[i].first);
        if (itr != mymap.end()) {
            ++results_count;
        }
    }
    return results_count;
}

struct test_times {
    std::chrono::microseconds insert_time;
    std::chrono::microseconds find_time;
};

template<typename HashMap>
test_times test(
    const std::vector< std::pair<KeyT, ValueT> > inserts,
    const std::vector< std::pair<KeyT, ValueT> > finds,
    HashMap& mymap) {

    test_times result;

    std::chrono::steady_clock::time_point start,end;
    ///////////////////////////////////////////////////////////////
    {
        // データを保存する時間の計測
        start = std::chrono::high_resolution_clock::now();
        mymap.reserve(inserts.size());
        InsertTest(mymap, inserts);
        end = std::chrono::high_resolution_clock::now();
        result.insert_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    }
    ///////////////////////////////////////////////////////////////
    {
        // データを検索する時間の計測
        start = std::chrono::high_resolution_clock::now();
        volatile int ret = FindTest(mymap, finds);
        end = std::chrono::high_resolution_clock::now();
        result.find_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    }
    ///////////////////////////////////////////////////////////////

    return result;
}