Вопрос такой: у меня есть клиенты, подключенные к одному серверу. Клиенты сбрасывают свои состояния, из которых я затем получаю пару <client_id, status_id>. Эта пара является ключом в std::map. status_id это uint64, которые чаще всего идут последовательно. Такое случается не всегда (статусы могут меняться и т.д.), но очень часто.
До тех пор, пока общий объем данных не велик, всё работает нормально. Но с увеличением объема данных, получаю потерю производительности. Где-то на глаза попадалось упоминание, что операция map.insert [key, value] экспоненциальная. Но где-то так у меня и получается.
Из готовых решений я так понимаю, есть boost:range. Утверждают, что работает быстрее. Но в проекте буст не используется и тянуть его только из-за этого не сильно хочется.
Вопрос получается простой: как можно ускорить вставку в std::map? Перебирать по итераторам и искать совпадения? Сортировать как-то хэши? Вообще буст построен повержу std::map? или у них своя структура какая-то для range?