3

std::mapいくつかの異なる文字列を互いにマップしたいので、プロジェクトでa を使用しています。たとえば、次のようなマップを作成できます。

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と組み合わせて as key コンパレータを使用してマップを使用しようとしlower_boundましたが、実行時エラーが発生し、このアプローチの効率にも疑問があります。

4

4 に答える 4

5

以下は、必要なことを行います。

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";
}
于 2013-10-01T16:20:04.790 に答える
0

の機能を使用して、そのstd::mapコンパレータを の外部で定義します。次のstd::mapようにします。

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

実際のデモで遊ぶには、こちらを参照してください: http://ideone.com/sg4sET

注:このコードは、同じことを行うさまざまな方法を示しています。必要なものだけを使用してください。個人的には、最後のコードが最もシンプルで読みやすいと思います。これは、コードが使用から遠く離れていないためです。

于 2013-10-01T20:24:09.313 に答える