Кратко — по каждой структуре: когда даёт преимущество по времени и памяти, типичные сложности, и практические рекомендации для выбора.
Массив (статический / динамический)
- Время: доступ по индексу $O(1)$. Добавление в конец у динамического массива — амортизированно $O(1)$, вставка/удаление в середине — $O(n)$.
- Память: плотное представление, накладные расходы минимальны — $O(n)$ (контiguous). Резервирование при росте даёт временный перепотребление.
- Преимущество: высокая кеш-локальность, компактность, быстрый случайный доступ.
- Когда выбирать: частые чтения/индексация, статические данные, очереди/стеки векторной реализации, когда важна экономия памяти и скорость чтения.
Связный список (singly/doubly, список узлов)
- Время: доступ по индексу $O(n)$. Вставка/удаление при наличии указателя на узел — $O(1)$.
- Память: значительный overhead на указатели: примерно $n\times$ (payload + pointer\_size). Итерирование медленнее из‑за плохой кеш‑локальности.
- Преимущество: эффективные сплайсы/перемещения подпоследовательностей без копирования.
- Когда выбирать: редко — когда нужно постоянное $O(1)$ добавление/удаление в середине при наличии итератора; для реализации очередей/стеков обычно лучше использовать массивы.
Хеш-таблица (хэш‑мапа)
- Время: среднее $O(1)$ для поиска/вставки/удаления, худший $O(n)$ при коллизиях (или $O(1)$ амортизировано с хорошей реализацией). Размер таблицы $m$, load factor $\alpha =\frac{n}{m}$.
- Память: потребляет больше, чем плотный массив — $O(m)$ с фактическим коэффициентом >1 из‑за пустых бакетов/цепочек.
- Преимущество: очень быстрые операции поиска по ключу, простая реализация словаря/множества.
- Когда выбирать: частые точечные поиски/вставки, порядок не важен, достаточно памяти для поддержания $\alpha$ низким; избегать при необходимости гарантированной скорости или упорядоченного обхода.
Деревья (балансные BST: AVL, Red‑Black; B‑tree для диска)
- Время: сбалансированное дерево — поиск/вставка/удаление $O(\log n)$. B‑tree для внешней памяти — $O({\log }_{B}n)$ по числу дисковых блоков $B$.
- Память: узлы с указателями — $O(n)$ с постоянным overhead на указатели/ключи/значения.
- Преимущество: поддержка упорядоченного множества, итераций в порядке, диапазонных запросов, predecessor/successor, гарантированные $O(\log n)$.
- Когда выбирать: нужен упорядоченный доступ, диапазонные запросы, детерминированные гарантии, индекс в БД (B‑tree) или когда хеш непригоден.
Куча (binary heap, pairing, Fibonacci)
- Время: доступ к минимуму/максимуму $O(1)$, вставка/удаление корня $O(\log n)$. Построение кучи из массива — $O(n)$. Фибоначчиева куча: амортизированное decrease‑key $O(1)$, extract‑min $O(\log n)$.
- Память: можно хранить в массиве — плотно $O(n)$.
- Преимущество: эффективна для приоритетной очереди, алгоритмов типа Dijkstra, слияний k‑вхождений.
- Когда выбирать: частые извлечения экстремума и вставки; когда нужен decrease‑key — смотреть на тип кучи (Фибоначчи, pairing).
Рекомендации при выборе для реального приложения
1. Определите горячие операции: какие операции наиболее часты/критичны? Сравнивайте по временным сложностям (например, нужен ли быстрый поиск по ключу, упорядоченный обход, частые вставки в середину и т.д.).
2. Учитывайте ограничения памяти и кеш‑поведения: если важна плотность и скорость чтения — массив/вектор; если память ограничена, хеш с большим $\alpha$ ухудшит производительность.
3. Нужен упорядоченный доступ или диапазонные запросы — берите сбалансированное дерево или отсортированный вектор + редкие вставки.
4. Для быстрых словарей/множеств обычно хеш‑таблица (если нет требований к порядку и допустимы амортизированные/средние гарантии).
5. Для внешней памяти/БД — B‑tree/LSM‑tree (оптимизация под блоки диска).
6. Для приоритетных задач — куча (binary heap для простоты, pairing/Fibonacci для специфических decrease‑key требований).
7. Конкурентность/параллелизм: проверяйте готовые concurrent-контейнеры или lock‑free реализации; простые структуры легче масштабируются.
8. Практика: сначала используйте стандартные контейнеры (std::vector, std::unordered_map, std::map, priority_queue), профилируйте по реальным нагрузкам, затем оптимизируйте (напр., заменить map на unordered_map, или на отсортированный вектор если вставки редки).
Коротко: выбирайте по характеру операций (поиска vs вставки vs упорядоченности), по требованиям памяти и по поведению на реальных данных (кеш‑локальность, распределение ключей). Профилирование и использование проверенных библиотек — ключ к правильному выбору.