Почему случайное удаление из 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 swap delete: 0.00000909461232367903
Нормальное удаление списка: 0.00011785102105932310

Answer 1

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

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

Answer 2

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

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

Answer 3

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

Answer 4

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

Answer 5

Это не случайно. Попробуйте vector1.erase (vector.begin () + rand ()% vector.size ()); вместо этого.