---

#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <chrono>
#include <utility>
#include <algorithm>
#include <random>

using namespace std;

// Заполнение вспомогательного вектора случайными числами
void generate_random_data(vector<int>& arr)
{	
	mt19937 gen(12);
	uniform_int_distribution<int> distrib(1, 1000000);
	for (int i = 0; i < arr.size(); i++) {
		arr[i] = distrib(gen);
	}
	return;
	// создание генератора случайных чисел с фиксированным seed
	// создание равномерного случайного распределения от 1 до 1000000
	// заполнение массива числами из этого распределения
}

// 1. Сравнение push_back
pair<double, double> test_push_back(const vector<int>& data)
{
	vector<int> v;
	auto start_vec = chrono::high_resolution_clock::now();
	//создание первой временной отметки - текущее время создание вектора
	//в цикле по data заполнять созданный массив элементами из data с помощью push_back
	for (int i = 0; i < data.size(); i++) {
		v.push_back(data[i]);
	}
	auto end_vec = chrono::high_resolution_clock::now(); // создание второй временной отметки
	double time_vec = chrono::duration_cast<chrono::microseconds>(end_vec - start_vec).count(); // разница между отметками в микросекундах (1 микросекунда = 10^(-6) секунд)
	list<int> lst;
	auto start_list = chrono::high_resolution_clock::now(); 
	//создание первой временной отметки создание списка в цикле по data заполнять созданный список элементами из data с помощью push_back
	for (int i = 0; i < data.size(); i++) {
		lst.push_back(data[i]);
	}
	auto end_list = chrono::high_resolution_clock::now(); //создание второй временной отметки
	double time_list = chrono::duration_cast<chrono::microseconds>(end_list - start_list).count(); // разница между отметками в микросекундах
	return { time_vec, time_list }; // возвращает пару - время выполнения для вектора и списка
}

// 2. Сравнение push_front
pair<double, double> test_push_front(const vector<int>& data)
{
	vector<int> v;
	auto start_vec = chrono::high_resolution_clock::now();
	// создание первой временной отметки создание вектора в цикле по data заполнять созданный массив элементами из data с помощью insert(в начало)
	for (int i = 0; i < data.size(); i++) {
		v.insert(v.begin(), data[i]);
	}
	// создание второй временной отметки
	auto end_vec = chrono::high_resolution_clock::now();
	// подсчет разницы между отметками в микросекундах для вектора
	double time_vec = chrono::duration_cast<chrono::microseconds>(end_vec - start_vec).count();
	list<int> lst;
	auto start_list = chrono::high_resolution_clock::now(); 
	// создание первой временной отметки создание списка в цикле по data заполнять созданный список элементами из data с помощью push_front
	for (int i = 0; i < data.size(); i++) {
		lst.push_front(data[i]);
	}
	auto end_list = chrono::high_resolution_clock::now();
	double time_list = chrono::duration_cast<chrono::microseconds>(end_list - start_list).count();
	return { time_vec, time_list };
}

// 3. Сравнение последовательного обхода (итерации)
pair<double, double> test_iteration(const vector<int>& data)
{
	list<int> lst;
	vector<int> v;
	for (int i = 0; i < data.size(); i++) {
		v.push_back(data[i]);
		lst.push_back(data[i]);
	}
	// подсчет суммы:
	volatile long long sum_vec = 0; // volatile защищает от оптимизации вырезания цикла
	// создание первой временной отметки
	auto start_vec = chrono::high_resolution_clock::now();
	for (int i = 0; i < v.size(); i++) {
		sum_vec += v[i];
	}
	// цикл по вектору для накапливания суммы в sum_vec
	// создание второй временной отметки
	auto end_vec = chrono::high_resolution_clock::now();
	// подсчет разницы между отметками в микросекундах для вектора
	double time_vec = chrono::duration_cast<chrono::microseconds>(end_vec - start_vec).count();
	// Тест для std::list
	volatile long long sum_list = 0;
	// создание первой временной отметки
	auto start_list = chrono::high_resolution_clock::now();
	// цикл по списку для накапливания суммы в sum_list
	for (auto it = lst.begin(); it != lst.end(); ++it) {
		sum_list += *it;
	}
	// создание второй временной отметки
	// подсчет разницы между отметками в микросекундах для списка
	auto end_list = chrono::high_resolution_clock::now();
	double time_list = chrono::duration_cast<chrono::microseconds>(end_list - start_list).count();
	// вернуть пару - время выполнения для вектора и списка:
	return { time_vec, time_list };
}
// 4. Сравнение сортировки
pair<double, double> test_sorting(const vector<int>& data)
{
	list<int> lst;
	vector<int> v;
	for (int i = 0; i < data.size(); i++) {
		v.push_back(data[i]);
		lst.push_back(data[i]);
	}
	// создание первой временной отметки
	auto start_vec = chrono::high_resolution_clock::now();
	// сортировка вектора встроенной функцией std::sort(итератор начала, итератор конца)
	sort(v.begin(), v.end());
	// создание второй временной отметки
	// подсчет разницы между отметками в микросекундах для вектора
	auto end_vec = chrono::high_resolution_clock::now();
	double time_vec = chrono::duration_cast<chrono::microseconds>(end_vec - start_vec).count();
	// создание первой временной отметки
	auto start_list = chrono::high_resolution_clock::now();
	// сортировка списка встроенной функцией list.sort()
	lst.sort();
	// создание второй временной отметки
	// подсчет разницы между отметками в микросекундах для списка
	auto end_list = chrono::high_resolution_clock::now();
	double time_list = chrono::duration_cast<chrono::microseconds>(end_list - start_list).count();
	// вернуть пару - время выполнения для вектора и списка:
	return { time_vec, time_list };
}

