CODEWITHSUNDEEP
c++dictionarymemory
Anne Quinn
Anne Quinn

Reputation: 13002

Is there an optimized version of Map for when the keys are allocated strings?

I'm using a map container with strings as keys, but simply using std::map<std::string, Value> means the keys are likely to not be local to one another, making the container costly to use in my application due to cache misses.

Is there an existing solution to this problem that keeps each individual key's data contained to a single contagious pool of memory?

Upvotes: 2

Views: 74

Answers (1)

Christophe
Christophe

Reputation: 73376

Probably, std::unordered_map could help you, since:

  • keys are hashed
  • internally, the items are stored in buckets, like in a hash table
  • access time is constant

Additional remarks:

THis snippet allows you to understand the layout of the map using the bucket interface: 

    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;

If you didn't foresee from the start enough buckets, and if the dynamic growth of the map leads to a suboptimal bucket load with too many collisions, you can rehash the map:

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

Online demo

Upvotes: 3

Related Questions