Выделение случайного времени в фиксированном интервале

Нормальный std::map (или std::unordered_map) может это сделать. У вас есть несколько вариантов того, как это сделать:

• Сохранение нормального ключа, где вы копируете значения по мере необходимости
• Сохранение нормального значения ключа, но где value - указатель на фактические данные, которые могут быть разделены, необязательно с помощью std::shared_ptr
• Используйте некоторую структуру (возможно, std::tuple) для сбора ключей (хотя, вероятно, это больше проблем с обработкой этого чем это стоит, ничего не рекомендую)
• Используйте Boost multi-index container

С Boost у вас есть готовое решение, которое вы можете просто используйте, и если вы уже используете Boost в своем проекте (это отличный набор библиотек и хорошо дополняет стандартную библиотеку), я думаю, что это решение не требует выбора.