Вектор - это осязаемая вещь, но список, о котором вы думаете, - это название пути к представлению нескольких слабо связанных, но отдельных вещей.
Вектор похож накоробка для яиц - это коробка с фиксированным количеством ячеек, в каждом из которых может быть или не быть чего-то внутри.Напротив, то, что вы думаете о списке, больше похоже на то, как вы берете несколько отдельных туфель и связываете их шнурки.«Список» на самом деле является представлением одной cons-ячейки , которая содержит значение - например, ячейку в коробке с яйцами - и указывает на другую cons-ячейку, которая также содержит значение и указывает на другую cons-ячейку,который содержит значение и, возможно, указывает ни на что другое, что делает его концом списка.То, что вы считаете списком, на самом деле не одно, а скорее отношение между несколькими различными cons-ячейками.
Вы правы, что есть некоторые операции, которые вы можете выполнять с обеими структурами, но их сложность времени отличается.Для списка нажатие элемента на передний план фактически ничего не меняет в существующем списке;вместо этого это означает создание новой cons-ячейки для представления новой head списка и указание этой cons-ячейки в существующем списке как нового tail .Это операция O (1) ;Неважно, насколько длинным был список, так как создание новой ячейки всегда занимает одинаковое количество времени.Точно так же, выталкивание элемента из передней части списка не изменяет существующий список;это просто означает смещение вашего взгляда на одну ячейку от текущей головы, чтобы увидеть, что было вторым элементом в качестве новой головы.
В отличие от этого, для переноса нового элемента вперед с вектором необходимо сначала переместить все существующие элементы на один пробел, чтобы в начале оставить пустое пространство - при условии, что в векторе достаточно места для всех элементов.существующие предметы и еще один.Это смещение имеет временную сложность O (n) , что означает, что чем больше элементов в векторе, тем больше времени требуется для их перемещения и освобождения места для нового элемента.Точно так же выталкивание из передней части вектора требует смещения всех существующих элементов, кроме первого, в направлении фронта, чтобы то, что было вторым, стало первым, а то, что было третьим, стало вторым, и так далее.Опять же, это сложная по времени O (n) .
Иногда можно поиграть с бухгалтерией в векторе, так что вытаскивание предмета с фронта не требует смещения всех существующихпредметы окончены;вместо этого просто измените запись о том, какой элемент считается первым.Вы можете себе представить, что у этого есть много проблем: индексы, используемые для доступа к элементам, должны быть скорректированы, емкость вектора больше не проста для интерпретации, и перераспределяя пространство для вектора для размещения новых элементов, теперь необходимо будет рассмотреть, где оставить новые элементы.-доступное пустое пространство после копирования существующих данных в новое хранилище. структура "deque" решает эти проблемы.
Выбор между списком и вектором требует обдумывания того, что вы собираетесь с ним делать, и как много вы знаете заранее о природе иразмер контента.Каждый из них поет в разных сценариях, несмотря на очевидное совпадение в их предназначении.
В то время, когда я писал ответ выше, задавался вопрос о толкании и выталкивании элементов с фронта как вектора, так и списка.Работа с end вектора как vector-push и vector-pop do намного больше похожа на манипулирование заголовком списка, чем на различие, проведенное в моем сравнении выше.В зависимости от того, может ли вектор вместить другой элемент без перераспределения, нажатие и выталкивание элементов в конце вектора занимает постоянное ( O (1) ) время.