Comment trouver un élément dans std::map avec des structures qui a au moins un membre de données égal à la clé

Question

J'ai une question sur la façon de trouver l'élément correspondant qui a au moins un numéro de données égal à la clé recherchée dans un fichier de type std::map avec des structures.

Par exemple, supposons que je doive trouver le numéro de téléphone d'une personne avec son nom ou dans un répertoire téléphonique (supposons qu'il n'y a pas de nom utilisé par plus d'une personne), je vais déclarer un fichier struct nommé Person et définir une std::map contenant Person et son numéro de téléphone (en std::string ) :

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

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

En cherchant sur Internet, j'ai découvert que les besoins de la structure étaient surchargés. == y < des opérateurs avec lesquels travailler std::map et les a mis en œuvre :

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

J'ai utilisé des "ou" logiques ( || ) dans la version surchargée de == opérateur afin d'implémenter la fonctionnalité permettant de trouver le numéro de téléphone avec le nom d'une personne. ou au lieu d'avoir besoin des deux.

J'ai écrit un peu de code pour tester la fonctionnalité :

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

Cependant, j'ai constaté que la recherche par id fonctionne très bien, mais que la recherche par nom ne peut pas fonctionner. Quel que soit le nom recherché, le numéro de téléphone ne peut jamais être trouvé. Le code du test ci-dessus produit le résultat suivant :

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

alors que le résultat attendu est

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

De plus, si je modifie la façon dont j'implémente la fonction surchargée < l'opérateur à

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

alors la recherche par nom fonctionne bien, mais la recherche par id ne fonctionnera pas.

Alors, comment puis-je mettre en œuvre la fonction (pour trouver le numéro de téléphone d'une personne avec son nom) ? ou id) avec std::map ? Ou bien est-il impossible de le mettre en œuvre de cette manière ?

Merci d'avance !

Answer 1

std::map est définie uniquement en fonction de la operator< . Deux entrées de carte sont considérées comme égales si et seulement si !(a < b) y !(b < a) . Votre operator== n'aide pas ici, et tous les find() est en train de trouver la personne avec l'ID que vous avez spécifié (ou le nom dans le second cas) parce qu'il ne considère que les éléments suivants operator< .

Le tableau général est le suivant std::map::find utilise le caractère trié de std::map (généralement implémenté comme un arbre rouge noir) pour éviter de devoir vérifier chaque élément. Cette propriété n'est pas utile si le nom et l'ID participent tous deux à votre recherche, car vous ne pouvez pas dire si un nom correspondant ou est avant ou après un nœud donné de l'arbre - vous ne le savez que pour l'ID (ou, dans le second cas, le nom).

À moins que vous ne souhaitiez mettre en œuvre un très une manière fantaisiste et complexe de combiner le nom et l'ID en un seul champ triable/rechercheable (je n'ai aucune idée de la façon dont vous feriez cela), vous devrez vérifier chaque élément. std::find_if fait cela pour vous :

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

Answer 2

Comme l'a souligné @Max Langhof, vous pouvez uniquement utiliser find() pour rechercher clés dans une carte car les cartes sont triées par clé. Pour effectuer une recherche sur la valeur (le nom dans votre cas), vous pouvez simplement itérer sur toutes les clés. Cependant, cette approche n'est pas efficace car vous devez rechercher dans chaque enregistrement de la carte.

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;