2

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?

Anne Quinn
  • 12,609
  • 8
  • 54
  • 101

1 Answers1

3

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

Christophe
  • 68,716
  • 7
  • 72
  • 138
  • I doubt, how long the code which you demoed online would be available in future. Therefore, it might be a good idea to past it in SO itself. (*IMHO*) :) – JeJo Nov 17 '18 at 17:08
  • @JeJo Thank you for your remark! In fact, the most relevant part of the code in regard of the question is already in the post (for exactly the reason that you mention). The remainder is rather trivial. This being said, ideone, is a site from a a well established company that keeps the code forever: and you can find on SO lots of old posts back to 2012 where the code is still accessible :-) – Christophe Nov 17 '18 at 18:24