#include "stdio.h"
#include <iostream>
#include <string>
#include <chrono>
#include <vector>
#include <map>
#include <algorithm>
#include <set>

using namespace std::chrono;
using namespace std;


const vector<string> vecorder({ "srb","jgp","wbz","dhk","ofy","vrw","ybw","sdj","tlf","vut"});
bool veccomp(const string &s1, const string &s2) {
	int a = find(vecorder.begin(), vecorder.end(), s1) - vecorder.begin();
	int b = find(vecorder.begin(), vecorder.end(), s2) - vecorder.begin();
	return a < b;
};

vector<string> KeySort(set<string> s, const vector<string>& order){
    vector<string> res;
    for(const auto& it : order){
        auto needle = s.find(it);
        if(needle != s.end()){
            res.emplace_back(move(*needle));
            s.erase(needle);
        }
    }
    for(auto&& it : s) {
        res.emplace_back(move(it));
    }
    return res;
}


map<const string, const int> maporder({ {"srb",1}, {"jgp",2}, {"wbz",3}, {"dhk",4}, {"ofy",5}, {"vrw",6}, {"ybw",7}, {"sdj",8}, {"tlf",9}, {"vut",10}});
bool mapcomp(const string &s1, const string &s2) {
	int a = maporder[s1];
	int b = maporder[s2];
	//maporder.erase(s1);
	return a < b;
};

vector<string> vp ={ "srb","jgp","wbz","dhk","ofy","vrw","ybw","sdj","tlf","vut"};
set<string> keyset ={ "srb","jgp","wbz","dhk","ofy","vrw","ybw","sdj","tlf","vut"};

void sortWithVector() {
	random_shuffle ( vp.begin(), vp.end() );
	sort(vp.begin(), vp.end(), veccomp);
}

void sortWithMap() {
	random_shuffle ( vp.begin(), vp.end() );
	sort(vp.begin(), vp.end(), mapcomp);
}


int main()
{
	high_resolution_clock::time_point t1;
	high_resolution_clock::time_point t2;
	double duration;
	
    /*--------------------------------------*/
    
    t1 = high_resolution_clock::now();
	
	for (int i=0; i < 10000; ++i) sortWithMap();
	
	t2 = high_resolution_clock::now();
    duration = std::chrono::duration_cast<std::chrono::microseconds>( t2 - t1 ).count();
    cout<< "map: " <<duration/1000.0  << "ms" << endl;
	
	/*--------------------------------------*/
    
    t1 = high_resolution_clock::now();
	
	for (int i=0; i < 10000; ++i) {random_shuffle ( vp.begin(), vp.end() ); KeySort(keyset, vecorder);}
	
	t2 = high_resolution_clock::now();
    duration = std::chrono::duration_cast<std::chrono::microseconds>( t2 - t1 ).count();
    cout<< "AtnNn: " <<duration/1000.0  << "ms" << endl;
	
	/*--------------------------------------*/
	
	t1 = high_resolution_clock::now();
	
	for (int i=0; i < 10000; ++i) sortWithVector();
	
	t2 = high_resolution_clock::now();
	duration = std::chrono::duration_cast<std::chrono::microseconds>( t2 - t1 ).count();
	cout << "vector: " << duration/1000.0  << "ms" << endl;

    return 0;
}