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

-1

Почему это случайное удаление из std :: vector быстрее, чем std :: list? То, что я делаю, чтобы ускорить это, - это обмен случайным элементом с последним, а затем удаление последнего. Я бы подумал, что список будет быстрее, поскольку случайное удаление - это то, для чего он был создан.Как происходит случайное удаление из 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

источник

2009-05-14 Peter Ølsted

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

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

источник

2009-05-14 20:49:12 jalf

Действительно. Я не вижу там никакой случайности. –

Тогда какова цель std :: list, когда с одним свопом вектор быстрее и дает произвольный доступ? –

Это зависит от того, хотите ли вы сохранить вектор в порядке или нет. –

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

источник

2009-05-14 20:51:45 Macke

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

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

источник

2009-05-14 20:52:20

при написании стирания вы имеете в виду pop_back? AFAIK pop_back() не заменяет базовый массив (что означало бы его создание, до которого требуется много времени). Это уменьшает только размер вектора, а затем вызывает деструктор? –

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

Да, жаль, что я имел в виду вызовы pop_back и pop_front.В случае списка он реализуется с точки зрения стирания –

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

источник

2009-05-14 21:22:25 Sergio

Ухаживать за ним? –

Если ваша архитектура не имеет режима доступа к указателю + индексной памяти и/или не содержит регистров для того, что вы делаете, то вполне вероятно, что при возникновении ситуаций, когда доступ по индексу требует дополнительной инструкции или, по указателю/итератору. Конечно, вы можете потерять это, если вы вызовете end() в условии цикла, и компилятор не (или не может) оптимизировать его за пределами цикла. –

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

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

источник

2009-05-14 21:32:12

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

ответ

Смежные вопросы