Как найти элемент в std :: map со структурами, в которых хотя бы один элемент данных равен ключу - PullRequest
Новая
       17

Как найти элемент в std :: map со структурами, в которых хотя бы один элемент данных равен ключу

3 голосов
/ 14 мая 2019

У меня есть вопрос о том, как найти соответствующий элемент, который имеет хотя бы один номер данных, равный ключу, который ищется в std::map со структурами.

Например, предположим, что я должен найтиномер телефона человека с его именем или id в телефонной книге (предположим, что нет имени, которое используется более чем одним человеком), я объявлю struct с именем Person и определю std::map содержит Person объектов и его / ее номер телефона (в 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;
}

Я использовал логические "или" (||) в перегруженном == операторе, чтобы реализовать функцию, которую может использовать телефонный номербыть найденным с именем человека или 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;

Однако я обнаружил, что поискпо идентификатору работает очень хорошо, но поискг по имени не может работать.Независимо от того, какое имя ищется, номер телефона не может быть найден.Приведенный выше код для проверки выдает следующий вывод: 

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?Или это не может быть реализовано таким образом?

Заранее спасибо!

Ответы [ 2 ]

4 голосов
/ 14 мая 2019

std::map определяется только в терминах operator<.Две записи на карте считаются равными тогда и только тогда, когда !(a < b) и !(b < a).Ваш operator== здесь не помогает, и все, что делает find(), - это поиск человека с указанным вами идентификатором (или именем во втором случае), поскольку он учитывает только operator<.

.большая картина в том, что std::map::find использует сортировку std::map (обычно реализованную как красное черное дерево), чтобы избежать необходимости проверять каждый элемент.Это свойство не полезно, если в вашем поиске участвуют как имя, так и идентификатор, потому что вы не можете определить, совпадает ли имя или до или после какого-либо узла в дереве - вы знаете это только для идентификатора(или, во втором случае, имя).

Если вы не хотите реализовать очень причудливый и сложный способ объединения имени и идентификатора в одно сортируемое / доступное для поиска поле (нетидея, как вы это сделаете), вам придется проверить каждый элемент.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;
});
0 голосов
/ 14 мая 2019

Как указал @Max Langhof, вы можете использовать find() только для поиска ключей на карте, поскольку карты сортируются по ключу. Для поиска с использованием значения (имя в вашем случае), вы можете просто использовать итерацию по всем ключам. Хотя этот подход неэффективен, так как вам приходится искать каждую запись на карте. 

for (auto it = phonebook.begin(); it != phonebook.end(); it++)
{
    if (it->second == "001")
    {
        return it->first;
    }     
}

// If you reach here, then value was not found
std::cout << "Cannot find the phone number for 001" << std::endl;
...