#include <algorithm>
#include <numeric>
#include <stack>
#include <queue>
#include <array>
#include <list>
#include <forward_list>
#include <vector>

#include <set>

#include <map>

#include <unordered_map>
#include <unordered_set>

#include <iostream>

using namespace std;


//forward_list односвязный список
struct Node {
    int value;
    Node* next;
    //конструктор по умолчанию. После : - значит,
    //что инициализация проиходит в момент создания переменной
    Node() : value(0), next(nullptr) {
    };

    Node(int value, Node* n) : value(0), next(n) {
    };
};

//двусвязный список //list<>
//Он содержит указатель на предыдущий (и на следующий тоже) элементы
struct Node {
    int value;
    Node* next;
    Node* prev;
    //конструктор по умолчанию. После : - значит,
    //что инициализация проиходит в момент создания переменной
    Node() : value(0), next(nullptr), prev(nullptr) {
    };

    Node(int value, Node* n, Node* p) : value(0), next(n), prev(p) {
    };
};



//stl - standart template library
int main() {
    stack<int> s; //FILO
    s.push(1);
    cout << s.top() << '\n';
    s.pop();
    s.empty(); //возвращает true, усли пустой

    queue<int> q; //FIFO

    q.push(1);
    cout << q.front() << ' ' << q.back() << '\n';
    q.pop();
    cout << q.empty() << '\n';

    forward_list<int> fl;
    fl.push_front(1);
    cout << fl.front() << '\n';
    //вставка элемента за константу
    fl.insert_after(fl.begin(), 10); //так как это односвязный список вставляем после определенного элемента

    //вставка элемента за константу
    list<int> l;
    l.insert(l.begin(), 10); // тут свободно перемещаемся вперед и назад, вставлять значение легче.

    /*
    Node nw;
    Node n1;
    auto o = n1->next;//&n2
    n1->next = nw;
    nw->next = o;

    n1->n2
    o = n2
    n1->nw
    nw->n2
    n1->nw->n2
    */

    array<int, 26> a;
    a.fill(0);

    set<int> se;//красночерное дерево - оно же бинарное дерево поиска, все операции за логорифм, кроме
    //минимум и максимум за константу. Самобалансируется! (родительский элемент меняется - не обязательно самый верхний)

    se.insert(1); //log(n)
    se.find(10); //log(n)
    cout << se.contains(7) << '\n';
    //элементы хранятся отсортированными

    map<int, string> mp; //такое же красночерное дерево, с такими асимптотиками, только каждый элемент хранит еще и значение

    unordered_set<int> st;
    //добавление за o(1) обычно, в худшем случае за o(n)
    //таблица со списками. (каждый элемент - список)

    //разные элементы возвращают одинаковые hash - коллизия
    //метод открытой адресации.

    deque<int> d; //удаление из начала - O(1) //память выделена не одним кусоком, а чанками
    //массивы




    //end() - возвращает указатель" следующий за последним. (итератор - класс, по смыслу - указатель)
    //другими словами begin() - возвращает итератор на начало итд
    //универсальный дает способ обойти любую коллекцию кроме stack, queue
    //random acces = vector, deque - есть операторы ++ -- +const -const. Можем попасть в любой элемент
    //bidirectional list, set, map - есть операторы ++ --. Можем попасть в следующий и предыдущий.
    //забыл называние типа итератора, есть толко ++, например forward_list. Можем попасть только в следующий
    for (auto set_iterator = a.begin(); set_iterator != a.end(); set_iterator++) {
        *set_iterator++;
    }

    for (auto elem : se) {
        cout << elem << ' ';
    }

    auto set_iterator = se.begin();
    set_iterator++;
    set_iterator++;
    set_iterator++;
    *set_iterator++;
    set_iterator--;


    vector<int> v;
    /*
    int* Tpointer;
    int size;
    int capacity;

    int value = 7;
    Tpointer = new int[100];
    size = 1;
    capacity = 100;
    Tpointer[0] = value;

    size--;
    */

    //инвалидация итератора
    //пример
    auto it = v.begin();
    cout << *it;

    for (int i = 0; i < 1000000; ++i) {
        v.push_back(100);
    }
    //тут много раз происходила реаллокация памяти для вектора. it смотрит на память, которую мы уже очистили

    //сортирует до правой границы. 1ый случай - до 5ого элемента, 2ой - весь вектор
    sort(v.begin(), v.begin() + 5);
    sort(v.begin(), v.end());
    cout << accumulate(v.begin(), v.end(), 0); //этот алгоритм из модуля numeric
    //count()
    //count_if()

    struct Student {
        string name;
        int score;
        int age;
    };

    vector<Student> vs;

    sort(vs.begin(), vs.end(), [](const auto& lhs, const auto& rhs) {
        if (lhs.score != rhs.score) {
            return lhs.score < rhs.score;
        }
        if (lhs.age != rhs.age) {
            reutrn lhs.age < rhs.age;
        }
        return lhs.name < rhs.name;
    });

    Student vasya{ "Vasya", 100, 100 };
    //[] - аргументы, которые нам нужны.
    //[vasya] - передали по копии.[&vasya]- передали по копии.
    //[=] передали все элементы по копии. [&] передали все элементы по ссылке
    //третим параметром передали правилол сравнения (лямбда функцию), так как компилятор на сможет сам правильно определеить
    //как сравнить структуру которую мы написали. (по каким полям сравнивать в первую, вторую, ... очередь)
    sort(vs.begin(), vs.end(), [vasya](const auto& lhs, const auto& rhs) {
        if (lhs.score != rhs.score) {
            return lhs.score < rhs.score;
        }
        if (lhs.age != rhs.age) {
            reutrn lhs.age < rhs.age;
        }
        return lhs.name < rhs.name;
    });

    //переменная my_max - хранит лямбда функцию. тип переменной my_max выводит компилятор
    auto my_max = [](int lhs, int rhs) {
        if (lhs < rhs) {
            return rhs;
        }
        return lhs;
    };

    int a1 = 10;
    int b1 = 20;
    cout << my_max(a1, b1);

    //принимает третим параметром функцию-предикат. Предикат возвращает для каждого элемента true или false
    //эта функция вернет количество семерок.
    int count = count_if(begin(v), end(v), [] (const auto& elem) {
        return elem == 7;
    });


    //функтор

    struct A {
        int a = 10;
        int operator()() {
            return a;
        }
    };

}

struct deq{
    int a[100];
    deq* next;
};