Почему случайное удаление из std::vector происходит быстрее, чем из std::list?

Question

Почему случайное удаление из std::vector происходит быстрее, чем из std::list?Чтобы ускорить процесс, я заменяю случайный элемент последним, а затем удаляю последний.Я думал, что список будет работать быстрее, поскольку он был создан для случайного удаления.

for(int i = 500; i < 600; i++){
    swap(vector1[i], vector1[vector1.size()-1]);
    vector1.pop_back();
}

for(int i = 0; i < 100; i++){
        list1.pop_front();
}

Результаты (в секундах):
Удаление Vec-свопа:0,00000909461232367903
Список обычного удаления:0,00011785102105932310

Answer 1

Однако то, что вы делаете, не является случайным удалением.Вы удаляете с конца, для чего и создаются векторы (помимо прочего).

И при замене вы выполняете одну случайную операцию индексации, которая также какие векторы хороши.

Answer 2

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

Таким образом, ваш выбор контейнера также зависит от того, какая семантика вам нужна.

Answer 3

Это не случайно.Попробуйте вектор1.erase(vector.begin() + rand() % вектор.размер());вместо.

Answer 4

Список erase приведет к удалению стертого элемента списка, это вызовет вызов метода delete оператор.Стирание вектора просто вызывает замену, а затем целочисленное уменьшение — это намного быстрее.

Answer 5

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