Здраствуйте!

Очередь стандартная, FIFO, в хвост кладём, из гривы извлекаем. Обычно deque использую, но чот решил у народу поинтересоваться, может есть что-то пооптимальнее сейчас?

Мне тут как-то говорили, что новая priority_queue неплоха, но мне не нужны приоритеты, надо извлекать в том порядке, как положили

спасибо за то что поинтересовались нашей вакансией
всего хорошего!

	Скрытый текст
	вам отказали на этапе первычного скринига до собеседования вы даже не дошли

M>Очередь стандартная, FIFO, в хвост кладём, из гривы извлекаем. Обычно deque использую, но чот решил у народу поинтересоваться, может есть что-то пооптимальнее сейчас?
M>Мне тут как-то говорили, что новая priority_queue неплоха, но мне не нужны приоритеты, надо извлекать в том порядке, как положили
1. Есть стандартная очередь.
2. Проще всего использовать список.
Если очередь не очень интенсивно нагружается, то проблем никаких.

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

M> Очередь стандартная, FIFO, в хвост кладём, из гривы извлекаем. Обычно deque использую, но чот решил у народу поинтересоваться, может есть что-то пооптимальнее сейчас?
Ты уже сделал перф-тесты и реально увидел, что у тебя deque является узким местом? Иначе — фигнёй страдаешь. Что значит "оптимальнее"? По памяти? По пропускной способности? По latency? По jitter?

С т.з. алгоритмической сложности — кольцевой буфер с фиксированным размером оптимальнее. Правда размер фиксированный... подойдёт ли тебе, хз. В стандарте нет прямо уж готового, но легко сделать на vector + пара индексов.
Для совсем low latency нужно смотреть в сторону disruptor.

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

LVV>1. Есть стандартная очередь.
queue реализован поверх deque

LVV>2. Проще всего использовать список.
проще, но не оптимальнее

Как уже отметили, кольцевой буфер для очереди — самое лучшее. Можно сделать его расщиряющимся (не обязательно фиксированного размера). deque имеет недостаток, что он "плавает" по памяти. При добавлении элементов выделяет новый фрейм, при удалении очищает старый. Для LIFO deque идеален.

Здравствуйте, sergii.p, Вы писали:

SP>Как уже отметили, кольцевой буфер для очереди — самое лучшее.

Ну, тут тоже есть кое-какие вопросы — например, о времени жизни объектов, извлекаемых из очереди. Тут традиционно быстродейиствие выходит против универсальности. Можно реализовать так, а можно эдак.

LVV>>1. Есть стандартная очередь.
SP>queue реализован поверх deque
А то я не знаю...
LVV>>2. Проще всего использовать список.
SP>проще, но не оптимальнее
Оптимальность бывает разная.
Есть оптимальность программы, а есть оптимальность программиста.
Если программа не нуждается в вылизывании шероховатостей, то программисту проще и быстрее (сиречь оптимальнее) просто использовать список.
SP>Как уже отметили, кольцевой буфер для очереди — самое лучшее. Можно сделать его расщиряющимся (не обязательно фиксированного размера). deque имеет недостаток, что он "плавает" по памяти. При добавлении элементов выделяет новый фрейм, при удалении очищает старый. Для LIFO deque идеален.
Смотря как он реализован.
А то я нарвался на реализацию от микрософта лет 10 назад, которая была в 5 раз медленнее реализации в gcc

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

LVV>1. Есть стандартная очередь.

Это же какая? std::queue? Это просто адаптер, у которого база по дефолту дека


LVV>2. Проще всего использовать список.

std::list? Что, правда, что ли?


LVV>Если очередь не очень интенсивно нагружается, то проблем никаких.

А если нагружается?

ЗЫ блин, профессор, ваш ответ был максимально бесполезен, и даже вреден

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

SP>>Как уже отметили, кольцевой буфер для очереди — самое лучшее.

