template <typename T>
class vector
{
private:
    T* m_data;         // Покажчик на масив елементів
    size_t m_size;     // Кількість реально існуючих елементів
    size_t m_capacity; // Кількість елементів, для яких виділена пам'ять
};

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> numbers;  // Створення порожнього вектора
    
    // Додавання елементів у кінець (O(1) амортизована)
    numbers.push_back(10);
    numbers.push_back(20);
    numbers.push_back(30);
    
    // Довільний доступ (O(1))
    std::cout << "Перший елемент: " << numbers[0] << '\n';       // 10
    std::cout << "Другий елемент: " << numbers.at(1) << '\n';    // 20 (з перевіркою меж)
    
    // Розмір та ємність
    std::cout << "size: " << numbers.size() << '\n';              // 3
    std::cout << "capacity: " << numbers.capacity() << '\n';      // 4 (може бути більше)
    
    // Резервування ємності (уникнення реалокацій)
    numbers.reserve(100);  // Гарантує capacity >= 100
    std::cout << "capacity після reserve: " << numbers.capacity() << '\n';
    
    // Вставка у довільну позицію (O(n))
    numbers.insert(numbers.begin() + 1, 15);  // Вставити 15 на індекс 1
    // Тепер: {10, 15, 20, 30}
    
    // Видалення елемента (O(n))
    numbers.erase(numbers.begin());  // Видалити перший елемент
    // Тепер: {15, 20, 30}
    
    // Видалення останнього елемента (O(1))
    numbers.pop_back();
    // Тепер: {15, 20}
    
    // Очищення вектора (size = 0, capacity не змінюється)
    numbers.clear();
    std::cout << "Після clear — size: " << numbers.size() 
              << ", capacity: " << numbers.capacity() << '\n';
    
    return 0;
}

#include <iostream>
#include <deque>

int main()
{
    std::deque<int> deq;
    
    // Додавання у кінець (O(1))
    deq.push_back(30);
    deq.push_back(40);
    
    // Додавання на початок (O(1)) — ключова перевага!
    deq.push_front(20);
    deq.push_front(10);
    
    // Тепер: {10, 20, 30, 40}
    
    // Довільний доступ (O(1))
    std::cout << "deq[1] = " << deq[1] << '\n';  // 20
    
    // Видалення з обох кінців (O(1))
    deq.pop_front();  // Видалити 10
    deq.pop_back();   // Видалити 40
    // Тепер: {20, 30}
    
    // Вставка у середину (O(n))
    deq.insert(deq.begin() + 1, 25);  // Вставити 25 на індекс 1
    // Тепер: {20, 25, 30}
    
    // Обхід контейнера
    for (int x : deq)
    {
        std::cout << x << ' ';
    }
    std::cout << '\n';
    
    return 0;
}

#include <iostream>
#include <deque>
#include <string>

class CommandHistory
{
private:
    std::deque<std::string> m_commands;
    size_t m_currentIndex;

public:
    CommandHistory() : m_currentIndex(0) {}
    
    void execute(const std::string& cmd)
    {
        // Видаляємо команди після поточної позиції (якщо були undo)
        while (m_commands.size() > m_currentIndex)
        {
            m_commands.pop_back();
        }
        
        m_commands.push_back(cmd);
        ++m_currentIndex;
        
        std::cout << "Виконано: " << cmd << '\n';
    }
    
    void undo()
    {
        if (m_currentIndex > 0)
        {
            --m_currentIndex;
            std::cout << "Скасовано: " << m_commands[m_currentIndex] << '\n';
        }
        else
        {
            std::cout << "Немає команд для скасування\n";
        }
    }
    
    void redo()
    {
        if (m_currentIndex < m_commands.size())
        {
            std::cout << "Повторено: " << m_commands[m_currentIndex] << '\n';
            ++m_currentIndex;
        }
        else
        {
            std::cout << "Немає команд для повторення\n";
        }
    }
};

int main()
{
    CommandHistory history;
    
    history.execute("Вставити текст 'Hello'");
    history.execute("Видалити слово");
    history.execute("Вставити зображення");
    
    history.undo();  // Скасовано: Вставити зображення
    history.undo();  // Скасовано: Видалити слово
    
    history.redo();  // Повторено: Видалити слово
    
    history.execute("Змінити шрифт на жирний");
    // Команда "Вставити зображення" видалена з історії
    
    return 0;
}

template <typename T>
struct ListNode
{
    T data;
    ListNode* prev;
    ListNode* next;
};

#include <iostream>
#include <list>

