Re[5]: Как устроен queue?
От: watchmaker  
Дата: 27.03.23 12:27
Оценка: +1
Здравствуйте, TailWind, Вы писали:

TW>- list хорошо для больших блоков данных. Так как выигрывает по скорости


Не выигрывает.

list — структура данных, главное достоинство которой — поддерджка быстрой операции splice. И операций, реализующихся через splice, — вставку и удаление элементов из середины контейнера, например.
Всё остальное в list плохо по сравнению с deque.

Так как для queue splice не нужен, то все достоинства list не используются, а все недостатки сохраняются (бóльшие накладные расходы по памяти, частые вызовы аллкатора, фрагментация памяти, большое число кеш-промахов).


Почти единственный вариант, когда list может быть оправдан для queue, — это когда хочется зачем-то гарантировать маленькие аллокации под элементы, так как deque аллоцирует блоками и не предоставляет интерфейса для настройки их размера.
Это какие-то вырожденные случаи, когда, например, есть миллионы очередей, в каждой из которой находится не больше одного элемента, и хочется сэкономить память ценой более медленной работы.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.