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

Use the std::map's ability to have it's comparator defined externally from std::map, like so:

#include <iostream>
#include <map>
#include <string>
#include <string.h>
#include <functional>

using namespace std;

// Define comparator functor:
struct functor_test
{
    bool operator()(string const & lhs, string const & rhs)
    {
        return strncmp(lhs.c_str(), rhs.c_str(), 4) < 0;
    }
};

// Define comparator function:
bool function_test(string const & lhs, string const & rhs)
{
    return strncmp(lhs.c_str(), rhs.c_str(), 4) < 0;
}

int main() {
    // Define comparator lambda:
    auto lambda_test = [](string const & lhs, string const & rhs)
    {
        return strncmp(lhs.c_str(), rhs.c_str(), 4) < 0;
    };

    // These are all valid ways to declare the key comparitor:

    //As a functor:
    //  map<string, string, functor_test>                                 map;

    //As a function using a function reference type:
    //  map<string, string, bool(&)(string const&, string const&)>        map(function_test);

    //As a function using a function pointer type:
    //  map<string, string, bool(*)(string const&, string const&)>        map(function_test);

    //As a function using a function class type wrapper:
    //  map<string, string, function<bool(string const&, string const&)>> map(function_test);

    //As a predefined lambda:
    //  map<string, string, decltype(lambda_test)>                        map(lambda_test);

    //As a predefined lambda using a function class type wrapper:
    //  map<string, string, function<bool(string const&, string const&)>> map(lambda_test);

    //As a lambda using a function class type wrapper:
    map<string, string, function<bool(string const&, string const&)>>   map(
        [](string const & lhs, string const & rhs)
        {
            return strncmp(lhs.c_str(), rhs.c_str(), 4) < 0;
        });

    map["test"] = "Foo";
    map["blah"] = "Drei";
    map["fayh"] = "Najh";

    std::cout << map.find("test123")->second << endl;    // Should output 'Foo'
    std::cout << map.find("test_2165")->second << endl;  // Should output 'Foo' as well
    if (map.find("tes") == map.end())
    {
        cout << "Not found" << endl;
    }// Key not found
    std::cout << map.find("fayh_TK_Ka")->second << endl; // 'Najh'

    return 0;
}

To play with a working demo, see here: http://ideone.com/sg4sET

Note: this code shows a bunch of different methods to do the same thing. Only use what you need. I personally think that the last one is the simplest and easiest to read as it doesn't scatter code far from it's use.

Answer 2

If you don't mind changing the order of elements in the map, this should work and is fairly simple:

    std::map<std::string, std::string, std::greater<std::string>> map;
    map["test"] = "Foo";
    map["blah"] = "Drei";
    map["fayh"] = "Najh";

    std::string s = "fay";

    auto i = map.lower_bound(s);
    if (i != map.end() && std::equal(i->first.begin(), i->first.end(), s.begin())) {
        std::cout << i->first << " -> " << i->second << "\n";
    } else {
        std::cout << "not found\n";
    }

Answer 3

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 4

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.