Dev Blog

Адаптери та нові інтерфейси ​

Адаптери: обмеження інтерфейсу як перевага ​

stack виражає LIFO, queue – FIFO, priority_queue – вибір найпріоритетнішого елемента. Вони використовують інший контейнер для зберігання, але відкривають вузький набір операцій. Наприклад, звичайна queue не дозволяє довільно відсортувати середину; це допомагає зберегти обрані правила обслуговування.

pop у стандартних адаптерів не повертає видалене значення. Спочатку читають front або top, потім виконують pop. На порожньому контейнері читання вершини некоректне: виклик empty є частиною алгоритму, а не необов’язковою діагностикою. Не зберігайте посилання на вершину після її видалення.

Компаратор priority_queue може здатися «оберненим»: типовий less дає найбільший елемент на top. У прикладі менший priority означає нижче місце, а за однакового пріоритету більший arrival іде пізніше. Це явно визначає нічию, яку сама priority_queue не зобов’язана розв’язувати стабільно за порядком вставки.

Обслуговування клієнтів і завдань ​

Умова. Порівняти FIFO-обслуговування з пріоритетами та часовою нічиєю.

cpp
#include <print>
#include <queue>
#include <string>
#include <vector>

struct Job { std::string name; int priority, arrival; };

struct Later {
    bool operator()(const Job& a, const Job& b) const {
        if (a.priority != b.priority)
            return a.priority < b.priority;
        return a.arrival > b.arrival;
    }
};

int main()
{
    std::queue<std::string> fifo;
    fifo.push("A"); fifo.push("B");
    while (!fifo.empty()) {
        std::println("FIFO: {}", fifo.front());
        fifo.pop();
    }
    std::priority_queue<Job, std::vector<Job>, Later> jobs;
    jobs.push({"normal", 1, 0});
    jobs.push({"urgent-1", 3, 1});
    jobs.push({"urgent-2", 3, 2});
    while (!jobs.empty()) {
        std::println("job: {}", jobs.top().name);
        jobs.pop();
    }
}

Результат виконання:

text
FIFO: A
FIFO: B
job: urgent-1
job: urgent-2
job: normal

Черга з пріоритетом не є моделлю реального медичного сортування. Тут числові пріоритети умовні й використовуються для програмних завдань. Перевірте два елементи з однаковим пріоритетом, порожню чергу та послідовність лише звичайних завдань.

Нові інтерфейси та перевірка підтримки ​

flat_map і flat_set C++23 поєднують впорядкований інтерфейс з компактним послідовним зберіганням. Пошук може бути логарифмічним, а вставка – лінійною через переміщення. Вони не є просто іншою назвою map. У перевіреному MSVC 19.51 заголовок flat_map присутній, а __cpp_lib_flat_map визначений. Для власного середовища перевіряють і макрос, і компіляцію малого прикладу; запис у плані курсу не повинен замінювати фактичну таблицю підтримки.

mdspan – невласний багатовимірний вигляд, а не контейнер, який самостійно володіє елементами матриці. Він описує відображення індексів на пам’ять і залежить від часу життя власника. inplace_vector та hive пов’язані з C++26; у перевіреній збірці заголовки відсутні. Тому обов’язкові приклади використовують наявні контейнери, а ці назви наведено для розуміння напрямку розвитку бібліотеки.

Не плутайте фіксовану максимальну місткість inplace_vector із незмінною кількістю array. Hive орієнтований на іншу модель стабільності елементів, а не на випадковий доступ вектора. Для прийняття рішення потрібні конкретні операції та гарантії, а не лише новіший рік у назві стандарту.

Перевірка вибору на практиці ​

Спочатку запишіть, що є ключем і чи допускаються дублікати. Далі перелічіть операції: додавання, пошук, відбір за діапазоном, видалення, друк. Якщо потрібен відбір усіх дат між двома межами, упорядкований словник і lower_bound природніші за хеш-таблицю. Якщо потрібна лише перевірка належності великого набору без порядку, варто оцінити unordered_set, але врахувати якість хеша.

Особливо перевіряйте зміну структури під час обходу. Безпечний шаблон видалення використовує ітератор, повернений erase, коли це передбачено інтерфейсом. Range-for не дає автоматичного захисту від push_back, rehash або видалення поточного елемента. У наступній темі ці правила розглядаються докладніше; уже зараз відділяйте фазу збирання змін від фази застосування, якщо гарантії незрозумілі.

У тестах порівнюйте математичний зміст, а не випадковий порядок хешованого обходу. Порожній набір, повторний ключ, відсутній пошук, нічиї пріоритетів і повторне оновлення значення – різні сценарії. Після кожного оновлення можна перевіряти інваріант: кількість записів, унікальність ключів та збереження потрібних значень.