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

T>Скажем последние 16 пакетов.

Для такого количества полезность сортировки сомнительна. Простой линейный поиск, скорее всего, будет быстрее.

Как альтернативу я бы рассмотрел вариант с отсортированным вектором (или деком):
Скорее всего, пакеты будут приходить, в основном, по порядку, и можно будет просто добавлять в конец за O(1).
Если пришел опоздавший, то поиск места вставки — O(log N), сама вставка O(N) в худшем случае, а если опоздание небольшое, то двигать мало придется.
Если задержек мало, то будет выгоднее, чем постоянная сортировка.

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

T>Вопрос, больше общий, наверное. Есть задача построения обмена данными по сети по протоколу UDP. Каждый пакет имеет порядковый номер, так как гарантии очерёдности доставки нет. Соответственно, нужно держать некоторый буфер входящих пакетов и сортировать его. Скажем последние 16 пакетов. То есть задача сводится к постоянной вставке новых и удалению старых пакетов. std::map для этого вроде бы подходит (так как нужно не только номер но и сам пакет хранить), но не будет ли слишком накладно постоянно пересортировывать внутреннее RB-дерево? Или может есть какие другие проверенные и стандартные подходы к решению этой задачи? Гугл пока не помог, видимо потому что "правильно сформулированный вопрос — уже половина ответа", а я не могу его сформулировать

Во-первых, нужно понять, сколько пакетов одновременно сосуществуют в памяти. И насколько критично это сказывается на скорости. Логлинейный доступ с большим коэффициентом за счёт обращения к куче (std::map, boost::multi_index, и т.д. и т.п.), против, например, линейного доступа с маленьким коэффициентом за счёт статического резервирования места (std::vector).
Возможно, компромисс на низком уровне достигается использованием деревянного контейнера со специальным аллокатором.

Во-вторых, для сборки суперпакета из последовательных (ну да, с учётом обгонов) пакетов нужно сделать контейнер вот примерно с такой логикой

void set_window(uint limit); // размер окна - скажем, 16
uint window() const;

// индексы самого старого и самого свежего пакета, включительно.
uint oldest() const;
uint newest() const;
// инвариант: newest()+1-oldest() <= window()

bool exist(uint id); // return oldest() <= id && id <= newest() && реально_существует(id)

bool add(uint id, packet p); // return true если успешно добавлен, false если слишком старый
packet get(uint id); // при условии, что exist(id)

Напрашивается кольцевой буфер с произвольным доступом.
В самом простом виде, это или vector<optional<packet>>, устаревшие элементы которого надо выкидывать, или vector<pair<uint,packet>>, где проверка наличия просходит через сравнение запомненного идентификатора с желаемым.

Функции удаления пакетов из буфера, в общем, необязательны — они уберутся по мере устаревания.

const uint INVALID = ~0U;

uint newest_;
uint index_of_newest_, size_of_window_;

uint oldest_; // для работы буфера необязательно, но для удобства пользователя - вполне

vector<uint> ids_;
vector<packet> packets_;

uint index_of(uint id) const {
  if (id < oldest_) return INVALID;
  if (id > newest_) return INVALID;
  uint age = newest_ - id;
  uint index = (size_of_window_ + index_of_newest_ - age) % size_of_window_;
  return index;
}

bool exist(uint id) {
  uint index = index_of(id);
  return index != INVALID && ids_[index] == id;
}

bool add(uint id, packet p) {
  if (id + size_of_window_ < newest_) return false;
  if (newest_ < id) {
    uint forward = id - newest_;
    newest_ = id;
    index_of_newest_ = (index_of_newest_ + forward) % size_of_window_;
  }
  uint index = index_of(id);
  assert(index != INVALID);
  ids[index] = id;
  packets[index] = packet;

  // и обновить oldest
  oldest_ = max(size_of_window_, newest_ + 1) - size_of_window_;
  while(oldest_ < newest_ && !exist(oldest_)) oldest_++;

  return true;
}

Вот как-то так... (писал с листа, мог и накосячить, особенно на ±1).

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

L>Как альтернативу я бы рассмотрел вариант с отсортированным вектором (или деком):
L>Скорее всего, пакеты будут приходить, в основном, по порядку, и можно будет просто добавлять в конец за O(1).
L>Если пришел опоздавший, то поиск места вставки — O(log N), сама вставка O(N) в худшем случае, а если опоздание небольшое, то двигать мало придется.
L>Если задержек мало, то будет выгоднее, чем постоянная сортировка.

Можно вообще не держать ничего в памяти, если пакеты идут по порядку и мы точно знаем что опоздавших и потерянных нет. Если же после 33-го пакета пришел 35-й, то нужно буферизовать пока не появится 34-й, либо пока не наступит таймаут, либо пока буфер не заполнится.

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

<>

Да, кстати, можно же (если отвлечься от выжимания предельной скорости) сделать скользящее окно на обычном деке или даже векторе.

deque<optional<packet>> packets; // optional - потому что некоторые пакеты могут ещё отсутствовать
const uint window; // размер окна
uint oldest; // номер первого по счёту пакета

void add(uint id, packet p) {
  if (oldest + window < id) { // слишком новый пакет, будем двигать окно
    uint drop = min(window, id - oldest); // сколько пакетов устарело (возможно, устарели все)
    packets.erase(packets.begin(), packets.begin() + drop);
    packets.resize(window);
    oldest = id - window;
  }
  packets[id - oldest] = p;
}

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

S>>Походу, у вас никакой не реал-тайм
T>Если имеется в виду RTOS и QNX то да, у меня обычный Embedded Linux. Аллокатор скорее будет свой, так как embedded, хотя там куча высокоуровневой обвязки на Java будет (не моё решение), поэтому вот вообще не могу сказать по этому поводу.

S>>Что до вашего вопроса, то за время, пока вы его обсуждаете на RSDN, уже можно было написать несколько простейших бенчмарков
T>В лабораторных условиях хорошо получается смоделировать потерю пакетов, а в этом случае вся нагрузка уходит на функции восстановления, а не сортировки.

Я так понимаю, коллега, вы решаете задачу однонаправленной передачи данных?
Если есть Джава, передавайте пакеты ей — она сконструирует файл или сообщение без rt по размеру и пришедшим пакетам...
Ваша задача, быстрее выскребать пакеты из IP стэка, поскольку иначе начнете терять в нем.
Как-то так.

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

T>Вопрос, больше общий, наверное. Есть задача построения обмена данными по сети по протоколу UDP. Каждый пакет имеет порядковый номер, так как гарантии очерёдности доставки нет. Соответственно, нужно держать некоторый буфер входящих пакетов и сортировать его. Скажем последние 16 пакетов. То есть задача сводится к постоянной вставке новых и удалению старых пакетов. std::map для этого вроде бы подходит (так как нужно не только номер но и сам пакет хранить), но не будет ли слишком накладно постоянно пересортировывать внутреннее RB-дерево? Или может есть какие другие проверенные и стандартные подходы к решению этой задачи? Гугл пока не помог, видимо потому что "правильно сформулированный вопрос — уже половина ответа", а я не могу его сформулировать
Почему не использовать обычный list? Операция вставки в хвост и удаления головы самая частая и дешевая. Операция вставки "пропущенного" или "потерянного" пакета достаточно дешевая.
Зачем заморачиваться с сортировками и перебалансировками?