std :: map部分匹配键

Question

我有一个std :: map,我想使用子字符串搜索一个键.例如

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

我想搜索包含子串"Marl"而不是"Marlon"的位置.可能吗？怎么样？

编辑:没有加速库!

Answer 1

您无法有效搜索子字符串,但您可以为前缀:

#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 << '\t' << 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

Answer 2

当您的子字符串是示例中的前缀时,您可以使用lower_bound搜索"Marl".

    map<string,string>::const_iterator m = tMap.lower_bound("Marl");
    cerr << (*m).second << endl;

这不适用于非前缀子串:在一般情况下,搜索地图与搜索其他容器没有太大区别.

Answer 3

我想通过使用map::lower_bound(). 正如该答案的评论中提到的，您必须检查是否lower_bound()returns tMap.end(). 如果没有，那么您还必须检查找到的键是否实际上以搜索字符串为前缀。例如，可以使用 来检查后者string::compare()。结果，我的 C++11 解决方案如下所示：

std::map<std::string, std::string> myMap{
    {"John", "AA"}, {"Mary", "BBB"}, {"Mother", "A"}, {"Marlon", "C"}, {"Marla", "D"}
};
std::string prefix("Marl");

auto it = myMap.lower_bound(prefix);
if (it != std::end(myMap) && it->first.compare(0, prefix.size(), prefix) == 0)
    std::cout << it->first << ": " << it->second << std::endl;

输出：

玛拉：D

但是，如果您想查找映射中以搜索字符串为前缀的所有键，则可以使用以下循环：

for (auto it = myMap.lower_bound(prefix); it != std::end(myMap) && it->first.compare(0, prefix.size(), prefix) == 0; ++it)
    std::cout << it->first << ": " << it->second << std::endl;

输出：

玛拉：D
马龙：C

Ideone 上的代码