Нет ли способа вставить в список STL за O (1) раз?

Question

Теоретически, вы должны иметь возможность вставлять в любое место списка (по индексу по вашему выбору) за O (1) время.Но при использовании списка STL вам нужно вставить в позицию итератора, и, насколько я понимаю, позиция итератора должна быть увеличена в O (n) раз, чтобы установить желаемый индекс.Я не понимаю, почему это так, конечно, я ошибаюсь, и есть способ сделать это быстрее?

Answer 1

наверняка я ошибаюсь

Нет, вы не ошиблись.

а есть способ сделать это быстрее?

Вы можете сделать это быстрее, только если вы кэшировали позицию для вставки, фиксируя возвращаемое значение из предыдущего вызова для вставки. Если у вас нет никакой информации, кроме списка и индекса, по которому вы хотите вставить, тогда O(n) - ваш единственный вариант, где n - это индекс, по которому вы хотите вставить.