时间戳

首页 > 解决方案 > 如何在 std::map 中查找具有至少一个数据成员等于键的结构的元素

c++ - 如何在 std::map 中查找具有至少一个数据成员等于键的结构的元素

问题描述

我有一个关于如何找到至少一个数据编号等于在std::mapwith 结构中搜索的键的相应元素的问题。

例如，假设我要在电话簿中找到一个人的电话号码和他的名字或id（假设没有使用多个人的名字），我将声明一个struct命名Person并定义一个std::map包含Person对象和他的/她的电话号码（in std::string）：

struct Person {
    std::string name;
    std::string id;
};

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

当我从互联网上搜索时，我知道该结构需要重载==和<操作符来使用std::map和实现它们：

bool operator==(const Person &person1, const Person &person2) {
    return person1.name == person2.name || person1.id == person2.id;
}

bool operator<(const Person &person1, const Person &person2) {
    return person1.id < person2.id;
}

||我在重载==运算符中使用了逻辑“或” （

我写了一些代码来测试这个功能：

// Add some entries
phonebook[{"Jack", "001"}] = "12345";
phonebook[{"Mike", "002"}] = "12346";
phonebook[{"Eric", "003"}] = "12347";

// Search by name
std::map<Person, std::string>::iterator iter = phonebook.find({"Jack", ""});
if (iter == phonebook.end())
    std::cout << "Cannot find the phone number for Jack" << std::endl;
else
    std::cout << "Jack's phone number is " << iter->second << std::endl;

// Search by id
iter = phonebook.find({"", "001"});
if (iter == phonebook.end())
    std::cout << "Cannot find the phone number for 001" << std::endl;
else
    std::cout << "001's phone number is " << iter->second << std::endl;

但是，我发现按 id 搜索效果很好，但按名称搜索就不行了。无论搜索什么名字，都找不到电话号码。上面的测试代码产生了以下输出：

Cannot find the phone number for Jack
001's phone number is 12345

而预期的输出是

Jack's phone number is 12345
001's phone number is 12345

更重要的是，如果我将实现重载<运算符的方式更改为

bool operator<(const Person &person1, const Person &person2) {
    return person1.name < person2.name; // change "id" to "name"
}

然后按名称搜索效果很好，但按 id 搜索将不起作用。

那么我该如何实现这个功能（用他/她的名字或身份证找到一个人的电话号码）std::map呢？还是不能以这种方式实施？

提前致谢！

标签： c++structstdmap

解决方案

std::map仅根据 来定义operator<。当且仅当!(a < b)和时，两个映射条目被认为是相等的!(b < a)。你operator==在这里没有帮助，所有的find()电话都是用你指定的 ID（或第二种情况下的名字）来寻找那个人，因为它只考虑operator<.

更大的图景是std::map::find利用std::map（通常实现为红黑树）的排序性来避免检查每个元素。如果名称和 ID 都参与您的搜索，则此属性没有帮助，因为您无法判断匹配名称是否在树中的任何给定节点之前或之后 - 您只知道 ID （或者，在第二个案例，名称）。

除非您想实现一种非常奇特且复杂的方式将名称和 ID 组合到一个可排序/可搜索的字段中（不知道您将如何做到这一点），否则您将不得不检查每个元素。std::find_if为您做到这一点：

std::find_if(phonebook.begin(), phonebook.end(), [name, id](const std::pair<Person, std::string>& personAndNumber) {
  const Person& person = personAndNumber.first;
  return person.name == name || person.id == id;
});

推荐阅读