Какую структуру данных выберешь для хранения большого количества целых чисел с частой операцией добавления?

Выбор структуры данных для хранения целых чисел с частым добавлением

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

1. std::vector (Динамический массив)

Лучший выбор в большинстве случаев:

#include <vector>

std::vector<int> numbers;

// Добавление элементов
for (int i = 0; i < 1000000; i++) {
    numbers.push_back(i);  // Амортизированная O(1)
}

// Резервирование памяти заранее
numbers.reserve(1000000);  // Избегаем лишних переаллокаций

// Итерирование очень быстро
for (int num : numbers) {
    // Доступ: O(1)
}

Преимущества:

• Амортизированная сложность O(1) для push_back
• Кэш-дружественный (линейное расположение в памяти)
• Очень быстрый доступ по индексу O(1)
• Минимальный оверхед памяти

Недостатки:

• При большом количестве добавлений может потребоваться переаллокация
• Удаление элемента из середины O(n)

Оптимизация:

// Плохо: частые переаллокации
std::vector<int> v;
for (int i = 0; i < 1000000; i++) {
    v.push_back(i);  // Может переаллоцировать ~20 раз
}

// Хорошо: резервирование заранее
std::vector<int> v;
v.reserve(1000000);  // Одна аллокация
for (int i = 0; i < 1000000; i++) {
    v.push_back(i);  // Быстро, без переаллокации
}

// Очень хорошо: если размер неизвестен, используй growth factor
// std::vector обычно удваивает размер при необходимости

2. std::deque (Двусторонняя очередь)

Хорош для добавления с обеих сторон:

#include <deque>

std::deque<int> numbers;

// O(1) добавление в начало и конец
numbers.push_back(5);   // Быстро
numbers.push_front(3);  // Тоже быстро

// O(1) доступ по индексу
int first = numbers[0];  // Константное время

// Не требует переаллокации на месте

Когда использовать:

• Нужны добавления в начало и конец
• Нужен быстрый доступ по индексу
• Хотим избежать переаллокации

Недостатки:

• Более сложная структура (несколько блоков памяти)
• Медленнее на кэше, чем vector
• Чуть больше памяти

3. std::list (Двусвязный список)

Для частых вставок/удалений из середины:

#include <list>

std::list<int> numbers;

// O(1) добавление
numbers.push_back(5);
numbers.push_front(3);

// Но O(n) доступ по индексу!
auto it = numbers.begin();
std::advance(it, 500000);  // Очень медленно!

// Хорошо для вставок/удалений в известное место
auto iter = numbers.begin();
++iter;  // Вторая позиция
numbers.insert(iter, 100);  // O(1) если известна позиция

Когда использовать:

• Частые вставки/удаления из середины (при наличии итератора)
• Не требуется быстрый случайный доступ

Недостатки:

• O(n) доступ по индексу
• Плохая локальность кэша
• Больше памяти на node (2 указателя)
• Медленный проход по списку

4. std::set / std::unordered_set (Множества)

Только если нужна уникальность или сортировка:

#include <set>
#include <unordered_set>

// std::set: отсортированный, O(log n)
std::set<int> unique_numbers;
unique_numbers.insert(5);   // O(log n)
unique_numbers.insert(5);   // Дубликат, не добавляется

// std::unordered_set: хеш-таблица, O(1) в среднем
std::unordered_set<int> fast_unique;
fast_unique.insert(5);  // O(1) в среднем

// Но нет быстрого доступа по индексу!

Когда использовать:

• Нужна гарантия уникальности
• Нужны быстрые поиски (O(log n) или O(1))

Недостатки:

• Медленнее push_back, чем vector
• Не гарантирует порядок (unordered_set)
• Больше памяти на элемент

5. Custom решения: Ring Buffer

Для специальных случаев (очень частые добавления, фиксированный размер):

template<typename T, size_t SIZE>
class RingBuffer {
private:
    std::array<T, SIZE> buffer;
    size_t head = 0, tail = 0;
    size_t count = 0;

public:
    void push(T value) {
        buffer[tail] = value;
        tail = (tail + 1) % SIZE;
        if (count < SIZE) count++;
        else head = (head + 1) % SIZE;  // Перезаписываем старые
    }

    T pop() {
        T value = buffer[head];
        head = (head + 1) % SIZE;
        count--;
        return value;
    }

    bool is_full() const { return count == SIZE; }
    size_t size() const { return count; }
};

int main() {
    RingBuffer<int, 1000> rb;
    
    // O(1) добавление без аллокации
    for (int i = 0; i < 1000000; i++) {
        rb.push(i);  // Переиспользует памяти по кругу
    }
}

6. Comparison Table

*С итератором

Практический рекомендации

Используй std::vector если:

• Неизвестен точный размер
• Нужен быстрый доступ к элементам
• Основная операция — добавление в конец
• Нужна максимальная производительность

// Базовый вариант
std::vector<int> v;
v.reserve(expected_size);
for (auto num : data_source) {
    v.push_back(num);
}

Используй std::deque если:

• Нужны добавления с обеих сторон
• Нужна возможность удалить с обеих сторон

std::deque<int> q;
q.push_back(1);
q.push_front(0);

Используй std::list если:

• Очень частые вставки/удаления из середины
• Не нужен доступ по индексу

Используй set/unordered_set если:

• Нужна гарантированная уникальность
• Нужны быстрые поиски

Оптимизация памяти для больших объёмов

// Если храним очень много целых чисел, подумай о типе
std::vector<uint32_t> v;  // Вместо int, экономим 50% памяти

// Компрессия данных если они специальные
std::vector<int16_t> small_numbers;  // Если числа маленькие

// Memory pool для избежания фрагментации
std::vector<int> pool;
pool.reserve(10000000);  // Одна большая аллокация

Итог: Для большого количества целых чисел с частыми операциями добавления используй std::vector с предварительным резервированием памяти. Это обеспечивает максимальную производительность, минимальное потребление памяти и лучшую локальность кэша. Только если есть специфические требования (частые удаления, двусторонние очереди, уникальность) — рассмотри альтернативы.