Сообщение Re: Как устроен queue? от 25.03.2023 14:10
Изменено 25.03.2023 14:23 rg45
Re: Как устроен queue?
Здравствуйте, 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>Это связный список или он на основе вектора
В основе 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, тогда все элементы будут лежать на месте и итераторы не будут инвалидироваться.
Re: Как устроен queue?
Здравствуйте, 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>Это связный список или он на основе вектора
В основе 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, тогда все элементы будут лежать на месте и итераторы не будут инвалидироваться.