Mystique restriction sur std::binary_search

Question

Problème desicription:
Considérons une structure ayant un std::string name membre. Pour la clarté supposons que c'est un struct Human, représentant des informations sur les personnes. En plus de l' name il peut aussi avoir de nombreux autres membres de données.
Qu'il y ait un conteneur std::vector<Human> vec, où les objets sont déjà triés par name. Aussi pour la clarté suppose que tous les noms sont uniques.
Le problème, c'est: avoir une chaîne de caractères nameToFind savoir s'il existe un élément dans le tableau ayant ce nom.

Solution et de mon avancement:
L'évidence et la solution naturelle semble effectuer une recherche binaire à l'aide de l' std::binary_search fonction. Mais il y a un problème: le type de l'élément recherché (std::string) est différent du type des éléments dans le conteneur (Human), et std::binary_search besoin d'une règle pour comparer ces éléments. J'ai essayé de résoudre ce de trois manières, décrites ci-dessous. Les deux premières sont prévues seulement pour illustrer l'évolution de ma solution et les problèmes qui j'en suis venu à travers. Ma principale question se réfère à la troisième.

Tentative 1: convertir std::string de Human.

Écrire une comparaison de la fonction:

bool compareHumansByNames( const Human& lhs, const Human& rhs )
{
   return lhs.name < rhs.name;
}

Puis ajouter un constructeur qui construit un Human objet à partir d' std::string:

struct Human
{
   Human( const std::string& s );
   //... other methods

   std::string name;
   //... other members
};

et l'utilisation de la binary_search dans la forme suivante:

std::binary_search( vec.begin(), vec.end(), nameToFind, compareHumansByNames );

Semble de travail, mais les virages jusqu'à deux gros problèmes:
Tout d'abord, comment initialiser d'autres membres de données, mais Human::name, surtout dans le cas où ils n'ont pas de constructeur par défaut ? réglage de la magie valeurs peut conduire à la création d'un objet qui est sémantiquement illégale.
Deuxièmement, nous devons déclarer ce constructeur non explicit afin de permettre les conversions implicites au cours de l'algorithme. Les mauvaises conséquences de cette situation sont bien connues.
Aussi, un tel temporaire Human objet sera construit à chaque itération, ce qui peut s'avérer être assez cher.

Tentative 2: convertir Human de std::string.

Nous pouvons essayer d'ajouter un operator string () de la Human de la classe qui le renvoie de l' name, puis utilisez la comparaison de deux std::strings. Cependant, cette approche est aussi incommodes par les raisons suivantes:

D'abord, le code ne compilera pas à la fois à cause du problème discuté ici. Il va falloir travailler un peu plus pour faire le compilateur utiliser le operator <.
Deuxièmement, ce qui signifie "convertir l'Homme à la chaîne" ? L'Existence d'une telle conversion peut conduire à sémantiquement mauvais usage de la classe Human, ce qui est indésirable.

Tentative 3: comparer sans conversion.

La meilleure solution que j'ai obtenu jusqu'à présent est de créer un

struct Comparator
{
   bool operator() ( const Human& lhs, const std::string& rhs )
   {
      return lhs.name < rhs;
   }
   bool operator() ( const std::string& lhs, const Human& rhs )
   {
      return lhs < rhs.name;
   }
};

et utiliser les binaires de recherche qu'

binary_search( vec.begin(), vec.end(), nameToFind, Comparator() );

Cette compile et s'exécute correctement, tout semble ok, mais c'est là que la partie intéressante commence:

Jetez un oeil à http://www.sgi.com/tech/stl/binary_search.html. Il est dit ici que "ForwardIterator's le type de valeur est du même type que T.". Assez déroutant de restriction, et ma dernière solution, il tombe. Nous allons voir quelle est la norme C++ dire à ce sujet:

---

25.3.3.4 binary_search

template<class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value);

template<class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);

Nécessite: Type T est LessThanComparable (20.1.2).

---

Rien n'est explicitement dit à propos de ForwardIterators'type. Mais, dans la définition de la LessThanComparable donné dans 20.1.2 il est dit à propos de la comparaison de deux éléments de même type. Et voici ce que je ne comprends pas. Est-il en effet que le type de l'objet recherché et le type du conteneur d'objets doit être la même, et ma solution casse cette restriction ? Ou il ne se réfère pas le cas lorsque l' comp comparateur est utilisé, et seulement sur le cas lorsque la valeur par défaut operator < est utilisé pour la comparaison ? Dans le premier cas, je suis confus sur la façon d'utiliser std::binary_search afin de résoudre ce sans rencontrer les problèmes mentionnés ci-dessus.

Merci d'avance pour l'aide et de trouver le temps de lire ma question.

Remarque: je comprends que l'écriture binaire de recherche à la main prend pas de temps et va résoudre le problème instantanément, mais pour éviter de réinventer la roue je veux utiliser les std::binary_search. Aussi, il est très intéressant pour moi de savoir à propos de l'existence d'une telle restriction selon la norme.

Answer 1

Si votre objectif est de trouver si il y a un Human avec un nom donné, les opérations suivantes doivent travailler pour assurer:

const std::string& get_name(const Human& h)
{
    return h.name;
}

...

bool result = std::binary_search(
    boost::make_transform_iterator(v.begin(), &get_name),
    boost::make_transform_iterator(v.end(), &get_name),
    name_to_check_against);

Answer 2

[Réécriture complète; ignorer les commentaires]

Le libellé a été modifié à partir de C++03 C++0x. Dans le deuxième cas, il n'est plus de l'exigence d' T à être moins comparable, sans doute pour pallier cette restriction inutile.

La nouvelle norme exige seulement qu' comp(e, value) implique !comp(value, e). Donc, tant que votre comparateur de implémente les deux directions, vous devriez être capable juridiquement de la recherche d'un string comme valeur avec un comparateur foncteur qui implémente à la fois asymétrique des comparaisons (c'est à dire votre "Tentative 3").

Answer 3

Je pense que le standard est en train de dire est que l'expression fucntor(a, b) doit être valide strict ordonnancement faible, peu importe si l'algorithme décide de faire quelque chose comme functor(*begin, *(begin + 1)). Donc, je pense que votre comparateur aurait besoin de fournir une surcharge d' operator()(Human, Human) afin d'être en conformité.

Cela dit, je pense que c'est une de ces choses pas explicitement autorisée par la norme, mais pour lesquelles peu ou pas il existe des implémentations qui profitent de la latitude offerte par la norme.

Answer 4

Je ne vois pas exiger n'importe où dans la norme que les types des valeurs transmises à la fonction de comparaison (ou à l' < opérateur) en binary_search doit être la même. Donc, officiellement, je pense qu'il est parfaitement acceptable d'utiliser un comparateur qui fonctionne avec deux différemment les types de valeurs.