int main()
{
    std::list<int> lst;
    
    // Додавання у кінець (O(1))
    lst.push_back(30);
    lst.push_back(40);
    
    // Додавання на початок (O(1))
    lst.push_front(20);
    lst.push_front(10);
    
    // Тепер: {10, 20, 30, 40}
    
    // НЕМАЄ довільного доступу [] або at()!
    // std::cout << lst[1];  // ПОМИЛКА компіляції
    
    // Доступ до першого та останнього елемента (O(1))
    std::cout << "Перший: " << lst.front() << '\n';  // 10
    std::cout << "Останній: " << lst.back() << '\n';  // 40
    
    // Вставка у довільну позицію (O(1), якщо маємо ітератор)
    auto it = lst.begin();
    ++it;  // Переміщуємо ітератор на 2-й елемент (20)
    lst.insert(it, 15);  // Вставити 15 перед елементом 20
    // Тепер: {10, 15, 20, 30, 40}
    
    // Видалення елемента (O(1), якщо маємо ітератор)
    auto itToRemove = lst.begin();
    std::advance(itToRemove, 2);  // Перемістити на 3-й елемент (20)
    lst.erase(itToRemove);  // Видалити 20
    // Тепер: {10, 15, 30, 40}
    
    // Обхід контейнера (єдиний спосіб доступу до всіх елементів)
    for (int x : lst)
    {
        std::cout << x << ' ';
    }
    std::cout << '\n';
    
    return 0;
}

#include <iostream>
#include <list>
#include <unordered_map>
#include <string>

class LRUCache
{
private:
    size_t m_capacity;
    std::list<std::pair<int, std::string>> m_items;  // {key, value}
    std::unordered_map<int, std::list<std::pair<int, std::string>>::iterator> m_map;

public:
    explicit LRUCache(size_t capacity) : m_capacity(capacity) {}
    
    void put(int key, const std::string& value)
    {
        // Якщо ключ вже є, видаляємо старий запис
        auto it = m_map.find(key);
        if (it != m_map.end())
        {
            m_items.erase(it->second);
        }
        
        // Додаємо новий елемент на початок списку (найсвіжіший)
        m_items.emplace_front(key, value);
        m_map[key] = m_items.begin();
        
        // Якщо перевищено ємність, видаляємо найстаріший (кінець списку)
        if (m_items.size() > m_capacity)
        {
            auto last = m_items.back();
            m_map.erase(last.first);
            m_items.pop_back();
        }
    }
    
    std::string* get(int key)
    {
        auto it = m_map.find(key);
        if (it == m_map.end())
        {
            return nullptr;  // Ключ не знайдено
        }
        
        // Переміщуємо елемент на початок (оновлення часу використання)
        auto listIt = it->second;
        m_items.splice(m_items.begin(), m_items, listIt);  // O(1) переміщення
        
        return &listIt->second;
    }
    
    void display() const
    {
        std::cout << "Кеш (найсвіжіший → найстаріший): ";
        for (const auto& [key, value] : m_items)
        {
            std::cout << "[" << key << ":" << value << "] ";
        }
        std::cout << '\n';
    }
};

int main()
{
    LRUCache cache(3);  // Ємність: 3 елементи
    
    cache.put(1, "один");
    cache.put(2, "два");
    cache.put(3, "три");
    cache.display();  // [3:три] [2:два] [1:один]
    
    cache.get(1);  // Доступ до ключа 1 → переміщує на початок
    cache.display();  // [1:один] [3:три] [2:два]
    
    cache.put(4, "чотири");  // Перевищено ємність → видаляємо найстаріший (2)
    cache.display();  // [4:чотири] [1:один] [3:три]
    
    return 0;
}

#include <array>

std::array<int, 5> arr = {10, 20, 30, 40, 50};  // Фіксований розмір 5
// arr.push_back(60);  // ПОМИЛКА: немає методу push_back (розмір фіксований)

template <typename T, size_t N>
struct array
{
    T m_data[N];  // Звичайний C-масив
    
    constexpr size_t size() const noexcept { return N; }
    T& operator[](size_t i) { return m_data[i]; }
    T& at(size_t i) { /* перевірка меж */ return m_data[i]; }
    // ... інші методи
};

#include <iostream>
#include <array>
#include <cmath>

class Vector3D
{
private:
    std::array<double, 3> m_coords;  // {x, y, z}

public:
    Vector3D(double x, double y, double z) : m_coords{x, y, z} {}
    
    double x() const { return m_coords[0]; }
    double y() const { return m_coords[1]; }
    double z() const { return m_coords[2]; }
    
