push_back

 
0
 
C++
ava
xTr1m | 21.03.2013, 19:35
День добрый, не побоюсь задать глупый вопрос, но почему

std::vector<int> vec;
for(int i=0; i<1000000; ++i)
    vec.push_back(i);

выполняется много быстрее, чем

std::list<int> list;
for(int i=0; i<1000000; ++i)
    list.push_back(i);

ведь вектору время от времени нужно делать рекопирование данных, в то время как списку просто создать объект и добавить на него ссылку с предыдущего?
или это в windows\msvs такая кривая реализация list? тогда в чем преимущество list?
Comments (13)
ava
baldina | 21.03.2013, 19:32 #
а с чего вы взяли что быстрее?

но допустим, быстрее. тогда такой ответ:
в случае списка память выделяется при добавлении каждого элемента.
в случае массива памяти выделяется каждый раз больше (раза в два), чем требуется, тем самым снижается число распределений памяти и копирований (и увеличивается выделенная, но неиспользуемая память)
преимущества списка не в добавлении в конец, а в добавлении в середину. в случае с vector копировать придется, даже если памяти достаточно, в случае списка - нет
ava
Alexeis | 21.03.2013, 20:56 #
Цитата (baldina @  21.3.2013,  20:32 findReferencedText)
в параметрах шаблона имеется allocator, так что стратегией выделения памяти можно управлять 

  Вот я тоже в свое время увидел это аллокатор, а вот других стандартных STL аллокаторов не встречал. Из этих же соображений пользую везде вектор. По ходу, нужно иметь список тыщ на 10 чтобы он окупил расходы по перераспределению памяти.
ava
volatile | 21.03.2013, 23:57 #
лист с маленькими типами вообще неэффективно юзать.
там накладных расходов дофига.
в каждом есть ссылка на предыдущий, следующий, это как минимум.
Фактически размер выделенной памяти получаецца в несколько раз больше полезного.

преимущество листа, в том что элементы остаюцца всегда на своих местах
даже при перемещении из одного списка в другой, (при правильном перемещении естественно)
есть моменты, когда это необходимо.
ava
disputant | 22.03.2013, 07:18 #
Цитата (xTr1m @ 21.3.2013,  18:35)
ведь вектору время от времени нужно делать рекопирование данных, в то время как списку просто создать объект и добавить на него ссылку с предыдущего?

или это в windows\msvs такая кривая реализация list? тогда в чем преимущество list?

В среднем получается, что каждый элемент рекопируется - каким бы длинным ни был вектор - аж один раз... Проверьте сами :)

А потом попробуйте из заполненных вектора и списка многократно удалять, скажем, первый элемент...
ava
Alexeis | 22.03.2013, 10:02 #
Цитата (volatile @  22.3.2013,  00:57 findReferencedText)
преимущество листа, в том что элементы остаюцца всегда на своих местах

даже при перемещении из одного списка в другой, (при правильном перемещении естественно)

есть моменты, когда это необходимо.


  Я так понимаю, речь о том, что все итераторы остаются валидными у листа, в то время как любая вставка/удаление в векторе потенциально делает невалидными все итераторы.
  А как сделать, чтобы при перемещении из одного list-а в другой итераторы сохранялись? 
ava
Alexeis | 22.03.2013, 10:12 #
Тест
ava
Alexeis | 22.03.2013, 10:12 #
Тест2
ava
volatile | 22.03.2013, 12:05 #
Цитата (Alexeis @  22.3.2013,  10:02 findReferencedText)
А, все нашел, есть метод splice 

Ага, при перемещении допустим из середины одного списка в другой, все итераторы сохраняюцца, в том числе и перемещаемого (-емых)
Для наглядности, если тоже самое проделать с векторами, то это повлечет за собой кучу пересылок, (а значит времени). При этом все итераторы (не только перемещаемые) в обоих векторах станут не валидными.


ava
Alexeis | 22.03.2013, 16:04 #
Цитата (volatile @  22.3.2013,  13:05 findReferencedText)
Для наглядности, если тоже самое проделать с векторами, то это повлечет за собой кучу пересылок, (а значит времени). При этом все итераторы (не только перемещаемые) в обоих векторах станут не валидными.

  В этому случае, можно сами данные выделять в куче, а в вектор помещать shred_ptr. Соответственно ссылаться не на не итераторы, а указатели в виде shred_ptr. Вектор с указателями работает быстро на всех операциях и в случае перераспределения памяти или элементов значения указателей остаются неизменными. При этом вектор дает большое преимущество - константное время адресации по индексу. 
ava
volatile | 22.03.2013, 18:41 #
Цитата (Alexeis @  22.3.2013,  16:04 findReferencedText)
 Вектор с указателями работает быстро на всех операциях 

Даже вектор с указателями не обгонит лист, в определенных условиях.
Допустим нужно удалить первый указатель в векторе с миллионом этих указателей. В этом случае остальные 999,999 штук указателей должны будут переместицца вперед, на освободившееся место.
В случае с листом, там будет обновлено только пару ссылок "следующий", "предыдущий"  (и еще может парочка внутренних переменных)
никаких грамадных перемещений миллионов указателей не будет.smile 

ava
Alexeis | 22.03.2013, 20:57 #
Цитата (volatile @  22.3.2013,  19:41 findReferencedText)
Допустим нужно удалить первый указатель в векторе с миллионом этих указателей. В этом случае остальные 999,999 штук указателей должны будут переместицца вперед, на освободившееся место.


  Ну я так и говорил, что смысл появляется при числе элементов порядка 10к+ . Но опять же вопрос, что чаще нужно делать выбирать произвольный элемент или делать вставки. Если 99% времени идут запросы по рандомным индексам, то лист захлебнется от перебора таких длиннющих списков.  Там уже нужны другие структуры данных типа хеш таблиц. Лист хорошо подходит для линейных потоковых операций, где ведется последовательная обработка длинных цепочек данных. Как только произвольный доступ, будь то 100 элементов, а тем более 100к эффективность будет плохая. Лично мне такие задачи не попадались. Да, я пару раз использовал его в качестве массива к которому нужен был лишь перебор, но чисто для эксперимента. 
ava
maxim1000 | 22.03.2013, 22:09 #
Цитата (Alexeis @  22.3.2013,  20:57 findReferencedText)
Лист хорошо подходит для линейных потоковых операций, где ведется последовательная обработка длинных цепочек данных.


кстати, тоже не всегда

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

я вообще забыл, когда последний раз список использовал...
ava
volatile | 22.03.2013, 23:46 #
Ну согласен, лист нужен гораздо реже вектора, но иногда он очень хорошо ложицца.
Последний раз, когда я его юзал, это был кеш картинок. (фрагменты большой карты). При любом обращении к картинке, она перемещалась на самый верх кеша. Обращения шли часто. Если бы это был вектор, то там бы пришлось при каждом таком обращении, перетасовывать его весь, а с листом очень лёгкая, и ясная операция получилась.
произвольный доступ там не был нужен.
В общем бывают случаи когда лист очень хорош.


Please register or login to write.
Firm of day
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Contributors
advanced
Submit