Re: [Boost-users] Static map like array or range?

Subject: Re: [Boost-users] Static map like array or range?
From: Gottlob Frege (gottlobfrege_at_[hidden])
Date: 2013-09-18 12:59:52

On Sun, Sep 15, 2013 at 3:55 PM, Duane Murphy <duanemurphy_at_[hidden]> 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