std::map 键的部分匹配

2021-12-20 00:00:00 dictionary containers search c++ stdmap

我有一个 std::map 并且我想使用子字符串搜索一个键.例如，我有以下代码:

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

现在，如果Marla"存储在地图中，我想搜索包含子字符串Marl"而不是Marlon"的位置.我想找到以Marl"开头的东西.我最多需要找到一个位置.这可能吗?如果是这样，如何?

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?

我不想使用任何 Boost 库！

I don't want to use any Boost libraries!

推荐答案

你不能高效搜索子字符串，但你可以搜索前缀:

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

打印:

Marl    Marlon, C
Mo      Mother, A
ther
Mad
Mom
Perr
Jo      John, AA

相关文章