Какой контейнер STL выбрать для хранения большого количества элементов, если их итоговое число заранее неизвестно?

В подавляющем большинстве случаев для этой задачи в C++ следует использовать std::vector.

Почему std::vector?

• Динамическое расширение: Вектор автоматически управляет своей памятью. При вызове push_back() или emplace_back() он выделит новый, больший блок памяти, если текущей capacity недостаточно.
• Эффективность доступа: Обеспечивает константное время доступа по индексу (O(1)) благодаря непрерывному хранению данных в памяти, что также улучшает производительность за счёт локальности данных (cache-friendliness).
• Контроль над переаллокациями: Можно заранее зарезервировать память с помощью reserve(), чтобы минимизировать дорогостоящие операции копирования/перемещения.

Пример:

#include <vector>
#include <iostream>

int main() {
    std::vector<int> dataStream;
    // Резервируем память под ожидаемое количество элементов для оптимизации
    dataStream.reserve(1000);

    // Симулируем получение неизвестного количества данных
    for (int incomingValue = 0; incomingValue < 5000; ++incomingValue) {
        dataStream.push_back(incomingValue);
    }
    std::cout << "Фактический размер: " << dataStream.size() << 'n';
    std::cout << "Зарезервированная ёмкость: " << dataStream.capacity() << 'n';
    return 0;
}

Альтернативы и их ниши:

• std::deque: Хорош, если нужны частые вставки/удаления как в начало, так и в конец. Доступ по индексу также O(1), но с большей константой, чем у вектора.
• std::list (двусвязный список): Стоит рассмотреть только при очень частых вставках/удалениях в произвольных позициях, когда производительность вектора/дека неприемлема. Жертвует локальностью данных и доступом по индексу.