Map Search Operation

Question

I want to do the following:
Define a map between the line and any object (there may be a list, an integer - anything).
The keys to the card can be as follows (values, again, are not important):
"AAA / 123" ==> 1
"AAA /" ==> 2
"BBB /" ==> 3
"CCC / *" ==> 4
"CCC / 123" ==> 5
Now I want to find the correct values, given the following lines:
"AAA / 123" should give 1.
"AAA / 111" should give 2.
"CCC / 111" shall provide 4.
"CCC / 123" shall provide 5.
"BBB / AAA / 123" should give 3.

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

Answer 1

Here's a variant of the litb response (which was somehow removed from the answer list) that could work when deleting the '*':

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 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 litb)?

Answer 2

From your requirement, it seems that you really do not need a map data structure, but it can be installed or something very simple.

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

The key is a string, and therefore it is also a regular expression expression. With this structure, you will need two algorithms:

 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 evaluating regular expressions at runtime can be expensive, you can use std :: vector> so that for regular expression patterns you save the compiled regular expression in one of the fields.

Perhaps it would be useful to give more information about what you want to achieve, as this can help solve the correct data structure and search algorithm.

Answer 3

How to use two cards?

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

If you want to find aaa / *, you do

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

If you want to find aaa / 123, you do

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

(of course, you SHOULD confirm that you are not done, this is just an example)