Честно говоря, если делать велосипед, я бы делал что нибудь простое. Типа Circle Ring Buffer на диске. Chunk фиксированного размера (байтов 30-60). Большие записи разбивать на несколько chunk'ов и просто писать последовательно.

Структура хранения будет тривиальная. Поскольку FIFO и Circle Ring Buffer то не будет фрагментации и все общение с диском исключительно последовательное - максимальная производительность на любом жетком диске.

Объем кода для полноценной реализации, думаю пара сотен строк в максимуме. Недостаток и одновременно достоинство, место для хранилище нужно выделять заранее. Для пользовательского софта это был бы недостаток, для серверного достоинство.


Про очистку не понял.

Вообще, interface из первого поста на Queue совершенно не похож. Где Вы видели такие Queue, я вообще не понимаю ))) и что данный интерфейс должен делать - тоже )))

Зачем?
1. Банальный файл на диске и логика Circle Ring Buffer.
в конец пишем, из начала читаем.

2. Если нужно удаление и random доступ к содержимому, то банальная табличка например в SQL Lite
id, data
Низ и верх / начало и конец / head tail FIFO очереди банально храним в самом классе. Т.ч. никаких сортировок или min/max не требуется

Насколько я помню. Табличка в SQL Lite это физически Key-Value, NoSQL структура. Т.ч. даже даже дополнительный индекс primary key в случае SQL Lite будет не нужен )))

Что там "реализовывать" ?

Можно конечно поискать в google.com, но честно говоря, интерес представляет не реализация (дабы ее любой школьник за час закодировать может), а оптимизация под конкретные условия работы

а тут нужно знать эти самые условия, особой конкретики в топике нет

из интересных обсуждений, использование circle ring buffer'а на диске для видеопередачи (видеокамера продюсер + пара видеоплееров консьюмеры)
https://stackoverflow.com/questions/45869793/c-circular-buffer-using-large-disk-file/45870483