[ACCEPTED]-Partial match for the key of a std::map-stdmap

Accepted answer
Score: 29

You can't efficiently search for substring, but you 1 can for prefix:

#include <iostream>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

typedef map<string, string> TStrStrMap;
typedef pair<string, string> TStrStrPair;

TStrStrMap::const_iterator FindPrefix(const TStrStrMap& map, const string& search_for) {
    TStrStrMap::const_iterator i = map.lower_bound(search_for);
    if (i != map.end()) {
        const string& key = i->first;
        if (key.compare(0, search_for.size(), search_for) == 0) // Really a prefix?
            return i;
    }
    return map.end();
}

void Test(const TStrStrMap& map, const string& search_for) {
    cout << search_for;
    auto i = FindPrefix(map, search_for);
    if (i != map.end())
        cout << '\t' << i->first << ", " << i->second;
    cout << endl;
}

int main(int argc, char *argv[])
{
    TStrStrMap tMap;

    tMap.insert(TStrStrPair("John", "AA"));
    tMap.insert(TStrStrPair("Mary", "BBB"));
    tMap.insert(TStrStrPair("Mother", "A"));
    tMap.insert(TStrStrPair("Marlon", "C"));

    Test(tMap, "Marl");
    Test(tMap, "Mo");
    Test(tMap, "ther");
    Test(tMap, "Mad");
    Test(tMap, "Mom");
    Test(tMap, "Perr");
    Test(tMap, "Jo");

    return 0;
}

This prints:

Marl    Marlon, C
Mo      Mother, A
ther
Mad
Mom
Perr
Jo      John, AA
Score: 9

When your substring is a prefix as in your example, you 4 can use lower_bound to search for "Marl".

    map<string,string>::const_iterator m = tMap.lower_bound("Marl");
    cerr << (*m).second << endl;

This does not work 3 for non-prefix substrings: in the general 2 case, searching a map is not much different 1 from searching other containers.

Score: 4

I'd like to expand on the answer by Sergey by providing 10 a full solution using map::lower_bound(). As mentioned in 9 the comments on that answer, you have to 8 check whether lower_bound() returns tMap.end(). If not, then you 7 also have to check whether the found key 6 is actually prefixed with the search string. Latter 5 can be checked, for example, by using string::compare(). As a result, my 4 C++11 solution looks as follows:

std::map<std::string, std::string> myMap{
    {"John", "AA"}, {"Mary", "BBB"}, {"Mother", "A"}, {"Marlon", "C"}, {"Marla", "D"}
};
std::string prefix("Marl");

auto it = myMap.lower_bound(prefix);
if (it != std::end(myMap) && it->first.compare(0, prefix.size(), prefix) == 0)
    std::cout << it->first << ": " << it->second << std::endl;

Output:

Marla: D

However, if 3 you want to find all keys in your map that 2 are prefixed with the search string, then 1 you can use the following loop:

for (auto it = myMap.lower_bound(prefix); it != std::end(myMap) && it->first.compare(0, prefix.size(), prefix) == 0; ++it)
    std::cout << it->first << ": " << it->second << std::endl;

Output:

Marla: D
Marlon: C

Code on Ideone

Score: 2

To search for a substring of a key in a map you have 16 no choice but to either use a new map on 15 a special kind of key type or to search 14 your map in O(n). std::map uses (by default) operator<() for 13 ordering keys and for searching, and that 12 compare function for std::string is a plain lexicographical 11 compare.

If you create a new map on a special 10 key type that has operator<() compare on basis of a 9 substring take note that this will also 8 affect the decision of whether a new element 7 to insert would be a duplicate. In other 6 words, such a map will only have elements 5 that are not substrings of each other.

The 4 O(n) search practically means you use std::find() over 3 the map, with a custom predicate that takes 2 a std::pair<std::string,std::string> and returns true if the second element 1 of the pair is a substring of the first.

Score: 0
typedef TStrStrMap::value_type map_value_type;

struct key_contains_substring
   : std::binary_function<map_value_type, std::string, bool>
{
    bool operator()(const map_value_type& map_value, const std::string& substr)
    {
         return std::search(map_value.first.begin(), map_value.first.end(),
                    substr.begin(), substr.end()) != map_value.first.end();  
    }
};

...


TStrStrMap::const_iterator it = std::find_if(tMap.begin(), tMap.end(), 
        std::bind2nd(key_contains_substring(), "Marl");

0

More Related questions