Как се оценява алгоритмичната сложност на операцията по вмъкване на елемент в средата на контейнера 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