Вопрос: когда добавляю или удаляю элемент в queue, остальные элементы лежат на месте или копируются?
Мне нужно сделать FIFO из vector<UCHAR>, больших по размеру
Подходит для этого queue?
Или какой контейнер лучше использовать? (чтобы не было перекопирования элементов)
Все описано тут 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?
Да.
TW>Я правда не нашёл по ссылкам именно внутреннее устройство
Так как параметром там deque, то внутреннее утройство — список блоков.
Но дек может быть реализован сильно по-разному.
Например, я столкнулся с тем, что дек в в библиотеке для компилера в Студии намного медленнее работает, чем дек в библиотеке для g++.
Так что реально надо проверять и измерять.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, 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, тогда все элементы будут лежать на месте и итераторы не будут инвалидироваться.
Я не понимаю, почему deque по умолчанию используется как основа для queue?
У deque ведь больше возможностей
У него и pop_front и pop_back
А у queue только один pop
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 тоже не входит в их число — ему вообще не нужны итераторы нижележащего контейнера.
Например:
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++, а логически.
Он просто закрывает часть функций листа и всё?
Глупо вводить отдельный класс в стандартную библиотеку только для этого
TW>Непонятно. Что он даёт? TW>Почему нельзя list вместо него использовать? TW>Для чего лишняя сущность?
Потому что неэффективен и избыточен по функционалу. list предполагает выделение отдельного дескриптора с двумя указателями и самим элементом на каждый добавленый элемент, плюс служебная информация на каждом выделении — так что дергать кучу и получать 2*64+ ~24 байта мусора в нагрузку на каждый элемент. Минус кеш памяти, использовать — последнее дело.
deque — выделает и удаляет блоками — редко, поэтому добавление и удаление элемента, это по большей части инкремент/декремент счетчика. Плюс извлечение последовательно по памяти а значит скорее всего будет закешировано.
Здравствуйте, Videoman, Вы писали:
R>>Более того, относительно недавно я сам сталкивался со случаем, когда инвалидируются итераторы, но объеты в памяти не перемещаются. Вот сейчас силюсь вспомнить, что это был за случай.
V>std::unordered_map
Да, очень может быть. Я пытаюсь вспомнить, что за обсуждение это было и не могу. Поиском тоже не получилось. Что-то с памятью моей стало.
Кажется, Went задавал вопрос и я сам же еще и отвечал. Возможно, что о хэшмапе речь и шла.
