#c #list #stl
#c #Список #stl
Вопрос:
Теоретически, вы должны иметь возможность вставлять в любое место списка (по выбранному вами индексу) за O (1) время. Но при использовании списка STL вам нужно вставить в позицию итератора, и, насколько я понимаю, позиция итератора должна быть увеличена O (n) раз, чтобы установить для нее нужный индекс. Я ошеломлен, почему так оно и есть, конечно, я ошибаюсь, и есть способ сделать это быстрее?
Комментарии:
1. Списки на самом деле не имеют индексов. Ваше понимание списка кажется в корне ошибочным. Возможно, вы хотите
std::vector?2. A
std::list— это список с двойной связью. Переход к N-му элементуO(N)похож на любой другой связанный список. Если у вас уже есть итератор в позицию, в которую вы хотите вставить новый элемент, тогда этоO(1).3. Нет, вы неправильно поняли (хотя это распространенное недоразумение). С помощью связанного списка вы можете вставлять в позицию данного узла за постоянное время. Определение этого узла в среднем занимает линейное время.
4. Это может помочь устранить вашу путаницу, если вы попытаетесь самостоятельно создать список с нужным типом вставки. В какой-то момент вы застрянете, и именно этот момент будет ответом на ваш вопрос.
5. «Вставка в связанный список — это операция постоянного времени», похоже, одна из тех мантр, которые вы изучаете в начале своей карьеры, как раз перед тем, как забыть условия, при которых это верно. Вы можете найти недавнее видео Страуструпа в Интернете, где он делится своим удивлением по поводу того, насколько медленные случайные вставки списка сравниваются с вектором.
Ответ №1:
конечно, я ошибаюсь
Нет, вы не ошибаетесь.
и есть способ сделать это быстрее?
Вы можете сделать это быстрее, только если вы кэшировали позицию, в которую нужно вставить, захватив возвращаемое значение из предыдущего вызова insert . Если у вас нет никакой информации, кроме списка и индекса, в который вы хотите вставить, то O(n) это ваш единственный вариант, где n находится индекс, в который вы хотите вставить.