Partial match for the key of a std::map

Question

I have an std::map and I want to search for a key using a substring. For example, I have the following code:

#include <iostream> #include <map> #include <string> using namespace std;  typedef std::map<std::string, std::string> TStrStrMap; typedef std::pair<std::string, std::string> TStrStrPair;  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"));      return 0; } 

Now, I want to search for the position that holds the substring "Marl" and not "Marlon", if "Marla" is stored in the map. I want to find something that starts with "Marl". I need to find at most one position. Is this possible? If so, how?

I don't want to use any Boost libraries!

Answer 1

You can't efficiently search for substring, but you 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