Розбори та типові помилки

Розбір сценарію: каталог і два незалежні порядки

Розглянемо каталог книг із кодом, автором, назвою та кількістю примірників. Вимога «пошук за кодом» природно веде до map або unordered_map. Вимога «усі книги автора» має інший ключ і допускає повтори. Один контейнер не зобов’язаний одночасно забезпечувати обидва інтерфейси з найкращою складністю. Можна зберігати основні записи за кодом, а додатковий індекс – автор → коди книг.

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

Тепер потрібно змінити автора книги. Послідовність дій важлива: знайти запис, перевірити допустимість нового автора, підготувати новий індекс, вилучити старий зв’язок та змінити основний запис. Якщо посеред операції можливий виняток, треба визначити гарантію узгодженості. Для навчальної невеликої бази можна сформувати новий стан у копії й замінити його після успішних перевірок. Це дорожче, але робить гарантію зрозумілою.

Таблиця 13.1. Узгодження двох індексів одного каталогу

Операція	Основне сховище	Індекс авторів
Додавання	Новий унікальний код	Додати код до групи автора
Зміна назви	Змінити поле запису	Змін не потрібно
Зміна автора	Оновити автора	Перенести код між групами
Видалення	Вилучити код	Вилучити зв’язок і порожню групу

Тести повинні перевіряти не лише красивий звіт. Після видалення книги жоден індекс не має повертати її код. Після перейменування автора загальна кількість книг не змінюється. Повторне додавання того самого коду має або відмовити, або виконати явно визначене оновлення; ці дві політики не можна випадково змішати використанням [] в одному місці та insert в іншому.

Де достатньо одного вектора

Якщо записів лише кілька десятків, змінюються вони рідко, а звіт потрібно друкувати в кількох порядках, vector є добрим початком. Основний порядок можна зберегти, а для звіту створити vector індексів або копію відфільтрованих записів. Це відділяє порядок зберігання від порядку представлення. Проте індекси теж потребують оновлення після видалення з середини, тому їх не варто зберігати безстроково.

Вектор особливо зручний для пакетної обробки: завантажити всі дані, відсортувати один раз, виконати багато читань. Map може бути зручнішим для постійних вставок із підтриманням порядку. Хеш-таблиця виграє в іншому сценарії: часті точні пошуки за ключем без інтервальних запитів. Жодне з цих тверджень не є універсальним рейтингом контейнерів.

Поширені помилки, відтворені маленькими трасами

Перший випадок: словник має один запис A → 10. Ви хочете лише перевірити B і пишете if (prices["B"] == 0). Після перевірки словник уже має два ключі, бо [] створив B. Тепер size повідомляє 2, а звіт містить вигаданий нуль. Правильний спосіб читання залежить від політики відсутності: contains, find або at, але не неявна вставка.

Другий випадок: у multiset є {2,2,2,5}. Виклик erase(2) прибирає всі еквівалентні ключі. Для списання одного примірника спочатку find, потім erase за ітератором, якщо він не end. Контрольний результат тоді {2,2,5}. Різниця перевантажень має безпосередній доменний зміст: один примірник проти всіх примірників.

Третій випадок: set рейтингу порівнює лише бал. Два різні гравці з балом 100 стають еквівалентними ключами, і другий не вставляється. Якщо потрібні обидва, додайте у компаратор унікальний ID як другий критерій або використайте multiset з іншою моделлю пошуку. Оператор == гравця не виправить еквівалентність компаратора.

Четвертий випадок: у priority_queue стоять A з пріоритетом 3 та B з пріоритетом 1. Якщо змінити зовнішній об’єкт A, це не змінить уже скопійований у чергу запис. Якщо через непряму вказівникову модель змінити ключ на місці, структура купи не перебудується автоматично. Для змінюваних пріоритетів потрібна явна стратегія: перебудова, повторна вставка з версією або інша структура даних.

План відтворюваного експерименту зі складністю

Для порівняння контейнерів згенеруйте один vector ключів за фіксованим seed і використайте його для всіх реалізацій. Окремо сформуйте запити: половина наявних, половина відсутніх. Час побудови вимірюйте окремо від часу запитів. Інакше контейнер із дорогою початковою організацією даних здаватиметься повільним навіть у задачі, де він потім обслуговує мільйони пошуків.

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

Виконайте щонайменше кілька повторів для кожного розміру й подайте медіану, а не випадковий найкращий запуск. Запишіть режим оптимізації, архітектуру, версію компілятора та чи був виклик reserve. Якщо для n=100 і n=1000 порядок швидкості змінився, це привід пояснити сталі витрати, а не приховати незручний результат. Одна машина й один тип ключа не дають підстав оголошувати контейнер найкращим для всіх програм.

Перевірка інваріантів після операції

Наступна таблиця є не списком обов’язкових контейнерів, а способом перетворити загальну вимогу на конкретну перевірку. Наприклад, «кеш працює» надто нечітко; «після вставки четвертого ключа місткість 3 не перевищена, а найстаріший ключ відсутній» уже має спостережуваний результат. Оберіть перевірки для власного варіанта до написання коду операції.

Таблиця 13.2. Від загальної вимоги до конкретного інваріанта

Сценарій	Що перевірити після зміни
Словник контактів	Повторний try_emplace не змінив старого номера й size.
Черга друку	Кожен прийнятий ID виконано один раз, скасований не виконано.
LRU-кеш	Ключі словника точно відповідають вузлам списку; size не перевищує ліміт.
Бібліотечні примірники	Списання одного зменшило кратність рівно на один.
Рейтинг	Оновлення бала не залишило старої версії запису в set.
Граф дружби	Кожному ребру A–B відповідає B–A; немає ребра A–A.
Парковка	Зайняті й вільні місця не перетинаються, їх сума дорівнює місткості.
Частоти слів	Сума лічильників дорівнює кількості прийнятих слів.
Склад за секціями	Переміщення не змінило загальної кількості товару.

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