Cum se evaluează complexitatea algoritmică a operației de inserare a unui element în mijlocul containerului std::list?

Вставка элемента в середину контейнера std::list в C++ имеет алгоритмическую сложность O(1), при условии, что у вас уже есть итератор на позицию вставки.

std::list реализован как двусвязный список, поэтому вставка или удаление элемента по итератору выполняется за константное время, так как требуется только переназначить несколько указателей.

Однако если нужно сначала найти позицию вставки, то время поиска зависит от количества элементов и будет O(n).

Пример вставки:

std::list<int> lst = {1, 2, 4, 5};
auto it = std::next(lst.begin(), 2); // итератор на элемент '4'
lst.insert(it, 3); // вставка '3' перед '4'
// lst теперь: 1, 2, 3, 4, 5