Контейнеры и стоимость операций

Контейнер выбирают не по привычке, а по операциям, которые задача выполняет чаще всего. Массив удобен для доступа по индексу, множество — для членства, словарь — для связи ключа со значением, очередь — для удаления в порядке поступления.

Какую таблицу требует поток значений

Дан поток целых чисел. Нужно построить таблицу частот, чтобы затем быстро отвечать, сколько раз встречалось любое значение. Числа могут быть большими и отрицательными, поэтому прямой массив счётчиков по значению может оказаться непрактичным.

Что происходит при хранении пар в списке

Можно хранить пары (значение, частота) в обычном списке. Для каждого нового числа линейно искать его пару и увеличивать счётчик. Если различных ключей k, один поиск занимает до O(k), а весь подсчёт — до O(nk), то есть O(n²) при всех разных значениях.

Почему обновление тормозит линейный поиск

Обновление счётчика само по себе стоит O(1). Дорога повторная линейная адресация: перед каждым обновлением мы заново ищем запись нужного ключа.

Выбираем контейнер по главной операции

Задача естественно описывается соответствием ключ → счётчик. unordered_map в C++ и dict в Python выполняют поиск и обновление по ключу в ожидаемое O(1). Если нужен только ответ «есть или нет», значение не требуется и лучше использовать set.

Полезные ориентиры: чтение vector[i] в C++ и list[i] в Python — O(1); добавление в конец динамического массива — амортизированное O(1); удаление из начала массива — O(n) из-за сдвига; поиск в неотсортированном массиве — O(n).

Динамический массив — это три величины, а не «массив без границ»

Для std::vector полезна физическая модель непрерывного буфера. Распространённая реализация CPython хранит в таком массиве ссылки на объекты, но точное устройство Python list не закреплено контрактом языка и может отличаться в другой реализации. На алгоритмическом уровне Python list ведёт себя как динамический массив: даёт быстрый доступ по индексу и амортизированно быстрое добавление в конец.

В модели динамического массива структура хранит:

• адрес буфера;
• size — сколько позиций занято логически;
• capacity — сколько позиций уже выделено физически.

Всегда выполняется инвариант 0 ≤ size ≤ capacity. Благодаря непрерывному буферу адрес элемента вычисляется по индексу, поэтому случайный доступ занимает O(1), а последовательный обход хорошо использует кэш процессора.

Python list концептуально ближе к std::vector, чем к std::list. Название list не означает связный список: доступ values[i] рассматривается как O(1). C++ std::list, напротив, состоит из раздельных узлов и не поддерживает быстрый доступ по индексу.

Что происходит при append, когда места больше нет

Если size < capacity, новый элемент записывается в свободную позицию и size увеличивается. Если буфер заполнен, контейнер выполняет дорогой шаг:

1. выделяет буфер большей ёмкости, обычно с мультипликативным запасом;
2. переносит или копирует существующие элементы в новый буфер;
3. освобождает старый буфер;
4. добавляет новый элемент.

Точный коэффициент роста — деталь реализации, а не часть контракта языка. Существенно то, что ёмкость растёт не на единицу. Иначе последовательность из n добавлений копировала бы 1 + 2 + … + (n - 1) элементов и стоила бы O(n²).

Почему append амортизированно O(1), хотя расширение стоит O(n)

Отдельное добавление в момент перераспределения может стоить O(n). Но при геометрическом росте дорогие копирования происходят всё реже. За длинную последовательность добавлений суммарно переносится порядка

1 + 2 + 4 + … < 2n

элементов. Поэтому n добавлений требуют O(n) суммарной работы, а средняя стоимость одного в этой последовательности — амортизированное O(1).

«Амортизированное» описывает гарантированную среднюю стоимость последовательности операций, а не вероятность и не худшее время одного push_back/append.

Мини-модель роста без попытки заменить библиотеку

Концептуально динамический массив можно представить так:

append(value):
    if size == capacity:
        new_capacity = max(1, capacity * 2)
        allocate new_buffer[new_capacity]
        move elements [0, size) into new_buffer
        buffer = new_buffer
        capacity = new_capacity
    buffer[size] = value
    size += 1

В реальной задаче используйте стандартный контейнер. Эта модель нужна, чтобы объяснить стоимость и важный C++-эффект: перераспределение vector может сделать недействительными старые указатели, ссылки и итераторы на элементы. reserve уменьшает число расширений, когда примерный размер известен заранее, но не меняет логический size.

Почему вставка в середину остаётся O(n)

Свободная ёмкость помогает добавить элемент в конец, но не создаёт отверстие внутри плотного порядка. Вставка по индексу сдвигает суффикс вправо, удаление — влево. В худшем случае перемещаются O(n) элементов.

Запас capacity - size также занимает память. Это осознанный обмен: немного свободного места и редкие дорогие расширения вместо нового выделения на каждом добавлении.

Когда плотный массив — правильная первая мысль

Выбирайте std::vector или Python list, когда важны:

