Как устроен queue?
От: TailWind  
Дата: 25.03.23 09:14
Оценка:
Это связный список или он на основе вектора

Вопрос: когда добавляю или удаляю элемент в queue, остальные элементы лежат на месте или копируются?

Мне нужно сделать FIFO из vector<UCHAR>, больших по размеру
Подходит для этого queue?
Или какой контейнер лучше использовать? (чтобы не было перекопирования элементов)
Re: Как устроен queue?
От: DiPaolo Россия  
Дата: 25.03.23 09:24
Оценка: +1
Все описано тут 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?
Да.
Патриот здравого смысла
Re[2]: Как устроен queue?
От: TailWind  
Дата: 25.03.23 12:26
Оценка:
Большое спасибо

Я правда не нашёл по ссылкам именно внутреннее устройство
Там как пользоваться описание

Если у кого есть ссылка, поделитесь плиз
Re[3]: Как устроен queue?
От: LaptevVV Россия  
Дата: 25.03.23 12:31
Оценка:
TW>Я правда не нашёл по ссылкам именно внутреннее устройство
Так как параметром там deque, то внутреннее утройство — список блоков.
Но дек может быть реализован сильно по-разному.
Например, я столкнулся с тем, что дек в в библиотеке для компилера в Студии намного медленнее работает, чем дек в библиотеке для g++.
Так что реально надо проверять и измерять.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re: Как устроен queue?
От: rg45 СССР  
Дата: 25.03.23 14:10
Оценка: +4
Здравствуйте, 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, тогда все элементы будут лежать на месте и итераторы не будут инвалидироваться.
--
Не можешь достичь желаемого — пожелай достигнутого.
Отредактировано 28.03.2023 21:08 rg45 . Предыдущая версия . Еще …
Отредактировано 25.03.2023 14:44 rg45 . Предыдущая версия .
Отредактировано 25.03.2023 14:38 rg45 . Предыдущая версия .
Отредактировано 25.03.2023 14:23 rg45 . Предыдущая версия .
Отредактировано 25.03.2023 14:18 rg45 . Предыдущая версия .
Отредактировано 25.03.2023 14:15 rg45 . Предыдущая версия .
Re[2]: Как устроен queue?
От: TailWind  
Дата: 25.03.23 15:27
Оценка:
Я не понимаю, почему deque по умолчанию используется как основа для queue?
У deque ведь больше возможностей
У него и pop_front и pop_back
А у queue только один pop

Как-то не логично
Re[2]: Как устроен queue?
От: watchmaker  
Дата: 25.03.23 15:32
Оценка: 16 (1) +1
Здравствуйте, rg45, Вы писали:


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 тоже не входит в их число — ему вообще не нужны итераторы нижележащего контейнера.
Re[3]: Как устроен queue?
От: DiPaolo Россия  
Дата: 25.03.23 15:51
Оценка:
Clang — https://github.com/llvm/llvm-project/blob/main/libcxx/include/deque
MSVC — https://github.com/microsoft/STL/blob/main/stl/inc/deque
GCC — https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_deque.h

Так и не понял, что вам конкретно надо
Патриот здравого смысла
Re[4]: Как устроен queue?
От: TailWind  
Дата: 25.03.23 17:16
Оценка:
DP>Так и не понял, что вам конкретно надо

Концепция на пальцах

Например:
list — список. в листьях указатели на соседние элементы
map — тоже самое что лист, только ещё красно/чёрное дерево
vector — блок памяти, который выделен с избытком. Когда кончается память, происходит копирование всего объёма в новую память

Вот чем queue или deque отличается от list, я не понимаю

Я честно в гугле искал. Но он совсем плохо ищет последнее время
Re[3]: Как устроен queue?
От: rg45 СССР  
Дата: 25.03.23 18:11
Оценка:
Здравствуйте, watchmaker, Вы писали:

W>Похоже ты считаешь, что из инвалидации итераторов как-то следует инвалидация ссылок на элементы, но это совсем не так. Операции на обоих границах deque никогда не инвалидируют ссылки на незатронутые элементы.


Более того, относительно недавно я сам сталкивался со случаем, когда инвалидируются итераторы, но объеты в памяти не перемещаются. Вот сейчас силюсь вспомнить, что это был за случай.
--
Не можешь достичь желаемого — пожелай достигнутого.
Re[4]: Как устроен queue?
От: T4r4sB Россия  
Дата: 25.03.23 18:21
Оценка:
Здравствуйте, rg45, Вы писали:

R>Здравствуйте, watchmaker, Вы писали:


W>>Похоже ты считаешь, что из инвалидации итераторов как-то следует инвалидация ссылок на элементы, но это совсем не так. Операции на обоих границах deque никогда не инвалидируют ссылки на незатронутые элементы.


R>Более того, относительно недавно я сам сталкивался со случаем, когда инвалидируются итераторы, но объеты в памяти не перемещаются. Вот сейчас силюсь вспомнить, что это был за случай.


