在std :: map中部分匹配长键

Question

我std::map在我的项目中使用了一个,因为我想要将几个不同的字符串相互映射.例如,我可能会创建一个类似于此的地图:

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

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

我想使用比地图中的键更长的键找到这些值,即部分匹配键.地图中的所有键与它们所比较的键共享相同的前缀

这就是我想要实现的目标:

// 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'

我希望你明白我的意思.我想有效地检索映射到键的值,这些键对应于比它们大的比较键,但共享相同的前缀(例如'test').

我不知道std::map在这种情况下是否是最佳选择,如果没有,请告诉其他选项.

注意:我已经尝试使用带有std::greater_equal关键比较器的地图结合lower_bound方法,但我最终得到了运行时错误,我也质疑这种方法的效率.

Answer 1

以下将满足您的需求:

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";
}