map complex find operation

Question

I want to do the following:
Define a map between a string and any kind of object (may be a list, integer - anything).
The keys to the map can be as follow (the values are, again, not important):
"AAA/123" ==> 1
"AAA/" ==> 2
"BBB/" ==> 3
"CCC/*" ==> 4
"CCC/123" ==> 5
Now, the trick is I want to find the right values given the following strings:
"AAA/123" should give 1.
"AAA/111" should give 2.
"CCC/111" should give 4.
"CCC/123" should give 5.
"BBB/AAA/123" should give 3.

Any idea how I do that with C++ and possibly STL/boost ?

Answer 1

Here's a variant of litb answer (which was somehow deleted from the answers list) which might work given the '*' is removed:

template<typename Map> typename Map::const_iterator
find_prefix(Map const& map, typename Map::key_type const& key)
{
    typename Map::const_iterator it = map.upper_bound(key);
    while (it != map.begin())
    {
        --it;
        if(key.substr(0, it->first.size()) == it->first)
            return it;
    }

    return map.end(); // map contains no prefix
}

I forgot to add the code that uses it:

std::map<std::string, int> smap;
smap["AAA/"] = 1;
smap["BBB/"] = 2;
smap["AAA/AA"] = 3;

find_prefix(smap, "AAA/AB")->second; // ==> 1
find_prefix(smap, "AAA/AA")->second; // ==> 3
find_prefix(smap, "BBB/AB")->second; // ==> 2
find_prefix(smap, "CCC/AB"); // ==> smap.end()

any comment (and thanks to litb) ?

Answer 2

From your requirement it seems that you don't really want map data structure but may be set or something very simple.

I think structure like this std::map might help you. Boost::any will be able to store anything, but caveat is that you need to know that value type is to read it back.

Key is string and hence it can be regex expression too. With this structure you will need two pass algorithm as:

std::map<std::string, boost::any> _map;
if (_map.find(key) != _map.end)
{
   // exact match
}
else
{
   // Have to do sequential regex (use boost::regex) matching
}

Since regex evaluation at runtime might be costly, you may use std::vector>, such that for regex patterns you store compiled regex into one of the fields.

It might be useful to give more background what you want to accomplish, as it may help to decide on right data structure and search algorithm.

Answer 3

What about using two maps ?

std::map<std::string, std::map<int, object> >

If you want to lookup aaa/* you do

a.find("aaa") => you get an iterator to the map with all "aaa" prefix

If you want to lookup aaa/123 you do

a.find("aaa")->find(123)

(of course you MUST validate that you don't get end, this is just for the example)