/** Пример #0: скорость */
// STL: set, map, list -- ссылочные структуры, постоянно вызывают operator new
// Чтобы new работал быстрее, используем
#define FAST_ALLOCATOR_MEMORY 1e8
#include "optimization.h"

#include <map>
#include <unordered_map>
#include <set>
#include <string>
#include <vector>
#include <queue>

using namespace std;

int main() {

	/** Пример #1 */
	map<string, vector<int>> m1; // для каждой строки храним вектор
	m1["abc"].push_back(0);
	vector<int> &a1 = m1["abc"]; // запомнили ссылку, чтобы каждый раз не обращаться к map
	auto &b1 = m1["abc"]; // автовывод типа, запомнили ссылку, чтобы каждый раз не обращаться к map

	/** Пример #2 */
	map<vector<int>, pair<set<int>, vector<int>>> m2; // для каждого вектора храним пару <set, vector>
	m2[vector<int>(3, 1)].first.insert(3);
	pair<set<int>, vector<int>> &a2 = m2[vector<int>(3, 1)]; // запомнили ссылку, чтобы каждый раз не обращаться к map
	auto &b2 = m2[vector<int>(3, 1)]; // автовывод типа, запомнили ссылку, чтобы каждый раз не обращаться к map

	/** Пример #3: кучи */
	priority_queue<int> q1; // куча, в корне максимум
	priority_queue<int, vector<int>, greater<int>> q2; // куча, в корне минимум

	/** Пример #4: удаление из кучи */
	// Хотите удалять?
	// а) можно хранить set<int>, как кучу
	// б) можно хранить две кучи -- добавленные элементы и удалённые элементы
	priority_queue<int> q_add, q_del; 

	/** Пример #5: хеш-таблица */
	const int n = 1e6;
	unordered_map<int, vector<int>> table(n); // хеш-таблица, выделили заранее n ячеек, что важно для скорости
	table[10] = {2, 3, 4};

	// unordered_map работает за O(1), map и set за O(log n)
}