Задача. Идёт поток проштампованных временем сообщений. Хотя сообщения обычно приходят

Question

Задача. Идёт поток проштампованных временем сообщений. Хотя сообщения обычно приходят

в правильном порядке, они могут приходить и в неправильном. Надо их расскладывать сообразно временному порядку. Вопрос. Какую структуру данных для этого имеет смысл применить?

#c++ #embedded #programming #russian

0

11.04.2022

15 ответов

5 просмотров

Kelbon

Oleksandr
Зависит от того что с этими сообщениями будет даль...

priority queue перекладывать же будет

0

11.04.2022

Aleksander Spichak

set

0

11.04.2022

Constantine Drozdov

хм... а зачем нам порядок сообщений?

0

11.04.2022

Alexander Karaev

Сортированный вектор? Если неправильный порядок - редкий, то и вставка не в конец будет редкой

0

11.04.2022

Constantine Drozdov

поясню: "раскладывать сообразно временному порядку" немного хамелеон внутрь, черный ящик декларирует своё внутреннее устройство, когда должен декларировать внешний интерфейс; если предположить (а) сообщения приходят позже нормы, потому что отдельные сообщения запаздывают (статистически - редко) (б) через много времени, достаточное для прибытия последнего опоздавшего, нас попросят перечислить всех прибывших (в) многопоточности нет то вроде бы правильный ответ такой: держим две очереди, одну обычную, другую PQ (для опоздавших) на выходе выполняем аналог std::merge

0

11.04.2022

Aleksander Spichak

Alexander Karaev
Сортированный вектор? Если неправильный порядок - ...

ну вставка в центр это O(n) , а btree это грубо говоря дерево векторов

0

11.04.2022

netricks Автор вопроса

А чего такого он делает?

0

11.04.2022

Constantine Drozdov

netricks
А чего такого он делает?

элементы двигает, разумеется, как вектор

0

11.04.2022

Constantine Drozdov

Constantine Drozdov
поясню: "раскладывать сообразно временному порядку...

в общем, this, и можете побенчмаркать - добавление десятка миллионов элементов по одному в порядке возрастания в priority_queue вроде бы сработает быстрее, чем в std::list :)

0

11.04.2022

Aleksander Spichak

netricks
А чего такого он делает?

https://github.com/microsoft/STL/blob/52505b9d3249c50b33eb22152a1f18f208ea2959/stl/inc/deque#L1365

0

11.04.2022

netricks Автор вопроса

Aleksander Spichak
https://github.com/microsoft/STL/blob/52505b9d3249...

А в чём криминал?

0

11.04.2022