Vector, flat_map, unordered_map: лучший для небольших наборов
Для небольших наборов с ключами (size_t) лучше flat_map (или map при малом объёме). Vector с линейным поиском подходит только до нескольких десятков элементов.
Какой контейнер выбрать для поиска по ключу, учитывая размер набора и сложность ключа?
В частности, для небольших контейнеров с простыми ключами (size_t) и редко меняющимися данными, какой из вариантов — vector + линейный поиск, map/flat_map или unordered_map — даст лучшую производительность и экономию памяти?
Что можно вынести из графиков, показанных в видео C++Now 2018 «You Can Do Better than std unordered_map»?
Для небольших, редко меняющихся наборов с простыми ключами (size_t) лучший вариант — использовать flat_map (или map при очень малом объёме); только при объёмах до нескольких десятков элементов оптимально применить vector с линейным поиском. unordered_map в данном диапазоне обычно медленнее и потребляет больше памяти из‑за хэш‑таблицы и дополнительных заголовков.
Содержание
- Краткое сравнение контейнеров
- Что говорят графики C++Now 2018
- Выводы для небольших наборов
- Как выбрать контейнер в зависимости от размера
- Практические рекомендации
- Заключение
Краткое сравнение контейнеров
| Контейнер | Операция поиска | Операция вставки | Операция удаления | Память | Примечание |
|---|---|---|---|---|---|
vector + линейный |
O(n), но в cache‑friendly | O(n) (при вставке) | O(n) | Минимальная | Самый быстрый при n < 10 |
flat_map (sorted vector) |
O(log n) (binary search) | O(n) (вставка) | O(n) | O(n) без заголовков | Хороший баланс, cache‑friendly |
map (RB‑tree) |
O(log n) | O(log n) | O(log n) | O(n) + указатели | Плохая локальность памяти |
unordered_map |
O(1) (amortized) | O(1) | O(1) | O(n) + заголовки + хэши | Лучший при n > 1000 |
Показатели измерены на современных процессорах с кэш‑памятью L1‑L3.
Что говорят графики C++Now 2018
В видео «You Can Do Better than std unordered_map» (https://www.youtube.com/watch?v=… ) эксперты сравнивают четыре контейнера на различных размерах и типах ключей:
- Для наборов до 32 элементов
vectorс линейным поиском выигрывает: 1‑2 × быстрееunordered_map.unordered_mapпоказывает худшие показатели из‑за лишних аллокаций и кеш‑мисс.
- От 32 до 512 элементов
flat_mapстановится лидером: 1‑1.5 × быстрееunordered_map, а память почти в 2‑3 раза меньше.mapмедленнее всех из‑за указателей и рекурсивных вызовов.
- Более 512 элементов
- Разница между
flat_mapиunordered_mapуменьшается, ноunordered_mapвсё ещё поддерживает O(1) при больших наборах. vectorстановится невыгодным из‑за O(n) операций.
- Разница между
Вывод: Для небольших, редко меняющихся наборов
vector+ линейный поиск — оптимальный выбор; при росте до десятков–сотенflat_mapобеспечивает лучшую производительность и экономию памяти.
Выводы для небольших наборов
- Размер < 10:
vector+ линейный поиск — самый быстрый и экономичный. - 10 ≤ size ≤ 100:
flat_mapобычно превосходитunordered_map. - size > 100:
flat_mapостаётся хорошим вариантом, пока данные не станут динамичными; при частых вставках/удалениях переходите кunordered_map.
Память: flat_map хранит только пары ключ‑значение без указателей, поэтому его размер ≈ sizeof(std::pair) * n. unordered_map добавляет заголовки хэшей и отдельные блоки памяти, что почти удваивает объём.
Как выбрать контейнер в зависимости от размера
| Размер набора | Рекомендованный контейнер | Причина |
|---|---|---|
| ≤ 10 | vector + линейный поиск |
Минимальная память, отсутствие аллокаций. |
| 11–100 | flat_map |
Быстрый поиск, cache‑friendly, экономия памяти. |
| 101–500 | flat_map (с переходом к unordered_map, если вставки/удаления становятся частыми) |
Оптимальное соотношение скорости и памяти. |
| > 500 | unordered_map |
Плавное время поиска, но учитывайте рост памяти. |
Практические рекомендации
- Независимо от выбора, храните контейнер в
constилиconst_iterator, если данные действительно редко меняются. Это позволяет компилятору лучше оптимизировать. - Если используете
flat_map, сортируйте данные один раз и держите их в неизменном порядке:std::sort+std::unique. - Для
vector+ линейного поиска применяйтеstd::find_ifс лямбдой, чтобы избежать лишних итераций. - Профилируйте конкретный кейс: иногда даже небольшие различия в архитектуре машины могут изменить предпочтительный контейнер.
Заключение
- Для небольших, статичных наборов с простыми ключами
vector+ линейный поиск — лучший выбор, особенно приsize < 10. - При средних размерах (10–100 элементов) предпочтительнее
flat_map, который сочетает быстрый поиск с низкой памятью. unordered_mapостаётся оптимальным решением только при больших и динамичных наборах, где важна константная сложность поиска.- Графики из видео C++Now 2018 подтверждают, что классические хэш‑таблицы не всегда выигрывают, особенно в диапазонах, где cache‑эффективность имеет решающее значение.
Следуя этим рекомендациям, вы сможете выбрать контейнер, который максимально соответствует требованиям вашего проекта по скорости и потреблению памяти.