Здравствуйте, TailWind, Вы писали:
TW>Непонятно. Что он даёт?
Дает интерфейс.
TW>Почему нельзя list вместо него использовать?
Можно использовать.
А можно не использовать.
А можно вектор. А можно дек.
Вместе с типом тащится его специфика.
Вместе с типом контейнера тащится:
— его специфика управления памятью (его аллокатор);
— специфика доступа к элементам (интерфейс, категории итераторы, complexity);
— всякое другое вроде специфики инвалидации итераторов, thread safety, и т.д.
TW>Для чего лишняя сущность?
Это адаптер.
Он определяет интерфейс. Скрывает детали.
Грубо говоря если это очередь, то у тебя должны быть push и pop,
но не должны быть push_front/back, pop_front/back и не должно
быть всяких там at, оператора[], итераторов и прочего.
Потому что применение других методов контейнера может
сломать инвариант очереди.
Здравствуйте, TailWind, Вы писали:
TW>- list хорошо для больших блоков данных. Так как выигрывает по скорости
Не выигрывает.
list — структура данных, главное достоинство которой — поддерджка быстрой операции splice. И операций, реализующихся через splice, — вставку и удаление элементов из середины контейнера, например.
Всё остальное в list плохо по сравнению с deque.
Так как для queue splice не нужен, то все достоинства list не используются, а все недостатки сохраняются (бóльшие накладные расходы по памяти, частые вызовы аллкатора, фрагментация памяти, большое число кеш-промахов).
Почти единственный вариант, когда list может быть оправдан для queue, — это когда хочется зачем-то гарантировать маленькие аллокации под элементы, так как deque аллоцирует блоками и не предоставляет интерфейса для настройки их размера.
Это какие-то вырожденные случаи, когда, например, есть миллионы очередей, в каждой из которой находится не больше одного элемента, и хочется сэкономить память ценой более медленной работы.
Здравствуйте, rg45, Вы писали:
R>А это как раз и зависит от того, какой используется underlying container. Когда по умолчанию используется std::deque, то при добавлении (но не при удалении) элемента могут происходить релокации и элементы очереди могут перемещаться или копироваться, все итераторы инвалидируются
я когда-то давно наткнулся в литературе на safe-итераторы, которые не инвалидируются, обрадовался, потом не смог даже нагуглить про существование оных. Понятно, что самому написать можно.
Здравствуйте, TailWind, Вы писали:
TW>Или какой контейнер лучше использовать? (чтобы не было перекопирования элементов)
Внезапно, есть такая штука, как семантика перемещения!
И у вектора она дешёвая.
И у контейнеров, выполняющих переаллокацию (то есть, у того же вектора) — происходит не копирование, а перемещение элементов.
Поэтому можно немножко расслабиться по поводу того, что у тебя элементы — это гигантские vector<UCHAR>. Если всё сделаешь аккуратно, там не будет копирования этих самых гигантских массивов.
deque вообще не перемещает элементы, если не делать вставки-удаления из середины.
По части расхода памяти — list самый избыточный, затем идёт deque (который устроен, как вектор векторов), ну и наконец, собственно vector.
Если очередь короткая, то можно повыбирать между vector, deque и какими-нибудь кольцевыми буферами (их нет в стандартной библиотеке, но можно взять готовый https://www.boost.org/doc/libs/master/doc/html/circular_buffer.html или самому наколхозить, если не лень)
Если очередь длинная, то лучше взять deque, он не будет заниматься сдвигом элементов.
list — во всех случаях проигрывает, потому что он жрёт память. forward_list — чуть дешевле.
А теперь отвечу на вопрос, зачем нужен именно queue.
1) пишешь код, в котором фигурирует std::queue<T>, где T — это твои std::vector<UCAHR>
2) профилируешь его
3) если видишь, что операции push/pop оказались узким местом, то заменяешь std::queue<T> на std::queue<T, another_underlying_container<T>> (экспериментируешь там со списком, кольцевым буфером, рукодельным деком)
4) если видишь, что очередь (больше) не является узким местом, то не паришь себе голову.
Вся выгода тут в том, что, меняя контейнер у адаптера, ты не меняешь весь клиентский код.
Но, конечно, можешь с самого начала написать код работы с очередью, где вместо push/pop будет push_back/pop_front.
Здравствуйте, Кодт, Вы писали:
К>Внезапно, есть такая штука, как семантика перемещения! К>И у вектора она дешёвая.
Только вот вектор не совсем подходит по требованиям underlying контейнера ввиду отсутсвия у него функции-члена pop_front (который используется внутри queue::pop). Конечно, этот недостаток можно без особого труда восполнить собственными силами, тем не менее, дополнительное телодвижение сделать нужно.
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, T4r4sB, Вы писали:
TB>А очередь на основе вектора понимает, что если ты вытащил элемент из начала, то не обязательно весь хвост сдвигать каждый раз?
А она и не вытащит — ввиду отстустствия у вектора pop_front — это нужно допиливать самому. И тут уже все будет зависеть от того, как будет утсроен этот самый pop_front, ну и весь этот контейнер.
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, T4r4sB, Вы писали:
TB>А очередь на основе вектора понимает, что если ты вытащил элемент из начала, то не обязательно весь хвост сдвигать каждый раз?
Конечно, не понимает. Потому что queue<T,Container>.pop = Container.pop_front.
А стандартная реализация вектора резервирует место только в хвосте — и поэтому сдвигает всё при удалении из головы.
Если хочется, то можно написать рукодельный вектор, который будет оставлять пустое место в голове.
Только надо продумать правила реаллокации. Например, если в хвосте место кончилось, то в каких случаях надо увеличивать размер хранилища, а в каких — сдвинуть всё в голову.
Чистого кодинга там, думаю, на пару часов. Ещё день — на юниттесты и отладку.
Если упороться по всевозможным сочетаниям Copy/Move Constructible/Assignable — то ещё день уйдёт. Это я пессимистичную оценку даю.
Но опять-таки, мы же не знаем характерный размер очереди у ТС.
Если очередь из десятка векторов (пусть каждый из которых по стопятьсот значений), то сдвиг хвоста — "это не проблемы, а расходы".
И затраты на дек (который гарантированно будет выделять-удалять блоки на куче, хоть и не на каждую операцию) могут оказаться даже дороже.
Профилировать надо!
Здравствуйте, rg45, Вы писали:
К>>Внезапно, есть такая штука, как семантика перемещения! К>>И у вектора она дешёвая.
R>Только вот вектор не совсем подходит по требованиям underlying контейнера в виду отсутсвия у него функции-члена pop_front (который используется внутри queue::pop). Конечно, этот недостаток можно без особого труда восполнить собственными силами, тем не менее, дополнительное телодвижение сделать нужно.
Ой, точно. Давненько не заглядывал в справочник
Что, однако, не мешает наколхозить.
pop_front() = erase(begin()).
Можно хакнуть STL и сделать специализацию queue<T, vector<T>>.
Перекуём баги на фичи!
