c++ - libreria - Restricción mística en std:: binary_search

sort algorithm c++

Question

Descripción del problema:
Considere alguna estructura que tenga un miembro de std::string name . Para mayor claridad, supongamos que es una struct Human , que representa información sobre personas. Además del name , también puede tener muchos otros miembros de datos.
Deje que haya un contenedor std::vector<Human> vec , donde los objetos ya están ordenados por name . También por claridad, supongamos que todos los nombres son únicos.
El problema es : tener un string nameToFind averiguar si existe un elemento en la matriz que tenga dicho nombre.

Solución y mi progreso:
La solución obvia y natural parece realizar una búsqueda binaria usando la función std::binary_search . Pero hay un problema: el tipo del elemento que se busca ( std::string ) es diferente del tipo de los elementos en el contenedor ( Human ), y std :: binary_search necesita una regla para comparar estos elementos. Traté de resolver esto de tres maneras, que se describen a continuación. Los dos primeros se proporcionan solo para ilustrar la evolución de mi solución y los problemas que encontré. Mi pregunta principal se refiere a la tercera.

Intento 1: convertir std::string en Human .

Escribe una función de comparación:

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

A continuación, agregue un constructor que construye un objeto Human de std::string :

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

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

y use binary_search en la siguiente forma:

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

Parece que funciona, pero aparece dos grandes problemas:
Primero, ¿cómo inicializar otros miembros de datos pero Human::name , especialmente en el caso en que no tengan un constructor predeterminado? establecer valores mágicos puede conducir a la creación de un objeto que es semánticamente ilegal.
Segundo, tenemos que declarar este constructor como no explicit para permitir conversiones implícitas durante el algoritmo. Las malas consecuencias de esto son bien conocidas.
Además, se construirá un objeto Human temporal en cada iteración, lo que puede resultar bastante costoso.

Intento 2: convertir Human a std::string .

Podemos intentar agregar una operator string () a la clase Human que devuelve su name , y luego usar la comparación para dos std::string s. Sin embargo, este enfoque también es inconveniente por las siguientes razones:

Primero, el código no se compilará de inmediato debido al problema discutido here . Tendremos que trabajar un poco más para que el compilador use el operator < apropiado operator < .
En segundo lugar, ¿qué significa "convertir un humano en cuerda"? La existencia de tal conversión puede conducir a un uso semántico erróneo de la clase Human , lo cual es indeseable.

Intento 3: compare sin conversiones.

La mejor solución que tengo hasta ahora es crear 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;
   }
};

y usa la búsqueda binaria como

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

Esto compila y ejecuta correctamente, todo parece estar bien, pero aquí es donde comienza la parte interesante:

Eche un vistazo a http://www.sgi.com/tech/stl/binary_search.html . Aquí se dice que "el tipo de valor de ForwardIterator es del mismo tipo que T ". Restricción bastante confusa, y mi última solución la rompe. Veamos qué dice el estándar de C ++ al respecto:

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

Requiere: el tipo T es LessThanComparable (20.1.2).

Nada se dice explícitamente sobre el tipo de ForwardIterator . Pero, en la definición de LessThanComparable dada en 20.1.2 , se dice acerca de la comparación de dos elementos del mismo tipo . Y esto es lo que no entiendo. ¿De hecho significa que el tipo de objeto que se busca y el tipo de objetos del contenedor debe ser el mismo, y mi solución rompe esta restricción? ¿O no se refiere al caso cuando se utiliza el comparador de comp , y solo se trata del caso cuando el operator < predeterminado operator < se utiliza para la comparación? En el primer caso, estoy confundido acerca de cómo usar std::binary_search para resolver esto sin encontrar los problemas mencionados anteriormente.

Gracias de antemano por su ayuda y encontrar tiempo para leer mi pregunta.

Nota: Entiendo que escribir una búsqueda binaria a mano no requiere tiempo y resolveré el problema al instante, pero para evitar reinventar una rueda, quiero usar std :: binary_search. También me resulta muy interesante conocer la existencia de tal restricción según el estándar.

Answer 1

Creo que lo que el estándar está diciendo aquí es que la expresión fucntor(a, b) necesita ser un ordenamiento débil estricto válido, sin importar si el algoritmo decide hacer algo como functor(*begin, *(begin + 1)) . Por lo tanto, creo que su comparador necesitaría suministrar una sobrecarga de operator()(Human, Human) para conformarse.

Dicho esto, creo que esta es una de esas cosas que el estándar no permite explícitamente, pero para las cuales existen pocas o ninguna implementación que aproveche la flexibilidad ofrecida por el estándar .

Answer 2

No veo que requiera en ninguna parte de la norma que los tipos de valores pasados ​​a la función de comparación (o al < operador) por binary_search sean los mismos. Entonces, formalmente, creo que está perfectamente bien usar un comparador que funcione con dos valores de tipos diferentes.

Answer 3

Si su objetivo es encontrar si hay un Human con un nombre dado, entonces lo siguiente debería funcionar con seguridad:

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 4

[Reescribir completo; no tener en cuenta los comentarios]

La redacción ha cambiado de C ++ 03 a C ++ 0x. En este último caso, no hay más requisito para que T sea ​​menos que comparable, presumiblemente para aliviar esta restricción innecesaria.

El nuevo estándar solo requiere que comp(e, value) implique !comp(value, e) . Por lo tanto, siempre que su comparador implemente ambas direcciones, debería poder buscar legalmente una string como el valor con un funcionador de comparación que implemente ambas comparaciones asimétricas (es decir, su "Intento 3").