¿Cómo se evalúa la complejidad algorítmica de la operación de insertar un elemento en el medio del contenedor 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