Есть ли оптимизированная версия Map для того, когда на ключи выделяются строки?

Question

Я использую контейнер карты со строками в качестве ключей, но простое использование std::map<std::string, Value> означает, что ключи, скорее всего, не будут локальными по отношению друг к другу, что делает контейнер дорогим для использования в моем приложении из-за пропадания кэша.

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

Answer 1

Возможно, std::unordered_map может помочь вам, поскольку:

• ключи хешируются
• внутри, элементы хранятсяв корзинах, как в хеш-таблице
• время доступа постоянно

Дополнительные замечания:

Этот фрагмент позволяет понять расположение карты с помощью интерфейса сегмента:

    std::cout << "Bucket count: " << m.bucket_count() <<std::endl; 
    for (int i=0; i < m.bucket_count(); i++ ) {
        std::cout <<"   bucket "<< i << " : size " << m.bucket_size(i) << std::endl;
    }
    std::cout<<"Average bucket load:" <<m.load_factor()<<std::endl; 

Если вы с самого начала не предвидели достаточно сегментов и приводит ли динамический рост картык неоптимальной загрузке сегмента с большим количеством столкновений вы можете перефразировать карту:

m.rehash (2*m.bucket_count() );

Онлайн-демонстрация