#include <unordered_map>

std::unordered_map<std::string, std::string> dictionary;

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

// Знайти елемент 30
auto it = std::find(numbers.begin(), numbers.end(), 30);  // O(n)

#include <iostream>
#include <set>

int main()
{
    std::set<int> numbers;
    
    // Вставка елементів (O(log n))
    numbers.insert(30);
    numbers.insert(10);
    numbers.insert(50);
    numbers.insert(20);
    numbers.insert(30);  // Дублікат — ігнорується
    
    // Розмір множини: 4 (дублікат не додався)
    std::cout << "Розмір: " << numbers.size() << '\n';
    
    // Ітерація — завжди відсортована!
    std::cout << "Елементи: ";
    for (int x : numbers)  // Виведе: 10 20 30 50 (відсортовано)
    {
        std::cout << x << ' ';
    }
    std::cout << '\n';
    
    // Пошук елемента (O(log n))
    if (numbers.find(20) != numbers.end())
    {
        std::cout << "20 знайдено\n";
    }
    
    // Видалення елемента (O(log n))
    numbers.erase(30);
    
    // Перевірка наявності (C++20: contains)
    if (numbers.contains(30))  // C++20
    {
        std::cout << "30 є у множині\n";
    }
    else
    {
        std::cout << "30 відсутній\n";
    }
    
    return 0;
}

#include <iostream>
#include <unordered_set>

int main()
{
    std::unordered_set<int> numbers;
    
    // Вставка елементів (O(1) у середньому)
    numbers.insert(30);
    numbers.insert(10);
    numbers.insert(50);
    numbers.insert(20);
    numbers.insert(30);  // Дублікат — ігнорується
    
    // Розмір: 4
    std::cout << "Розмір: " << numbers.size() << '\n';
    
    // Ітерація — порядок НЕ гарантований!
    std::cout << "Елементи: ";
    for (int x : numbers)  // Може вивести: 20 50 10 30 (довільний порядок)
    {
        std::cout << x << ' ';
    }
    std::cout << '\n';
    
    // Пошук (O(1) у середньому)
    if (numbers.find(20) != numbers.end())
    {
        std::cout << "20 знайдено\n";
    }
    
    // Видалення (O(1) у середньому)
    numbers.erase(30);
    
    return 0;
}

#include <iostream>
#include <vector>
#include <unordered_set>

std::vector<int> findDuplicates(const std::vector<int>& numbers)
{
    std::unordered_set<int> seen;
    std::unordered_set<int> duplicates;
    
    for (int num : numbers)
    {
        if (seen.contains(num))  // C++20
        {
            duplicates.insert(num);
        }
        else
        {
            seen.insert(num);
        }
    }
    
    return std::vector<int>(duplicates.begin(), duplicates.end());
}

int main()
{
    std::vector<int> numbers = {1, 2, 3, 2, 4, 5, 3, 6, 7, 3};
    
    auto dups = findDuplicates(numbers);
    
    std::cout << "Дублікати: ";
    for (int x : dups)
    {
        std::cout << x << ' ';
    }
    std::cout << '\n';
    
    return 0;
}

#include <iostream>
#include <map>
#include <string>

int main()
{
    std::map<std::string, int> ages;
    
    // Вставка пар (O(log n))
    ages["Олександр"] = 25;
    ages["Марія"] = 30;
    ages["Дмитро"] = 22;
    ages.insert({"Анна", 28});
    
    // Доступ до значення за ключем (O(log n))
    std::cout << "Вік Марії: " << ages["Марія"] << '\n';
    
    // Якщо ключа немає, operator[] створює його зі значенням за замовчуванням!
    std::cout << "Вік Петра: " << ages["Петро"] << '\n';  // Створить {"Петро", 0}
    std::cout << "Розмір після доступу: " << ages.size() << '\n';  // 5 (додався Петро)
    
    // Безпечний доступ через at() (викидає виняток, якщо ключа немає)
    try
    {
        std::cout << ages.at("Іван") << '\n';  // std::out_of_range
    }
    catch (const std::out_of_range& e)
    {
        std::cout << "Ключ 'Іван' не знайдено\n";
    }
    
    // Ітерація — відсортована за ключами (алфавітний порядок для string)
    std::cout << "Всі записи:\n";
    for (const auto& [name, age] : ages)  // C++17 structured bindings
    {
        std::cout << "  " << name << ": " << age << '\n';
    }
    
    // Пошук ключа
    if (ages.find("Марія") != ages.end())
    {
        std::cout << "Марія є у мапі\n";
    }
    
    // Видалення
    ages.erase("Петро");
    
    return 0;
}

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

int main()
{
    std::unordered_map<std::string, int> wordCount;
    
    std::string text = "hello world hello C++ world hello";
    std::istringstream stream(text);
    std::string word;
    
    // Підрахунок частоти слів (O(n) для n слів)
    while (stream >> word)
    {
        ++wordCount[word];  // Якщо ключа немає, створюється зі значенням 0
    }
    
    // Виведення результатів (порядок НЕ гарантований)
    std::cout << "Частота слів:\n";
    for (const auto& [word, count] : wordCount)
    {
        std::cout << "  " << word << ": " << count << '\n';
    }
    
    return 0;
}

#include <iostream>
#include <unordered_map>
#include <vector>
#include <queue>
#include <string>
#include <sstream>

// Допоміжна структура для порівняння пар (слово, частота)
struct WordFreq
{
    std::string word;
    int count;
    
    // Оператор для priority_queue (мінімальна купа)
    bool operator<(const WordFreq& other) const
    {
        return count > other.count;  // Інвертуємо для min-heap
    }
};

