Need const_map

I love STL containers in C++. They're so much better in general to work with than their C counterparts. The bit that's missing though is an instantiation-time optimized version of map.

Take, for instance, reading a set of commands at startup from a set of dynamically loaded plugins. It's not going to change, in this hypothetical case, because we neither load nor unload plugins after startup. But it's dynamic in the sense that we do not know it at compile time - so doing something like gperf to generate a perfect hash is out of the question.

But why should we pay the lookup cost on a dynamic container for every lookup if I can determine, based on program flow, that the contents of the container are not going to change once it's instantiated.

Something like:

const perfect_map(some_dynamic_map_I_built);

Where the constructor would do a perfect hash generation once, and the map itself would be const (not allowing contents to be added or removed) but was full of references to objects which might not be const. Right? I can't be the only one wanting this, am I? 

2 Comments

  1. [1]   Jon
    May 17, 2011 at 02:13 PM

    You're talking about unordered_map, I hope? Pre-0x STL has no hash map, just one built on an a (typically-RB) tree. Beyond that, it seems a good question. Have you estimated how much performance payoff this would buy you, though? With a typical dataset, check the number of buckets your unordered_map ends up with and evaluate the quality of the hash function you're providing. Average list traversal after the hash would be O(average_count_per_bucket/2), so again the focus is on enough buckets and a good hash function. I ask because, by switching to a dynamic hash, you'd go from a hard-coded hash to one whose properties would be have to be algorithmically applied at each hash operation. (Or, alternately, a large set of hard-coded functions whose pointers could be provided based on a best match.) Since you pay that penalty each hash operation, it could quickly dwarf the bucket-walk time mentioned above.
  2. [2]   Mats Kindahl
    May 19, 2011 at 03:55 AM

    I usually solve it by using a static C array of the contents and then add an adapter on top of it that either does a binary search or creates a hash. Think of it as an "indexing" layer on top of a normal C array of structures.