Partially match long key in std::map

Question

I'm using a std::map in my project, because I want to map several different strings to each other. For example I might create a map that looks similar to this:

std::map<std::string, std::string> map;

map["test"] = "Foo";
map["blah"] = "Drei";
map["fayh"] = "Najh";
// And so on...

I want to find these values using keys that are longer than the ones in the map, i.e partially match the keys. All keys in the map share the same prefix as the keys that they are compared against

This is what I am trying to achieve:

// Same map as earlier
std::cout << map.find('test123').second;    // Should output 'Foo'
std::cout << map.find('test_2165').second;  // Should output 'Foo' as well
std::cout << map.find('tes').second;        // Key not found
std::cout << map.find('fayh_TK_Ka').second; // 'Najh'

I hope you understand what I am after. I want to efficiently retrieve values mapped to keys that correspond to compared keys which are larger than them, but share the same prefix (such as 'test').

I don't know if std::map is the best choice in this case, if not, please do tell about other options.

NOTE: I have tried using a map with std::greater_equalas key comparator combined with the lower_bound method, but I end up with runtime errors, and I also question the efficiency of this approach.

Answer 1

The following will do what you need:

std::string my_find( const std::string& s )
{
    auto it = map.lower_bound( s );
    if( it != map.begin() ) {
        if( it != map.end() && it->first == s ) return it->second; // exact match
        --it;
        if( it->first == s.substr( 0, it->first.size() ) ) {
            return it->second;
        }
    }
    return "Key not found";
}

Answer 2

This code should be pretty efficient:

#include <algorithm>
#include <vector>
#include <iostream>

typedef std::pair<std::string, std::string> Strings;
typedef std::vector<Strings> Values;

std::string findValue( const Values &vals, const std::string &str )
{
   auto it = std::lower_bound( vals.begin(), vals.end(), Strings( str, std::string() ), []( const Strings &s1, const Strings &s2 ) {
      size_t len = std::min( s1.first.length(), s2.first.length() );
      return s1.first.substr( 0, len ) < s2.first.substr( 0, len );
   } );
   if( it == vals.end() || it->first.length() > str.length() ) return std::string();
   return it->second;
}

void test(  const Values &vals, const std::string &str )
{
   std::cout << "testing \"" << str << "\" - \"" << findValue( vals, str ) << "\"" << std::endl;
}

int main()
{
    Values vals { { "test", "Foo" }, { "blah", "Drei" }, { "fayh", "Najh" } };
    std::sort( vals.begin(), vals.end(), []( const Strings &s1, const Strings &s2 ) { return s1.first < s2.first; } );

    test( vals, "test123" );
    test( vals, "test_2165" );
    test( vals, "test" );
    test( vals, "tes" );

    return 0;
}

For more efficient solution you can use parser generator like lex, if your data is static of course.