R>Ну, тут тоже есть кое-какие вопросы — например, о времени жизни объектов, извлекаемых из очереди. Тут традиционно быстродейиствие выходит против универсальности. Можно реализовать так, а можно эдак.

А можно раскрыть мысль? Какие проблемы с объектами в очереди? И как оно влияет на тип очереди, который лучше использовать?

M>ЗЫ блин, профессор, ваш ответ был максимально бесполезен, и даже вреден
При твоих исходных — получил именно то, что спросил.
Написал бы сразу про нагрузку — про кольцевой буфер получил бы ответ
А так твой вопрос сильно похож на вопрос неопытного джуна...

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

LVV>Оптимальность бывает разная.
LVV>Есть оптимальность программы, а есть оптимальность программиста.
LVV>Если программа не нуждается в вылизывании шероховатостей, то программисту проще и быстрее (сиречь оптимальнее) просто использовать список.

С тем же успехом можно использовать деку, и это будет имхо быстрее работать в рантайме. И ничего тут вылизывать не нужно. Плохие советы лучше своим студентам раздавайте, нам не надо

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

M>> Очередь стандартная, FIFO, в хвост кладём, из гривы извлекаем. Обычно deque использую, но чот решил у народу поинтересоваться, может есть что-то пооптимальнее сейчас?
·>Ты уже сделал перф-тесты и реально увидел, что у тебя deque является узким местом?

Нет конечно, ничего я не делал, я ещё ни строчки кода не написал


·>Иначе — фигнёй страдаешь.

Так точно!


·>Что значит "оптимальнее"? По памяти? По пропускной способности? По latency? По jitter?

Оптимальнее в совокупности

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

M>>ЗЫ блин, профессор, ваш ответ был максимально бесполезен, и даже вреден
LVV>При твоих исходных — получил именно то, что спросил.

Нет. Ты даже ни одного конкретного типа не привел, отделался общими словами. А вопрос был про конкретные типы из современной стандартной библиотеки


LVV>Написал бы сразу про нагрузку — про кольцевой буфер получил бы ответ

А нагрузка всегда подразумевается, не?


LVV>А так твой вопрос сильно похож на вопрос неопытного джуна...

Не важно, какой вопрос, важно, какой ответ. Твой ответ похож на ответ неопытного джуна, вот это и плохо

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

M>А можно раскрыть мысль? Какие проблемы с объектами в очереди? И как оно влияет на тип очереди, который лучше использовать?

Ну допустим, у нас очередь объектов с нетривиальным конструированием и разрушением. Что происходит когда мы извлекаем объект такого типа из очереди? Просто передвинуть индекс не вариант, наверное, нужно же еще и корректно завершить время жизни объекта, так ведь? А потом, когда до этого элемента снова по кругу дойдет очередь, создать на его месте новый объект. Наверное, самое простое, что можно придумать — это оборачивать все элементы очереди в std::optional — чтоб не глотать пыль с буферами и с placement new/delete. Такой вариант будет универсальным как для простых, так и для сложных типов. Но как такая реализация повлияет на производительность очередей простых типов? Можно вместо std::optional использовать шаблонную обертку со специализациями, которая для сложных типов будет использовать std::optional, а для простых не будет делать ничего (вырожденная пустышка). Но ведь это же нужно еще делать, это не в одну строчку решение.

LVV>>Написал бы сразу про нагрузку — про кольцевой буфер получил бы ответ
M>А нагрузка всегда подразумевается, не?
Нет. Ситуации бывают самые разные.
LVV>>А так твой вопрос сильно похож на вопрос неопытного джуна...
M>Не важно, какой вопрос, важно, какой ответ. Твой ответ похож на ответ неопытного джуна, вот это и плохо
Я с тебя фигею! Неважно, какой вопрос — А-БАЛ-ДЕТЬ!

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

M>Очередь стандартная, FIFO, в хвост кладём, из гривы извлекаем. Обычно deque использую, но чот решил у народу поинтересоваться, может есть что-то пооптимальнее сейчас?

