Какие преимущества имеют векторы перед связанными списками

Question

У меня был следующий обмен с моим профессором, который не очень удовлетворял. Я включил свои части обмена, которых должно быть достаточно, чтобы донести свою точку зрения.

"Для векторов проходит ли реализация C ++ через каждый элемент старого динамически размещенного массива и освобождает его? (Правка: я имею в виду, при изменении размера и добавлении элементов, либо с помощью pushback, либо с изменением размера)

Мне особенно любопытно, потому что в книге делается попытка сделать так, чтобы связанные списки вызывали беспокойство из-за необходимости проходить каждый раз. Мне не кажется, чтовекторы имеют огромное преимущество в этом отношении.

Основным преимуществом векторов, которое я вижу, является удобство и быстрый доступ, но не намного больше. Как, например, каждый раз, когда вы пытаетесь сделать что-то кроме доступа, вы будетепройти через все, чтобы двигаться и освободить память. Это правильно? "

После его ответа я добавил.

" Профессор хххх,

Я вышел на тестирование,и на самом деле, адреса меняются, если вы изменяете размер или push_back, поэтому я предполагаю, что старые адреса освобождаются. правильно. Я могу только предположить, что программе придется обращаться к каждому элементу, чтобы освободить его, и, если это правильно, не будет ли добавление новых вещей дорогостоящим с точки зрения времени, даже больше, чем обход связанных списков?

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

TL; DR: недостаток связанных списков заключается в обходе, но использование векторов (push_back, resize () и т. Д.) Чаще всего требует обхода в любом случае, так как же векторы быстрее?

Answer 1

Есть несколько вещей, которые работают быстрее, чем вы ожидаете:

• Когда вектор перераспределяется, исходные элементы уничтожаются, а не освобождаются, один за другим. Их хранилище освобождается сразу. Это в отличие от связанного списка, где каждый узел выделяется и освобождается индивидуально. Но это несколько спорный вопрос, потому что:

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

Answer 2

В качестве дополнения к уже предоставленному ответу и комментариям ...

Элементы std::vector хранятся в памяти непрерывно, хотя это не относится к связанному списку. Прямым следствием является то, что доступ к элементу тривиален для std::vector, но не для связанного списка. Например, если я хочу получить доступ к элементу n ^th связанного списка, я должен выполнить итерацию по списку до достижения нужного элемента.

Но нас другой стороны, связанный список будет работать лучше, если мы хотим вставить новый элемент внутрь. Действительно, для связанного списка мы должны выполнять итерации, пока не достигнем желаемой позиции, тогда нам просто нужно изменить соединения между предыдущим и следующим узлом, чтобы новый элемент вставлялся между ними. Для std::vector необходимо переместить все элементы после требуемой позиции (и при необходимости перераспределить, т. Е. Если добавление нового элемента превышает зарезервированное доступное пространство).

Таким образом, std::vector равно лучше для доступа к элементу , но менее эффективно при вставке элемента внутрь (то же самое для удаления).