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

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

Возможно, тебе подойдёт куча. Операция произвольного доступа по ключу (порядковому номеру) тебе всё равно вряд ли нужна. А поиск минимума (самого раннего из последних 16 сообщений), возможно, пригодится.