    double length() const
    {
        return std::sqrt(m_coords[0] * m_coords[0] +
                        m_coords[1] * m_coords[1] +
                        m_coords[2] * m_coords[2]);
    }
    
    Vector3D operator+(const Vector3D& other) const
    {
        return Vector3D(m_coords[0] + other.m_coords[0],
                       m_coords[1] + other.m_coords[1],
                       m_coords[2] + other.m_coords[2]);
    }
    
    void display() const
    {
        std::cout << "(" << m_coords[0] << ", " 
                  << m_coords[1] << ", " 
                  << m_coords[2] << ")\n";
    }
};

int main()
{
    Vector3D v1(1.0, 2.0, 3.0);
    Vector3D v2(4.0, 5.0, 6.0);
    
    Vector3D v3 = v1 + v2;
    
    std::cout << "v1 = "; v1.display();
    std::cout << "v2 = "; v2.display();
    std::cout << "v1 + v2 = "; v3.display();
    std::cout << "Довжина v3: " << v3.length() << '\n';
    
    return 0;
}

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> numbers = {10, 20, 30, 40, 50};
    
    // Ітератор на перший елемент
    std::vector<int>::iterator it = numbers.begin();
    
    // Обхід контейнера через ітератор
    while (it != numbers.end())
    {
        std::cout << *it << ' ';  // Розіменування (як покажчик)
        ++it;  // Перехід до наступного елемента
    }
    std::cout << '\n';
    
    return 0;
}

std::vector<int> numbers = {10, 20, 30};

for (int x : numbers)
{
    std::cout << x << ' ';
}

{
    auto&& __range = numbers;
    auto __begin = __range.begin();
    auto __end = __range.end();
    
    for (; __begin != __end; ++__begin)
    {
        int x = *__begin;
        std::cout << x << ' ';
    }
}

#include <iostream>
#include <deque>
#include <stack>
#include <string>

// Типи операцій
enum class OperationType { INSERT, DELETE };

// Структура для збереження команди
struct Command
{
    OperationType type;
    size_t position;
    std::string text;
};

class TextEditor
{
private:
    std::deque<std::string> m_lines;  // Рядки тексту
    std::stack<Command> m_undoStack;  // Історія команд

public:
    void insertLine(size_t pos, const std::string& text)
    {
        if (pos > m_lines.size())
        {
            std::cerr << "Помилка: позиція за межами тексту\n";
            return;
        }
        
        m_lines.insert(m_lines.begin() + pos, text);
        m_undoStack.push({OperationType::INSERT, pos, text});
        
        std::cout << "Вставлено рядок на позицію " << pos << '\n';
    }
    
    void deleteLine(size_t pos)
    {
        if (pos >= m_lines.size())
        {
            std::cerr << "Помилка: позиція за межами тексту\n";
            return;
        }
        
        std::string deletedText = m_lines[pos];
        m_lines.erase(m_lines.begin() + pos);
        m_undoStack.push({OperationType::DELETE, pos, deletedText});
        
        std::cout << "Видалено рядок на позиції " << pos << '\n';
    }
    
    void undo()
    {
        if (m_undoStack.empty())
        {
            std::cout << "Немає операцій для скасування\n";
            return;
        }
        
        Command cmd = m_undoStack.top();
        m_undoStack.pop();
        
        if (cmd.type == OperationType::INSERT)
        {
            // Скасовуємо вставку → видаляємо рядок
            m_lines.erase(m_lines.begin() + cmd.position);
            std::cout << "Скасовано вставку на позиції " << cmd.position << '\n';
        }
        else  // DELETE
        {
            // Скасовуємо видалення → повертаємо рядок
            m_lines.insert(m_lines.begin() + cmd.position, cmd.text);
            std::cout << "Скасовано видалення на позиції " << cmd.position << '\n';
        }
    }
    
    void display() const
    {
        std::cout << "=== Вміст документа ===\n";
        for (size_t i = 0; i < m_lines.size(); ++i)
        {
            std::cout << i << ": " << m_lines[i] << '\n';
        }
        std::cout << "=======================\n";
    }
};

int main()
{
    TextEditor editor;
    
    editor.insertLine(0, "Перший рядок");
    editor.insertLine(1, "Другий рядок");
    editor.insertLine(2, "Третій рядок");
    editor.display();
    
    editor.deleteLine(1);  // Видаляємо "Другий рядок"
    editor.display();
    
    editor.undo();  // Скасовуємо видалення
    editor.display();
    
    editor.undo();  // Скасовуємо вставку "Третій рядок"
    editor.display();
    
    return 0;
}