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

vector<int> vec;
vec.resize(10);

vec[2] = ... // пакет с айди 2
vec[5] = .. // пакет с айди 5

S>vector<int> vec;
S>vec.resize(10);
S>vec[5] = .. // пакет с айди 5

vec[19937] = .. // пакет с айди 19937?

// Create a circular buffer with a capacity for 3 integers.
boost::circular_buffer<int> cb(3);

// Insert threee elements into the buffer.
cb.push_back(1);
cb.push_back(2);
cb.push_back(3);

int a = cb[0];  // a == 1
int b = cb[1];  // b == 2
int c = cb[2];  // c == 3

// The buffer is full now, so pushing subsequent
// elements will overwrite the front-most elements.

cb.push_back(4);  // Overwrite 1 with 4.
cb.push_back(5);  // Overwrite 2 with 5.

// The buffer now contains 3, 4 and 5.
a = cb[0];  // a == 3
b = cb[1];  // b == 4
c = cb[2];  // c == 5

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

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)

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;
}

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;
}