c++ container search by key and value

Question

I'm trying to build a container of string representations of ordinal numbers, searchable both by the string and by the number. For example, I can do it trivially, but inefficiently, with an array:

std::string ordinalStrings = {"zeroth", "first", "second",..}

getting the string with ordinalStrings[number], and the integer with a while(not found) loop, but I figure that one of the STL containers would do a better job, just not sure which one.

It needn't be searchable by both, for example, simply getting the numerical key of a map with a string key would work, but there doesn't seem to be a function for it, and besides, it seems a little messy.

As an aside, is it possible to have a constant STL container? I only need the searching functionality, not the insertion. Also, since I assume I can't, is it possible to fill the container without an initializer function? That is, can a header simply say:

std::map<std::string, int> ordinals;
ordinals["zero"] = 0;
ordinals["one"] = 1;
...

It just seems silly to have an initializer function for what is essentially a constant value;

Thanks, Wyatt

Answer 1

You can provide two different lookup mechanisms using boost::multi_index (here's an example of a bidirectional map using multi_index). Another (maybe simpler) option is to maintain two containers: one to lookup by ordinal, one to search by string. You could use two std::map or a std::map and a std::vector (for constant time lookup of ordinality).

As an aside, is it possible to have a constant STL container? I only need the searching functionality, not the insertion.

Yes, but you must initialize a non-const container. You can then copy that into a const container. For example, you can use a helper function: const std::map<string, int> ordinals = create_map();

That is, can a header simply say: ...

No, you should initialize the container within a proper control flow.

Answer 2

Stephen suggested using Boost.MultiIndex, however it's a bit an overkill.

Boost.Bimap has been developped over it, and offer extra functionalities. It is in fact tailored right for this task. It's also one of the few libraries which has (imho) a good documentation :)

Here is an example right from this page.

#include <iostream>

#include <boost/bimap.hpp>

struct country  {};
struct place    {};

int main()
{
    using namespace boost::bimaps;

    // Soccer World cup.

    typedef bimap
    <
        tagged< std::string, country >,
        tagged< int        , place   >

    > results_bimap;

    typedef results_bimap::value_type position;

    results_bimap results;
    results.insert( position("Argentina"    ,1) );
    results.insert( position("Spain"        ,2) );
    results.insert( position("Germany"      ,3) );
    results.insert( position("France"       ,4) );

    std::cout << "Countries names ordered by their final position:"
                << std::endl;

    for( results_bimap::map_by<place>::const_iterator
            i    = results.by<place>().begin(),
            iend = results.by<place>().end() ;
            i != iend; ++i )
    {
        std::cout << i->get<place  >() << ") "
                  << i->get<country>() << std::endl;
    }

    std::cout << std::endl
              << "Countries names ordered alphabetically along with"
                 "their final position:"
              << std::endl;

    for( results_bimap::map_by<country>::const_iterator
            i    = results.by<country>().begin(),
            iend = results.by<country>().end() ;
            i != iend; ++i )
    {
        std::cout << i->get<country>() << " ends "
                  << i->get<place  >() << "º"
                  << std::endl;
    }

    return 0;
}