В деке или в хешмапе? В хешмапе итераторы инвалидируются при перестройке таблицы, при этом указатели на элементы стабильны
Re[5]: Как устроен queue?
От: rg45 СССР  
Дата: 25.03.23 18:22
Оценка:
Здравствуйте, T4r4sB, Вы писали:

TB>В деке или в хешмапе? В хешмапе итераторы инвалидируются при перестройке таблицы, при этом указатели на элементы стабильны


Не помню, как отрезало Кажется, Went задавал вопрос и я сам же еще и отвечал. Возможно, что о хэшмапе речь и шла.
--
Не можешь достичь желаемого — пожелай достигнутого.
Отредактировано 25.03.2023 18:24 rg45 . Предыдущая версия .
Re: Как устроен queue?
От: 3V Россия  
Дата: 25.03.23 19:14
Оценка:
Здравствуйте, TailWind, Вы писали:

TW>Вопрос: когда добавляю или удаляю элемент в queue, остальные элементы лежат на месте или копируются?

Это адаптер.
Какой контейнер — так и хранятся.
Можешь свой тип контейнера подсунуть.
Re[5]: Как устроен queue?
От: TailWind  
Дата: 25.03.23 19:51
Оценка:
То есть чем list хуже чем queue в качестве FIFO?

Или queue для мелких типов типа int?
Re[2]: Как устроен queue?
От: TailWind  
Дата: 25.03.23 19:52
Оценка:
3V>Это адаптер.
3V>Какой контейнер — так и хранятся.
3V>Можешь свой тип контейнера подсунуть.

Непонятно. Что он даёт?
Почему нельзя list вместо него использовать?
Для чего лишняя сущность?
Отредактировано 25.03.2023 19:53 TailWind . Предыдущая версия .
Re[4]: Как устроен queue?
От: Videoman Россия https://hts.tv/
Дата: 25.03.23 20:09
Оценка:
Здравствуйте, rg45, Вы писали:

R>Более того, относительно недавно я сам сталкивался со случаем, когда инвалидируются итераторы, но объеты в памяти не перемещаются. Вот сейчас силюсь вспомнить, что это был за случай.


std::unordered_map

References and pointers to either key or data stored in the container are only invalidated by erasing that element, even when the corresponding iterator is invalidated.
Отредактировано 25.03.2023 20:11 Videoman . Предыдущая версия .
Re[6]: Как устроен queue?
От: DiPaolo Россия  
Дата: 25.03.23 20:12
Оценка:
TW>То есть чем list хуже чем queue в качестве FIFO?
Прежде всего тем, что list — это НЕ FIFO, а queue — это FIFO.

Можно, конечно, использовать и список как FIFO, но вероятность ошибки возрастает (например, кто-то другой начнет пихать в него не с той стороны). Ну короче, если по смыслу в коде нужна очередь, не понимаю, зачем пытаться применить там список . Тут даже безотносительно именно C++, а логически.
Патриот здравого смысла
Re[7]: Как устроен queue?
От: TailWind  
Дата: 25.03.23 22:01
Оценка:
TW>>То есть чем list хуже чем queue в качестве FIFO?
DP>Прежде всего тем, что list — это НЕ FIFO, а queue — это FIFO.

DP>Можно, конечно, использовать и список как FIFO, но вероятность ошибки возрастает (например, кто-то другой начнет пихать в него не с той стороны). Ну короче, если по смыслу в коде нужна очередь, не понимаю, зачем пытаться применить там список . Тут даже безотносительно именно C++, а логически.


Он просто закрывает часть функций листа и всё?
Глупо вводить отдельный класс в стандартную библиотеку только для этого
Re[3]: Как устроен queue?
От: Teolog  
Дата: 26.03.23 06:46
Оценка: 8 (1) +3
TW>Непонятно. Что он даёт?
TW>Почему нельзя list вместо него использовать?
TW>Для чего лишняя сущность?

Потому что неэффективен и избыточен по функционалу. list предполагает выделение отдельного дескриптора с двумя указателями и самим элементом на каждый добавленый элемент, плюс служебная информация на каждом выделении — так что дергать кучу и получать 2*64+ ~24 байта мусора в нагрузку на каждый элемент. Минус кеш памяти, использовать — последнее дело.
deque — выделает и удаляет блоками — редко, поэтому добавление и удаление элемента, это по большей части инкремент/декремент счетчика. Плюс извлечение последовательно по памяти а значит скорее всего будет закешировано.
Re[5]: Как устроен queue?
От: rg45 СССР  
Дата: 26.03.23 07:33
Оценка:
Здравствуйте, Videoman, Вы писали:

R>>Более того, относительно недавно я сам сталкивался со случаем, когда инвалидируются итераторы, но объеты в памяти не перемещаются. Вот сейчас силюсь вспомнить, что это был за случай.


V>std::unordered_map


Да, очень может быть. Я пытаюсь вспомнить, что за обсуждение это было и не могу. Поиском тоже не получилось. Что-то с памятью моей стало.
--
Не можешь достичь желаемого — пожелай достигнутого.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.