std::vector<WordFreq> topKFrequent(const std::string& text, int k)
{
    // Крок 1: Підрахунок частоти (O(n))
    std::unordered_map<std::string, int> wordCount;
    std::istringstream stream(text);
    std::string word;
    
    while (stream >> word)
    {
        ++wordCount[word];
    }
    
    // Крок 2: Знаходження топ-K через мінімальну купу (O(n log k))
    std::priority_queue<WordFreq> minHeap;
    
    for (const auto& [word, count] : wordCount)
    {
        minHeap.push({word, count});
        
        if (minHeap.size() > static_cast<size_t>(k))
        {
            minHeap.pop();  // Видаляємо найменший елемент
        }
    }
    
    // Крок 3: Витягуємо результат
    std::vector<WordFreq> result;
    while (!minHeap.empty())
    {
        result.push_back(minHeap.top());
        minHeap.pop();
    }
    
    // Реверсуємо, щоб найчастіші були на початку
    std::reverse(result.begin(), result.end());
    
    return result;
}

int main()
{
    std::string text = "hello world hello C++ world hello programming "
                      "C++ programming hello world C++ hello";
    
    auto top3 = topKFrequent(text, 3);
    
    std::cout << "Топ-3 найчастіших слів:\n";
    for (const auto& [word, count] : top3)
    {
        std::cout << "  " << word << ": " << count << " разів\n";
    }
    
    return 0;
}

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

// Перевірка балансу дужок у виразі
bool isBalanced(const std::string& expression)
{
    std::stack<char> brackets;
    
    for (char ch : expression)
    {
        if (ch == '(' || ch == '{' || ch == '[')
        {
            brackets.push(ch);
        }
        else if (ch == ')' || ch == '}' || ch == ']')
        {
            if (brackets.empty())
            {
                return false;  // Закриваюча дужка без відкриваючої
            }
            
            char opening = brackets.top();
            brackets.pop();
            
            // Перевірка відповідності типів дужок
            if ((ch == ')' && opening != '(') ||
                (ch == '}' && opening != '{') ||
                (ch == ']' && opening != '['))
            {
                return false;
            }
        }
    }
    
    return brackets.empty();  // Всі дужки мають бути закриті
}

int main()
{
    std::cout << std::boolalpha;
    std::cout << "((3+5)*2): " << isBalanced("((3+5)*2)") << '\n';      // true
    std::cout << "((3+5)*2: " << isBalanced("((3+5)*2") << '\n';        // false
    std::cout << "{[()()]}: " << isBalanced("{[()()]}") << '\n';        // true
    std::cout << "{[(])}: " << isBalanced("{[(])}") << '\n';            // false
    
    return 0;
}

std::stack<int, std::vector<int>> stackOnVector;  // Стек на базі vector
std::stack<int, std::list<int>> stackOnList;      // Стек на базі list

#include <iostream>
#include <queue>
#include <string>

struct PrintJob
{
    std::string documentName;
    int pages;
};

class PrintQueue
{
private:
    std::queue<PrintJob> m_jobs;

public:
    void addJob(const std::string& name, int pages)
    {
        m_jobs.push({name, pages});
        std::cout << "Додано до черги: " << name << " (" << pages << " стор.)\n";
    }
    
    void processNext()
    {
        if (m_jobs.empty())
        {
            std::cout << "Черга порожня\n";
            return;
        }
        
        PrintJob job = m_jobs.front();
        m_jobs.pop();
        
        std::cout << "Друкується: " << job.documentName 
                  << " (" << job.pages << " стор.)\n";
    }
    
    void showQueue() const
    {
        if (m_jobs.empty())
        {
            std::cout << "Черга порожня\n";
            return;
        }
        
        std::cout << "У черзі " << m_jobs.size() << " завдань:\n";
        std::queue<PrintJob> temp = m_jobs;  // Копіюємо для обходу
        
        while (!temp.empty())
        {
            std::cout << "  - " << temp.front().documentName << '\n';
            temp.pop();
        }
    }
};

int main()
{
    PrintQueue printer;
    
    printer.addJob("Звіт.pdf", 5);
    printer.addJob("Презентація.pptx", 12);
    printer.addJob("Договір.docx", 3);
    
    printer.showQueue();
    
    std::cout << "\nОбробка черги:\n";
    printer.processNext();
    printer.processNext();
    
    printer.showQueue();
    
    return 0;
}

#include <iostream>
#include <queue>
#include <string>

struct Task
{
    std::string name;
    int priority;  // Більше число = вищий пріоритет
    
    // Оператор для priority_queue (максимальна купа за замовчуванням)
    bool operator<(const Task& other) const
    {
        return priority < other.priority;  // Інвертуємо для max-heap
    }
};

int main()
{
    std::priority_queue<Task> tasks;
    
    // Додаємо завдання з різними пріоритетами
    tasks.push({"Написати код", 3});
    tasks.push({"Виправити критичний баг", 10});
    tasks.push({"Оновити документацію", 2});
    tasks.push({"Ревю коду", 5});
    tasks.push({"Терміновий виправлення", 9});
    
    std::cout << "Виконання завдань за пріоритетом:\n";
    while (!tasks.empty())
    {
        Task current = tasks.top();
        tasks.pop();
        
        std::cout << "  [Пріоритет " << current.priority << "] " 
                  << current.name << '\n';
    }
    
    return 0;
}

// Мінімальна купа для int
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

minHeap.push(5);
minHeap.push(2);
minHeap.push(8);

std::cout << minHeap.top();  // Виведе: 2 (найменший елемент)