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

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

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

Размер элемента — не мерял, но там определенно что-то хранится .

Суть в том, что мне надо разобрать JSON в другие иерархиеческие объекты. Использую nlohman json. Тупой подход в лоб — это использовать рекурсию, мне он не очень нравится — если мне подсунут жирный JSON, то у меня может не хватить стека. Для этого я решил сделать всё через очередь — если встречаю обычное поле bool/int/float/string — то разбираю на месте, если object/array, то создаю целевой object/array, и кладу эту пару в очередь для дальнейшего разбора, и в цикле выбираю оттуда и делаю разбор содержимого. Тут если жирный JSON, то у меня конечно может не хватит памяти для создания целевого объекта (или даже не хватит памяти для разбора текста в nlohman::json ноды), но эта ситуация поддаётся контролю, и я могу вернуть ошибку, или кинуть исключение, которое выше поймаю, либо исключение будет кинуто при создании целевого объекта, либо при помещении пары в очередь.


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

Гарантий никаких нет


К>Если очередь не является узким местом (профилирование наше всё! флеймграф умеешь строить?) — то std::queue и не морочить себе голову.

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


К>Чем более нестандартные вещи применяются, тем труднее поддерживать программу.

Да, нестандартных не хочется. А стандартных не особо много, но может, что-то в новых стандартах по сравнению третьими плюсиками появилось хорошего. Собсно, вариантов кроме list и deque (или queue на deque) вроде как и нет, но list вроде как под каждую ноду в память лазает — это очевидная пессимизация сразу


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

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

Ага

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

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

M>·>Иначе — фигнёй страдаешь.
M>Так точно!
Ну тогда std::multimap используй для очереди. Не знаю как, не знаю зачем, но фигня будет знатная.

M>·>Что значит "оптимальнее"? По памяти? По пропускной способности? По latency? По jitter?
M>Оптимальнее в совокупности
Такого не бывает в природе.

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

·>Потом перф-тесты, поиск узких мест, разные варианты оптимизации и снова замеры перформанса, замеряя эффекты применённых оптимизаций.

performance тесты нужны, когда не понимаешь (или нет возможности понять), что внутри происходит. Если результаты не вписываются в твои ожидания, то или тесты написаны криво, или понимание не совпадает с реальностью. Просто писать тесты потому что так надо — это какой-то карго культ.
Тут то задача проще. Нужно все доступные контейнеры проверить на алгоритм FIFO. Внутреннее устройство контейнеров всем примерно понятно.

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

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

проблема не очень понятна. Например перед std::vector аналогичная задача стоит. Но она удовлетворительно решается внутри. При удалении элемента с хвоста индекс не просто сдвигается, а вызывается ещё деструктор. Тоже самое при повторном добавлении. Индекс свдинули, по памяти вызвали placement new.

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

SP>При удалении элемента с хвоста индекс не просто сдвигается, а вызывается ещё деструктор.

Ну зашибись, а что будет, когда дело дойдет до деструктора контейнера, который служит хранилищем очереди? И как проинициализировать этот контейнер при создании пустой очереди? Ну и доп. вопрос: а что если тип элемента очереди не имеет дефолтного конструктора, как создать пустую очередь?

P.S. Все сказанное мной в этой ветке актуально только в том случае, если я правильно истолковал исходное предложение

Автор: ·
Дата: 02.01 13:24

"vector + пара индексов". На самом деле, высказыание не очень детализировано и можно понять двояко. Принципиальный момент: вектор ЧЕГО предлагается использовать.

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

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

ох, попадись ты мне на собеседовании...

марти кодит с 2001 года как минимум, судя по форуму, это ж синьер или джун недоучка?
и не знает как или что выбрать лучше в очередь ? лол

а вообще это типичные ответы HR
я то причем

Откуда Китай Hong Kong

точно не попадусь

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

M>Суть в том, что мне надо разобрать JSON в другие иерархиеческие объекты. Использую nlohman json. Тупой подход в лоб — это использовать рекурсию, мне он не очень нравится — если мне подсунут жирный JSON, то у меня может не хватить стека. Для этого я решил сделать всё через очередь — если встречаю обычное поле bool/int/float/string — то разбираю на месте, если object/array, то создаю целевой object/array, и кладу эту пару в очередь для дальнейшего разбора, и в цикле выбираю оттуда и делаю разбор содержимого. Тут если жирный JSON, то у меня конечно может не хватит памяти для создания целевого объекта (или даже не хватит памяти для разбора текста в nlohman::json ноды), но эта ситуация поддаётся контролю, и я могу вернуть ошибку, или кинуть исключение, которое выше поймаю, либо исключение будет кинуто при создании целевого объекта, либо при помещении пары в очередь.

Искусство задавать правильные вопросы. (И искусство задавать правильные встречные вопросы).

Но я тогда задам второй встречный вопрос.
Почему очередь, если программно тут нужен стек?
Ведь наивный алгоритм — на стеке вызовов. Тогда рефакторинг состоит в замене стека вызовов на стек данных. Разве нет?
Или там "автомат калашникова — устройство, преобразующее магазин в очередь"?

Кстати, парсер — дом или сакс? Нлохман умеет в оба.

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

К>Искусство задавать правильные вопросы. (И искусство задавать правильные встречные вопросы).

Оба два искусства, мало кто владеет хотя бы одним, и лишь немногие владеют обоими


К>Но я тогда задам второй встречный вопрос.
К>Почему очередь, если программно тут нужен стек?

Я не могу знать, какой по жирности JSON мне подсунут на вход. Могут подсунуть такой JSON, на котором вылетит любой стек, даже если я задам кастомный размер (под виндой вместо дефолтных 100Мб — гиг, например).
Преобразовав стек в очередь я имею больший контроль над тем, что происходит. Если на раслабоне, то вылечу по bad_alloc, но могу задавать и свои ограничения.

Плюс, я конвертирую JSON в squirrel объекты (таблицы и массивы), там на VM есть свои ограничения (в тч что я могу задать при старте), она может упасть раньше, но я это поймаю плюсовыми средствами.

Если говорить о том, что использовать — стек или очередь в плюсиках — ну, тут я просто иду по накатанной, задачек на очередь прорешано больше, чем на стек Хотя, после намёков, стек так и просится, но уже лень


К>Ведь наивный алгоритм — на стеке вызовов. Тогда рефакторинг состоит в замене стека вызовов на стек данных. Разве нет?
К>Или там "автомат калашникова — устройство, преобразующее магазин в очередь"?

Типа того

На самом деле да, стек конечно больше просится, но у меня очередь как-то уже привычна, вот и запилил на ней
В принципе, я думаю, если я в своей готовченко поменяю очередь на стек, то в остальных местах много менять и не придётся. Может, даже производительность померяю и того и другого

К>Кстати, парсер — дом или сакс? Нлохман умеет в оба.

Дом

Со стеком вроде всё понятно — std::stack на базе std::vector в принципе вполне нормас и сто лет назад и сейчас.

А таки, если принять, что для данной задачи нужна именно очередь — какую очередь стоит использовать сейчас?