// Функция записи результатов в файл
void add_to_file(const vector<double>& res, int n, ofstream& file)
{
	file << n << ";";
	for (size_t k = 0; k < res.size(); k++)
		file << int(res[k]) << ";"; // Запись в микросекундах
	file << "\n";
}

int main()
{
	// Сколько раз прогонять тест на каждом размере для усреднения случайных всплесков процессора
	const int TEST_RUNS = 10;
	pair<double, double> a;

	// Файл 1: операции вставки в конец и обхода последовательности:
	ofstream file_fast("push_back_and_iteration.csv"); // создание потока для записи в файл
	file_fast << "size;vector_push_back;list_push_back;vector_iteration;list_iteration\n"; // создание первой строки в файле

	for (int size = 10000; size <= 200000; size += 10000) // цикл по размерам последовательностей
	{
		vector<int> data(size); // создание вспомогательного вектора для хранения последовательности
		// заполнение последовательности случайными значениями

		double avg_v_pb = 0, avg_l_pb = 0; // avg_v_pb - время операции добавление в конец для вектора, avg_l_pb - для списка
		double avg_v_it = 0, avg_l_it = 0; // avg_v_it - время обхода элементов последовательности для вектора, avg_l_it - для списка

		for (int t = 0; t < TEST_RUNS; ++t) { // Повтор одинаковых операций на одних и тех же данных для усреднения случайных всплесков процессора
			// сравнение времени выполнения операции добавления в конец
			// накопление результатов в счетчиках avg_v_pb и avg_l_pb
			// сравнение времени выполнения операции обхода элементов последовательности
			// накопление результатов в счетчиках avg_v_it и avg_l_it
			a = test_push_back(data);
			avg_v_pb += a.first; avg_l_pb += a.second;
			a = test_iteration(data);
			avg_v_it += a.first; avg_l_it += a.second;
		}
		add_to_file({ avg_v_pb / TEST_RUNS, avg_l_pb / TEST_RUNS, avg_v_it / TEST_RUNS, avg_l_it / TEST_RUNS }, size, file_fast);
	}
	file_fast.close();

	// Файл 2: операции вставки в начало :
	ofstream file_front("push_front.csv");
	file_front << "size;vector_push_front;list_push_front\n";

	for (int size = 2000; size <= 30000; size += 2000)
	{
		// создание вспомогательного вектора для хранения последовательности
		vector<int> data(size);
		generate_random_data(data);
		// заполнение последовательности случайными значениями
		double avg_v_pf = 0, avg_l_pf = 0; // avg_v_pf - время выполнения операции добавления в начало для вектора, avg_l_pf - для списка
		for (int t = 0; t < TEST_RUNS; ++t) {
			a = test_push_front(data);
			// сравнение времени выполнения операции добавления в начало
			avg_v_pf += a.first; avg_l_pf += a.second;
			// накопление результатов в счетчиках avg_v_pf и avg_l_pf
		}
		add_to_file({ avg_v_pf / TEST_RUNS, avg_l_pf / TEST_RUNS }, size, file_front);
	}
	file_front.close();

	//Файл 3: операции сортировки :
	ofstream file_sort("sorting.csv");
	file_sort << "size;vector_sort;list_sort\n";

	for (int size = 5000; size <= 50000; size += 5000)
	{
		vector<int> data(size);
		generate_random_data(data);
		double avg_v_sort = 0, avg_l_sort = 0; // avg_v_sort - время выполнения сортировки вектора, avg_l_sort - списка
		for (int t = 0; t < TEST_RUNS; ++t) {
			// сравнение времени сортировки
			a = test_sorting(data);
			// накопление результатов в счетчиках avg_v_sort и avg_l_sort
			avg_v_sort += a.first; avg_l_sort += a.second;
		}
		add_to_file({ avg_v_sort / TEST_RUNS, avg_l_sort / TEST_RUNS }, size, file_sort);
	}
	file_sort.close();

	return 0;
}