Здравствуйте, 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.
TW>Непонятно. Что он даёт? TW>Почему нельзя list вместо него использовать? TW>Для чего лишняя сущность?
Потому что неэффективен и избыточен по функционалу. list предполагает выделение отдельного дескриптора с двумя указателями и самим элементом на каждый добавленый элемент, плюс служебная информация на каждом выделении — так что дергать кучу и получать 2*64+ ~24 байта мусора в нагрузку на каждый элемент. Минус кеш памяти, использовать — последнее дело.
deque — выделает и удаляет блоками — редко, поэтому добавление и удаление элемента, это по большей части инкремент/декремент счетчика. Плюс извлечение последовательно по памяти а значит скорее всего будет закешировано.
Здравствуйте, TailWind, Вы писали:
TW>Это связный список или он на основе вектора
В основе std::queue может лежать любой контейнер, удовлетворяющий требованиям SequenceContainer и имеющий функции-члены front, back, push_back, pop_front. Из стандартных контейнеров под эти требования подходят std::list и std::deque. По умолчанию используется std::deque, но она может быть заменена по желанию любым подходящим по требованиям контейнером, в т.ч. и самописным. (А самописный, в свою очередь, может быть реализован поверх какого-то из стандарных). Короче говоря, варианты есть.
TW>Вопрос: когда добавляю или удаляю элемент в queue, остальные элементы лежат на месте или копируются?
А это как раз и зависит от того, какой используется underlying container. Когда по умолчанию используется std::deque, то при добавлении (но не при удалении) элемента могут происходить релокации и элементы очереди могут перемещаться или копироваться, все итераторы инвалидируются (подробнее здесь: std::deque::push_back). Но можно вместо std::deque использовать std::list, тогда все элементы будут лежать на месте и итераторы не будут инвалидироваться.
--
Не можешь достичь желаемого — пожелай достигнутого.
TW>>Вопрос: когда добавляю или удаляю элемент в queue, остальные элементы лежат на месте или копируются?
R>А это как раз и зависит от того, какой используется underlying container. Когда по умолчанию используется std::deque, то при добавлении (но не при удалении) элемента могут происходить релокации и элементы очереди могут перемещаться или копироваться, все итераторы инвалидируются (подробнее здесь: std::deque::push_back).
Похоже ты считаешь, что из инвалидации итераторов как-то следует инвалидация ссылок на элементы, но это совсем не так. Операции на обоих границах deque никогда не инвалидируют ссылки на незатронутые элементы. https://eel.is/c++draft/deque#modifiers-1
An insertion at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque.
А для удаления ещё более строгие рядом требования.
Так что в контексте std::queue использование std::deque никогда не будет приводить к перемещению или к копированию элементов. И замена dequeue на list ничего не изменит этом числе копирований или перемещений.
Да, итераторы инвалидируются, но не многие алгоритмы или контейнеры сохраняют или как-то используют итераторы на внутренние элементы одновременно с модификацией контейнера. И адаптер queue тоже не входит в их число — ему вообще не нужны итераторы нижележащего контейнера.
Здравствуйте, TailWind, Вы писали:
TW>Непонятно. Что он даёт?
Дает интерфейс.
TW>Почему нельзя list вместо него использовать?
Можно использовать.
А можно не использовать.
А можно вектор. А можно дек.
Вместе с типом тащится его специфика.
Вместе с типом контейнера тащится:
— его специфика управления памятью (его аллокатор);
— специфика доступа к элементам (интерфейс, категории итераторы, complexity);
— всякое другое вроде специфики инвалидации итераторов, thread safety, и т.д.
TW>Для чего лишняя сущность?
Это адаптер.
Он определяет интерфейс. Скрывает детали.
Грубо говоря если это очередь, то у тебя должны быть push и pop,
но не должны быть push_front/back, pop_front/back и не должно
быть всяких там at, оператора[], итераторов и прочего.
Потому что применение других методов контейнера может
сломать инвариант очереди.
Все описано тут https://en.cppreference.com/w/cpp/container/queue и тут https://en.cppreference.com/w/cpp/container/deque.
TW>Это связный список или он на основе вектора
Условно говоря, список.
TW>Вопрос: когда добавляю или удаляю элемент в queue, остальные элементы лежат на месте или копируются?
Лежат на месте.
TW>Мне нужно сделать FIFO из vector<UCHAR>, больших по размеру TW>Подходит для этого queue?
Да.
Здравствуйте, TailWind, Вы писали:
TW>- list хорошо для больших блоков данных. Так как выигрывает по скорости
Не выигрывает.
list — структура данных, главное достоинство которой — поддерджка быстрой операции splice. И операций, реализующихся через splice, — вставку и удаление элементов из середины контейнера, например.
Всё остальное в list плохо по сравнению с deque.
Так как для queue splice не нужен, то все достоинства list не используются, а все недостатки сохраняются (бóльшие накладные расходы по памяти, частые вызовы аллкатора, фрагментация памяти, большое число кеш-промахов).
Почти единственный вариант, когда list может быть оправдан для queue, — это когда хочется зачем-то гарантировать маленькие аллокации под элементы, так как deque аллоцирует блоками и не предоставляет интерфейса для настройки их размера.
Это какие-то вырожденные случаи, когда, например, есть миллионы очередей, в каждой из которой находится не больше одного элемента, и хочется сэкономить память ценой более медленной работы.
Здравствуйте, rg45, Вы писали:
К>>Внезапно, есть такая штука, как семантика перемещения! К>>И у вектора она дешёвая.
R>Только вот вектор не совсем подходит по требованиям underlying контейнера в виду отсутсвия у него функции-члена pop_front (который используется внутри queue::pop). Конечно, этот недостаток можно без особого труда восполнить собственными силами, тем не менее, дополнительное телодвижение сделать нужно.
Ой, точно. Давненько не заглядывал в справочник
Что, однако, не мешает наколхозить.
pop_front() = erase(begin()).
Можно хакнуть STL и сделать специализацию queue<T, vector<T>>.
Вопрос: когда добавляю или удаляю элемент в queue, остальные элементы лежат на месте или копируются?
Мне нужно сделать FIFO из vector<UCHAR>, больших по размеру
Подходит для этого queue?
Или какой контейнер лучше использовать? (чтобы не было перекопирования элементов)
TW>Я правда не нашёл по ссылкам именно внутреннее устройство
Так как параметром там deque, то внутреннее утройство — список блоков.
Но дек может быть реализован сильно по-разному.
Например, я столкнулся с тем, что дек в в библиотеке для компилера в Студии намного медленнее работает, чем дек в библиотеке для g++.
Так что реально надо проверять и измерять.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Я не понимаю, почему deque по умолчанию используется как основа для queue?
У deque ведь больше возможностей
У него и pop_front и pop_back
А у queue только один pop
Например:
list — список. в листьях указатели на соседние элементы
map — тоже самое что лист, только ещё красно/чёрное дерево
vector — блок памяти, который выделен с избытком. Когда кончается память, происходит копирование всего объёма в новую память
Вот чем queue или deque отличается от list, я не понимаю
Я честно в гугле искал. Но он совсем плохо ищет последнее время
Здравствуйте, watchmaker, Вы писали:
W>Похоже ты считаешь, что из инвалидации итераторов как-то следует инвалидация ссылок на элементы, но это совсем не так. Операции на обоих границах deque никогда не инвалидируют ссылки на незатронутые элементы.
Более того, относительно недавно я сам сталкивался со случаем, когда инвалидируются итераторы, но объеты в памяти не перемещаются. Вот сейчас силюсь вспомнить, что это был за случай.
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, rg45, Вы писали:
R>Здравствуйте, watchmaker, Вы писали:
W>>Похоже ты считаешь, что из инвалидации итераторов как-то следует инвалидация ссылок на элементы, но это совсем не так. Операции на обоих границах deque никогда не инвалидируют ссылки на незатронутые элементы.
R>Более того, относительно недавно я сам сталкивался со случаем, когда инвалидируются итераторы, но объеты в памяти не перемещаются. Вот сейчас силюсь вспомнить, что это был за случай.
В деке или в хешмапе? В хешмапе итераторы инвалидируются при перестройке таблицы, при этом указатели на элементы стабильны
Здравствуйте, T4r4sB, Вы писали:
TB>В деке или в хешмапе? В хешмапе итераторы инвалидируются при перестройке таблицы, при этом указатели на элементы стабильны
Не помню, как отрезало Кажется, Went задавал вопрос и я сам же еще и отвечал. Возможно, что о хэшмапе речь и шла.
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, TailWind, Вы писали:
TW>Вопрос: когда добавляю или удаляю элемент в queue, остальные элементы лежат на месте или копируются?
Это адаптер.
Какой контейнер — так и хранятся.
Можешь свой тип контейнера подсунуть.
Здравствуйте, rg45, Вы писали:
R>Более того, относительно недавно я сам сталкивался со случаем, когда инвалидируются итераторы, но объеты в памяти не перемещаются. Вот сейчас силюсь вспомнить, что это был за случай.
TW>То есть чем list хуже чем queue в качестве FIFO?
Прежде всего тем, что list — это НЕ FIFO, а queue — это FIFO.
Можно, конечно, использовать и список как FIFO, но вероятность ошибки возрастает (например, кто-то другой начнет пихать в него не с той стороны). Ну короче, если по смыслу в коде нужна очередь, не понимаю, зачем пытаться применить там список . Тут даже безотносительно именно C++, а логически.
TW>>То есть чем list хуже чем queue в качестве FIFO? DP>Прежде всего тем, что list — это НЕ FIFO, а queue — это FIFO.
DP>Можно, конечно, использовать и список как FIFO, но вероятность ошибки возрастает (например, кто-то другой начнет пихать в него не с той стороны). Ну короче, если по смыслу в коде нужна очередь, не понимаю, зачем пытаться применить там список . Тут даже безотносительно именно C++, а логически.
Он просто закрывает часть функций листа и всё?
Глупо вводить отдельный класс в стандартную библиотеку только для этого
Здравствуйте, Videoman, Вы писали:
R>>Более того, относительно недавно я сам сталкивался со случаем, когда инвалидируются итераторы, но объеты в памяти не перемещаются. Вот сейчас силюсь вспомнить, что это был за случай.
V>std::unordered_map
Да, очень может быть. Я пытаюсь вспомнить, что за обсуждение это было и не могу. Поиском тоже не получилось. Что-то с памятью моей стало.
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, rg45, Вы писали:
R>А это как раз и зависит от того, какой используется underlying container. Когда по умолчанию используется std::deque, то при добавлении (но не при удалении) элемента могут происходить релокации и элементы очереди могут перемещаться или копироваться, все итераторы инвалидируются
я когда-то давно наткнулся в литературе на safe-итераторы, которые не инвалидируются, обрадовался, потом не смог даже нагуглить про существование оных. Понятно, что самому написать можно.
Здравствуйте, Кодт, Вы писали:
К>Внезапно, есть такая штука, как семантика перемещения! К>И у вектора она дешёвая.
Только вот вектор не совсем подходит по требованиям underlying контейнера ввиду отсутсвия у него функции-члена pop_front (который используется внутри queue::pop). Конечно, этот недостаток можно без особого труда восполнить собственными силами, тем не менее, дополнительное телодвижение сделать нужно.
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, T4r4sB, Вы писали:
TB>А очередь на основе вектора понимает, что если ты вытащил элемент из начала, то не обязательно весь хвост сдвигать каждый раз?
А она и не вытащит — ввиду отстустствия у вектора pop_front — это нужно допиливать самому. И тут уже все будет зависеть от того, как будет утсроен этот самый pop_front, ну и весь этот контейнер.
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, T4r4sB, Вы писали:
TB>А очередь на основе вектора понимает, что если ты вытащил элемент из начала, то не обязательно весь хвост сдвигать каждый раз?
Конечно, не понимает. Потому что queue<T,Container>.pop = Container.pop_front.
А стандартная реализация вектора резервирует место только в хвосте — и поэтому сдвигает всё при удалении из головы.
Если хочется, то можно написать рукодельный вектор, который будет оставлять пустое место в голове.
Только надо продумать правила реаллокации. Например, если в хвосте место кончилось, то в каких случаях надо увеличивать размер хранилища, а в каких — сдвинуть всё в голову.
Чистого кодинга там, думаю, на пару часов. Ещё день — на юниттесты и отладку.
Если упороться по всевозможным сочетаниям Copy/Move Constructible/Assignable — то ещё день уйдёт. Это я пессимистичную оценку даю.
Но опять-таки, мы же не знаем характерный размер очереди у ТС.
Если очередь из десятка векторов (пусть каждый из которых по стопятьсот значений), то сдвиг хвоста — "это не проблемы, а расходы".
И затраты на дек (который гарантированно будет выделять-удалять блоки на куче, хоть и не на каждую операцию) могут оказаться даже дороже.
Профилировать надо!
Перекуём баги на фичи!
Кажется, Went задавал вопрос и я сам же еще и отвечал. Возможно, что о хэшмапе речь и шла.
