std::list C++ является последовательным, тогда как это может занять постоянное время для операций вставки и удаления в любом месте последовательности
В справочнике по С ++ я читал: "Списки - это контейнеры последовательности, которые позволяют выполнять операции вставки и удаления в постоянное время в любом месте последовательности и выполнять итерации в обоих направлениях". я сомневаюсь, что если он последовательный, то как может потребоваться постоянное время для удаления и вставки узла. Любым способом мы должны последовательно пройти, чтобы достичь этого узла. Удаление узла зависит от его положения
4 ответа
O(1) относится к сложности вставки / удаления узлов, если у вас уже есть дескриптор (в форме итератора) для этого узла. Получение итератора для i- го элемента списка с заданным итератором для первого - O(N).
Это часто упускается из виду при оценке относительных достоинств std::list против, скажем, std::vector, Но обратите внимание, что как вставка, так и удаление элементов возвращают итераторы, которые можно использовать для дальнейших операций вставки / удаления.
Вставка перед данным узлом(давайте назовем его pos) или как последний узел, или удаление данного узла является операцией с постоянным временем.
std::list может быть реализован в виде двусвязного списка. Контейнеры последовательностей не следует путать с непрерывным требованием к памяти.
Потому что список не отсортирован. Если вы внимательно посмотрите, фактическая функция для размещения элементов в списке list::insert(hint, element) ( http://www.cplusplus.com/reference/list/list/insert/). Т.е. для каждой вставки место, где добавляется элемент, уже известно, таким образом, постоянное время.
Например list::push_front(element) коротка для insert(begin(), element),
[Это в основном комментарий, но он не вписывается в поле]
Обратите внимание, что std::list не может быть реализован в виде единого связанного списка для удовлетворения требований сложности:
- Даже если у вас уже есть дескриптор узла одного связанного списка, вы не можете вставить перед ним (или стереть его) в постоянное время (поскольку вам потребуется доступ к предыдущему узлу).
Вот почему std::forward_list только обеспечивает insert_after а также erase_after,