• доступ по числовому индексу;
• плотное хранение и быстрый последовательный проход;
• в основном добавление и удаление с конца;
• сортировка или бинарный поиск по индексируемому диапазону.

Не выбирайте динамический массив ради частых удалений с начала, стабильности адресов после роста или O(1) вставки в произвольную середину. Очередь/дек, другой способ организации индексов или узловая структура могут лучше выражать такие операции.

Как читать состояние таблицы частот

После обработки первых i элементов frequency[x] равно числу появлений x среди индексов [0, i). Для отсутствующего ключа считаем частоту равной нулю.

Обновляем счётчик каждого ключа

1. Создать пустую таблицу frequency.
2. Для каждого значения получить текущий счётчик, считая отсутствующий равным нулю.
3. Увеличить счётчик на единицу.
4. После прохода использовать таблицу для запросов частоты.

Частоты и безопасный запрос отсутствующего ключа

C++17

#include <cassert>
#include <unordered_map>
#include <vector>

using namespace std;

unordered_map<int, int> countValues(const vector<int>& values) {
    unordered_map<int, int> frequency;

    for (int value : values) {
        ++frequency[value];
    }

    return frequency;
}

int getCount(const unordered_map<int, int>& frequency, int value) {
    const auto found = frequency.find(value);
    if (found == frequency.end()) {
        return 0;
    }
    return found->second;
}

int main() {
    const auto frequency = countValues({2, -1, 2, 7, 2});
    assert(getCount(frequency, 2) == 3);
    assert(getCount(frequency, -1) == 1);
    assert(getCount(frequency, 100) == 0);
}

Python 3

def count_values(values: list[int]) -> dict[int, int]:
    frequency: dict[int, int] = {}

    for value in values:
        frequency[value] = frequency.get(value, 0) + 1

    return frequency


frequency = count_values([2, -1, 2, 7, 2])
assert frequency.get(2, 0) == 3
assert frequency.get(-1, 0) == 1
assert frequency.get(100, 0) == 0

Ожидаемая стоимость словаря

При ожидаемом O(1) для хеш-поиска подсчёт занимает ожидаемое O(n) времени и O(k) памяти, где k — число различных значений. В худшем случае коллизии могут ухудшить время. Упорядоченный map в C++ даёт O(log k) на операцию, но хранит ключи по порядку.

Какие ключи и запросы требуют внимания

• Пустой вход создаёт пустую таблицу.
• Отрицательные и очень большие ключи не требуют огромного массива.
• Все значения одинаковы: таблица содержит один ключ.
• Все значения различны: память растёт до O(n).
• Запрос отсутствующего ключа не должен случайно менять таблицу, если нужен только просмотр.

Проверяем плотные и редкие ключи

Проверь пустой список, один ключ, повторяющийся ключ, отрицательное значение и запрос отсутствующего ключа. Для {2, -1, 2, 7, 2} ожидаются частоты 2 → 3, -1 → 1, 100 → 0.

По каким словам выбирать map или set

Сигналы словаря: «посчитать по каждому значению», «сопоставить идентификатор с данными», «найти по ключу». Сигналы множества: «встречалось ли», «все ли уникальны». Перед выбором назови операции и их требуемую стоимость.

Когда массив или очередь выражают задачу лучше

Не используй хеш-таблицу, если диапазон ключей мал и плотен — массив счётчиков проще и быстрее. Если нужен отсортированный обход или гарантированное худшее время, подойдёт упорядоченная структура. Для удаления строго с начала потока нужна очередь, а не список со сдвигом.

Почему чтение через [] может изменить таблицу

Вопрос. Почему frequency[value] удобно при подсчёте в C++, но нежелательно при простом запросе?

Ответ. Оператор [] создаёт отсутствующий ключ со значением по умолчанию. При подсчёте это полезно, а запрос несуществующего ключа неожиданно изменит таблицу, поэтому для чтения лучше find.

Когда прямой массив счётчиков выгоднее

Вопрос. Когда массив из 1_000_001 счётчика лучше словаря?

Ответ. Когда ключи гарантированно лежат в плотном диапазоне 0..1_000_000, память допустима, а быстрый прямой доступ важен. Для редких ключей вроде -10^9 и 10^9 словарь экономнее.

Ищем первый уникальный элемент

Найди первый элемент массива с частотой 1, сохранив исходный порядок. Подсказка: первым проходом построй словарь частот, вторым снова пройди исходный массив и верни первый ключ со счётчиком 1.

Самостоятельная задача о журнале событий

Задача 1

Дан список строковых идентификаторов в порядке поступления событий. Верните идентификаторы, встретившиеся не менее трёх раз, сохранив порядок их первого появления. Опишите контракт функции и оцените время и дополнительную память для худшего входа.

Контейнер следует за операциями

Сначала назови частые операции, затем выбери контейнер: в задаче о частотах словарь убирает повторный поиск записи и явно моделирует состояние ключ → счётчик.