Есть такое:
// Это топ.
// Тут просто список записей, где они часто из середины прыгают в начало
// Число записей - 100M.
// Список фтопку. Воткните любую структуру данных, которая обеспечит быстрое (хотя-бы логарифм) перемещение объекта из середины в некое начало - например std::map по ключу rating.
// и которая позволит пробежать все элементы от начала до конца в порядке увеличения rating
// Список тут является простейшим примером, это обеспечивающим, но явно не хранящем значение ratings (само оно неинтересно, интересно только относительное положение).
std::list<Record> top;
// А это чтобы быстро по ID получать запись.
std::map<uint32_t, std::list<Record>::iterator > ids;
Первый - это не список, а любая структура данных, которая хотите, которая позволит быстро получить первые 1000 записей. Хоть дерево с ключом 'timestamp_microsec', тогда первые 1000 записей — первые 1000 самых больших ключей. Первый контейнер нужен для решения тупой задачи «посмотреть топ 1000».
Второй контейнер нужен для рандом акцесса по ID.
Задача Хочется по id не просто достать запись, что сейчас сделано на std::map, а ещё и получить порядковый номер этой записи в первом контейнере — её место в топе от начала.
Решение: после каждого переноса записи из середины в начало top, пробегать по всему top со счётчиком и сохранять в Record её позицию от начала (текущее значение счётчика). Но это медленно, за такое сразу расстреливают.
P.S.
В посте нет кода, который относится к реальности или работает.
В посте нет кода, который надо сохранить в неизменном виде и обеспечить его работоспособность.
Список приведён только в качестве примера тупой структуры, индекс от начала в которой нужно получить и которая хранит последовательность и поддерживает быстрое извлечение из середины и вставку в начало (если хранить итератор на эту середину, например).
