привет всем, возникла задача, есть вот такой интерфейс:

struct storage{
    void insert(std::string& str) = 0;
    void erase(uint64_t index) = 0 ;
    std::string& get(uint64_t index) = 0;
};

Задача с виду проста, нужно вставлять в сортированный контейнер а удалять и получать по индексу.
В идеале нужен std::set только с доступом по индексу. Получается при каждой новой вставке нужно
получать std::distance и привязывать его к вновь вставленной записи.
На практике при миллионе записей работает очень медленно, у кого есть идея решения буду премногоблагодарен ).