std::list
Двусвязный список: вставка/удаление за O(1) по итератору.
Сигнатура
std::list<T>Контейнер std::list — двусвязный список. Вставка и удаление в любом месте за O(1) (если есть итератор), но нет доступа по индексу. Подходит, когда часто меняется середина последовательности.
std::list<int> lst = {1, 3};
auto it = lst.begin();
++it;
lst.insert(it, 2);
// список: {1, 2, 3}
std::cout << lst.size(); // результат: 3