Static map like array or range?
I find myself often building lookup tables for conversion or mapping of one piece of data to another. Common conversions include * converting from one string to a different string (e.g. text translation), * converting from an enum to a descriptive string * converting from a string to an enum * converting from a string to a function or functor The key aspect of these lookup tables is that they are static. If the table is reasonably large, say 7-10 items, I ensure that the table is presorted and use lower_bounds() to search the table. Some uses have started using map_list_of() to initialize the map. My inner optimizer finds this disturbing as inherently static information is being allocated dynamically in order to due to the lookup. I believe it would be more intuitive if there was a map like interface to the lookup table. The implementation would use the static nature of the data to its advantage. In particular the implementation would not require the data to be copied, re-allocated, etc. I've been searching the boost libraries, but have not been able to find something like this. Thank you for your suggestions. …Duane
I find myself often building lookup tables for conversion or mapping of one piece of data to another. Common conversions include
* converting from one string to a different string (e.g. text translation), * converting from an enum to a descriptive string * converting from a string to an enum * converting from a string to a function or functor
The key aspect of these lookup tables is that they are static. If the table is reasonably large, say 7-10 items, I ensure that the table is presorted and use lower_bounds() to search the table.
For the first, third, and fourth items, I sometimes use run-time created Keyword Matching functions. I wrote about ways of doing this at: http://blog.raymond.burkholder.net/index.php?/archives/129-A-Keyword-Matchin g-Algorithm.html http://blog.raymond.burkholder.net/index.php?/archives/371-Keyword-Matching- non-text-streams.html If built with static functions, then you get the 'build once, use many' style of functionality. There are probably some additional optimizations. The other way of doing this would be to use boost::spirit. You can use the parser to parse a series of predefined string candidates and generate a result. The parsers are built at compile time, and basically build a compile structure of the run time structure I suggest above. If I recall correctly, the compile time structure uses efficiently built tries for its search. For your second item, if your enums are close together, then I've heard that compilers optimize switch statements quite handily, sometimes turning switch statements into compile time indexed offset jump tables. You can't get much faster than that. Otherwise using lower_bound on random_iterator capable constructs seems to be the fastest way of doing things. -- This message has been scanned for viruses and dangerous content by MailScanner, and is believed to be clean.
On Sun, Sep 15, 2013 at 3:55 PM, Duane Murphy <duanemurphy@mac.com> wrote:
I find myself often building lookup tables for conversion or mapping of one piece of data to another. Common conversions include
* converting from one string to a different string (e.g. text translation), * converting from an enum to a descriptive string * converting from a string to an enum * converting from a string to a function or functor
The key aspect of these lookup tables is that they are static. If the table is reasonably large, say 7-10 items, I ensure that the table is presorted and use lower_bounds() to search the table.
Some uses have started using map_list_of() to initialize the map. My inner optimizer finds this disturbing as inherently static information is being allocated dynamically in order to due to the lookup.
I believe it would be more intuitive if there was a map like interface to the lookup table. The implementation would use the static nature of the data to its advantage. In particular the implementation would not require the data to be copied, re-allocated, etc.
I've been searching the boost libraries, but have not been able to find something like this.
Thank you for your suggestions.
…Duane
I've seen code that built a map of countries (ALL countries) from abbreviations ("USA" -> "United States of America", etc). Big static tables turned into dynamic std::maps. :-( So I wrote a static_map (again!) a couple of weeks ago. Example usage: // you might find it easiest to use a typedef...typedef static_map<char const *, SomeEnum> HelloMap; HelloMap::table_entry_type helloTable[] ={ // must be sorted! { "hello", E_HELLO }, { "world", E_WORLD }, // ... and many more...}; HelloMap helloMap = helloTable; // ie if you are replacing map<> based code:SomeEnum STLLikeLookup(char const * inputString){ HelloMpa::const_iterator it = helloMap.find(inputString); if (it != helloMap.end()) { return it->second; } return E_INVALID;} // or simply:SomeEnum doLookup(char const * inputString){ return helloMap.find_value_or(inputString, E_INVALID);} In my case, in debug mode the constructor checks that the table is presorted. (Since it is static data, the developer should be able to keep it sorted) But I'm considering changing the constructor to something that forces the sorting to be outside the class ie: HelloMap helloMap = ensureSorted(helloTable); with various functions like ensureSorted() that either check in debug or sort in place or various combinations. I *might* be able to get this into opensource. It is sadly just a complicated mess surrounding std::bsearch(). But it seems no one calls wants to call bsearch(), they'd rather have it packaged into a static_map. Tony
participants (3)
-
Duane Murphy -
Gottlob Frege -
Raymond Burkholder