https://en.cppreference.com/w/cpp/container/queue

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

M>Очередь стандартная, FIFO, в хвост кладём, из гривы извлекаем. Обычно deque использую, но чот решил у народу поинтересоваться, может есть что-то пооптимальнее сейчас?

Размер элемента, цена операций перемещения, характерный размер очереди, требования к многопоточности, требования к производительности — это всё, конечно же, никакого значения не имеет?

Если есть гарантии на максимальный размер очереди (или такие гарантии можно волюнтаристски ввести), то boost::circular_buffer, либо самому портировать / скопипастить / наколхозить поверх массива/вектора.
Он несложный, хотя и требует тщательности.

Если очередь не является узким местом (профилирование наше всё! флеймграф умеешь строить?) — то std::queue и не морочить себе голову.
Чем более нестандартные вещи применяются, тем труднее поддерживать программу.
Прежде всего потому, что начинает протекать абстракция:
— вопросы к коллегам и к себе из будущего в прошлое: что хотел сказать автор? почему здесь именно такая реализация? можно ли её безболезненно заменить на другую реализацию?
— как далеко надо растащить привязку всего остального кода к этой реализации? или придётся спрятать детали за шаблоном / пимплом / виртуальными функциями?

А может быть, очередь уже есть готовая в инфраструктуре — файловые буферы, сокеты, тредпулы там... И второй слой буферизации попросту не нужен?
Или это переписывание первого слоя буферизации, так как дефолтная реализация в инфраструктуре не устроила по производительности?

M>Мне тут как-то говорили, что новая priority_queue неплоха, но мне не нужны приоритеты, надо извлекать в том порядке, как положили

Что значит "неплоха"? Во-первых, это не контейнер, а обёртка (и обычно — над вектором). Во-вторых, она, действительно, делает совсем другое.
Как вообще пришло в голову её вспомнить? Просто потому что ..._queue?

К>Как вообще пришло в голову её вспомнить? Просто потому что ..._queue?

каждый новичек после 20 лет программирования на С++ хочет выйти за границы своего говнокодинга и притянуть что то эдакое в свое поделие

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

R>Ну допустим, у нас очередь объектов с нетривиальным конструированием и разрушением. Что происходит когда мы извлекаем объект такого типа из очереди? Просто передвинуть индекс не вариант, наверное, нужно же еще и корректно завершить время жизни объекта, так ведь? А потом, когда до этого элемента снова по кругу дойдет очередь, создать на его месте новый объект. Наверное, самое простое, что можно придумать — это оборачивать все элементы очереди в std::optional — чтоб не глотать пыль с буферами и с placement new/delete.

Мрачный подход. Хранить булев флажок в каждом элементе только ради того, чтоб меньше писать — как-то это не вяжется с вопросами производительности.

R>Такой вариант будет универсальным как для простых, так и для сложных типов. Но как такая реализация повлияет на производительность очередей простых типов? Можно вместо std::optional использовать шаблонную обертку со специализациями, которая для сложных типов будет использовать std::optional, а для простых не будет делать ничего (вырожденная пустышка). Но ведь это же нужно еще делать, это не в одну строчку решение.

В совсем немножко строчек. Например, так.

template<class T> struct mandatory {
  static_assert(std::is_trivial_v<T>);
  T t_;

  // минимальный апи, общий с std::optional

  auto& constexpr operator*() noexcept { return t_; }
  auto& constexpr operator*() const noexcept { return t_; }

  void reset() noexcept {}
  void reset(auto&& t) { t_ = std::forward<decltype(t)>(t); }
};

template<class T> using buffer_item_t = std::conditional_t<std::is_trivial_v<T>, mandatory<T>, std::optional<T>>;

https://old.reddit.com/r/cpp/comments/18x1mty/can_we_claim_that_stddeque_is_the_most_underrated/