C++ lambdas para std :: sort y std :: LOWER_BOUND/equal_range en un elemento de estructura en un vector ordenado de estructuras

Question

que tiene un std :: vector de esta estructura:

struct MS 
{   
    double aT; 
    double bT; 
    double cT; 
}; 

el que quiero usar std :: sort on aswell como std :: lower_bound/equal_range etc ...

Necesito poder ordenarlo y buscarlo en cualquiera de los primeros dos elementos de la estructura. Así que por el momento tengo esto:

class MSaTLess 
{ 
public: 
    bool operator() (const MS &lhs, const MS &rhs) const 
    { 
    return TLess(lhs.aT, rhs.aT); 
    } 
    bool operator() (const MS &lhs, const double d) const 
    { 
    return TLess(lhs.aT, d); 
    } 
    bool operator() (const double d, const MS &rhs) const 
    { 
    return TLess(d, rhs.aT); 
    } 
private: 
    bool TLess(const double& d1, const double& d2) const 
    { 
    return d1 < d2; 
    } 
}; 


class MSbTLess 
{ 
public: 
    bool operator() (const MS &lhs, const MS &rhs) const 
    { 
    return TLess(lhs.bT, rhs.bT); 
    } 
    bool operator() (const MS &lhs, const double d) const 
    { 
    return TLess(lhs.bT, d); 
    } 
    bool operator() (const double d, const MS &rhs) const 
    { 
    return TLess(d, rhs.bT); 
    } 
private: 
    bool TLess(const double& d1, const double& d2) const 
    { 
    return d1 < d2; 
    } 
}; 

Esto permite que llame tanto std :: sort y std :: LOWER_BOUND con MSaTLess() para ordenar/búsqueda basada en el elemento de AT y con el MSbTLess() para ordenar/búsqueda basada en el elemento bT.

Me gustaría alejarme de los funtores y usar C++ 0x lambdas en su lugar. Para sort que es relativamente sencillo ya que la lambda tomará dos objetos de tipo MS como argumentos.

¿Qué pasa con el algoritmo low_bound y otros algoritmos de búsqueda binaria? Necesitan poder llamar a un comparador con argumentos (MS, dobles) y también al revés (doble, MS), ¿verdad? ¿Cómo puedo proporcionar estos con un lambda en una llamada a lower_bound? Sé que podría crear un objeto ficticio MS con el valor de clave requerido que se busca y luego usar el mismo lambda que con std :: sort, pero ¿hay alguna forma de hacerlo sin usar objetos ficticios?

Answer 1

Es un poco incómodo, pero si revisas las definiciones de lower_bound y upper_bound de la norma, verá que la definición de lower_bound pone el iterador sin referencia como el primera parámetro de la comparación (y el segundo valor), mientras que upper_bound pone el iterador desreferenciado segundo (y el valor primero).

Por lo tanto, no he probado esto, pero creo que te gustaría:

std::lower_bound(vec.begin(), vec.end(), 3.142, [](const MS &lhs, double rhs) { 
    return lhs.aT < rhs; 
}); 

y

std::upper_bound(vec.begin(), vec.end(), 3.142, [](double lhs, const MS &rhs) { 
    return lhs < rhs.aT; 
}); 

Esto es bastante desagradable, y sin levantar la vista algunas cosas más que' No estoy seguro de que tenga derecho a suponer que la implementación usa el comparador solo en la forma en que se describe en el texto; esa es una definición del resultado, no los medios para llegar allí. Tampoco ayuda con binary_search o equal_range.

No es explícito en 25.3.3.1 que tipo de valor del repetidor debe ser convertible en T, pero es una especie de implícito en el hecho de que el requisito de que el algoritmo es que T (en este caso, double) debe ser LessThanComparable, no es que T deba ser comparable al tipo de valor del iterador en cualquier orden en particular.

Así que creo que es mejor usar siempre una lambda (o functor) que compare dos estructuras de MS, y en lugar de pasar un doble como valor, pase una MS ficticia con el campo correcto configurado al valor que está buscando:

std::upper_bound(vec.begin(), vec.end(), MS(3.142,0,0), [](const MS &lhs, const MS &rhs) { 
    return lhs.aT < rhs.aT; 
}); 

Si no quiere dar un constructor MS (porque usted quiere que sea POD), entonces usted puede escribir una función para crear el objeto de EM:

MS findA(double d) { 
    MS result = {d, 0, 0}; 
    return result; 
} 
MS findB(double d) { 
    MS result = {0, d, 0}; 
    return result; 
} 

Realmente, ahora que hay lambdas, para este trabajo queremos una versión de búsqueda binaria que tome unario "co mparator ":

double d = something(); 
unary_upper_bound(vec.begin(), vec.end(), [d](const MS &rhs) { 
    return d < rhs.aT; 
}); 

C++ 0x no lo proporciona, sin embargo.

Answer 2

Los algoritmos std :: sort, std :: lower_bound y std :: binary_search toman un predicado que compara dos elementos del contenedor. Cualquier lambda que compare dos objetos MS y devuelva true cuando estén en orden debería funcionar para los tres algoritmos.

Answer 3

no guardan relación directa con lo que estás diciendo de lambdas, pero esto podría ser una idea para utilizar las funciones de búsqueda binarios:

#include <iostream> 
#include <algorithm> 
#include <vector> 

struct MS 
{ 
    double aT; 
    double bT; 
    double cT; 
    MS(double a, double b, double c) : aT(a), bT(b), cT(c) {} 
}; 

// template parameter is a data member of MS, of type double 
template <double MS::*F> 
struct Find { 
    double d; 
    Find(double d) : d(d) {} 
}; 

template <double MS::*F> 
bool operator<(const Find<F> &lhs, const Find<F> &rhs) { 
    return lhs.d < rhs.d; 
} 
template <double MS::*F> 
bool operator<(const Find<F> &lhs, const MS &rhs) { 
    return lhs.d < rhs.*F; 
} 
template <double MS::*F> 
bool operator<(const MS &lhs, const Find<F> &rhs) { 
    return lhs.*F < rhs.d; 
} 

int main() { 
    std::cout << (Find<&MS::bT>(1) < Find<&MS::bT>(2)) << "\n"; 
    std::cout << (Find<&MS::bT>(1) < MS(1,0,0)) << "\n"; 
    std::cout << (MS(1,0,0) < Find<&MS::bT>(1)) << "\n"; 

    std::vector<MS> vec; 
    vec.push_back(MS(1,0,0)); 
    vec.push_back(MS(0,1,0)); 
    std::lower_bound(vec.begin(), vec.end(), Find<&MS::bT>(0.5)); 
    std::upper_bound(vec.begin(), vec.end(), Find<&MS::bT>(0.5)); 
} 

Básicamente, mediante el uso de Find como el valor, no tenemos para suministrar un comparador, porque Find se compara con MS usando el campo que especifiquemos. Este es el mismo tipo de respuesta que usted vio aquí: how to sort STL vector, pero utilizando el valor en lugar del comparador como en ese caso. No estoy seguro de si sería genial usarlo, pero podría serlo, ya que especifica el valor para buscar y el campo para buscar en una sola expresión corta.

Answer 4

Tuve el mismo problema para std::equal_range y se me ocurrió una solución alternativa.

Tengo una colección de punteros a los objetos ordenados en un campo de tipo. Necesito encontrar el rango de objetos para un tipo dado.

const auto range = std::equal_range (next, blocks.end(), nullptr, 
    [type] (Object* o1, Object* o2) 
{ 
    return (o1 ? o1->Type() : type) < (o2 ? o2->Type() : type); 
}); 

Aunque es menos eficiente que un predicado dedicado, ya que introduce una prueba nullptr innecesaria para cada objeto en mi colección, proporciona una alternativa interesante.

Como nota aparte, cuando uso una clase como en su ejemplo, tiendo a hacer lo siguiente. Además de ser más corto, esto me permite agregar tipos adicionales con solo 1 función por tipo en lugar de 4 operadores por tipo.

class MSbTLess 
{ 
private: 
    static inline const double& value (const MS& val) 
    { 
     return val.bT; 
    } 

    static inline const double& value (const double& val) 
    { 
     return val; 
    } 

public: 
    template <typename T1, typename T2> 
    bool operator() (const T1& lhs, const T2& rhs) const 
    { 
     return value (t1) < value (t2); 
    } 
}; 

Answer 5

En los definition of lower_bound y otros algoritmos STL la función de comparación es tal que el primer tipo debe coincidir con la de la Forward Iterator y el segundo tipo debe coincidir con la de T (es decir, del valor).

template< class ForwardIt, class T, class Compare > 
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp); 

Así que uno puede comparar cosas de diferentes objetos (haciendo lo que la otra respuesta llamó un Comparador Unario). En C++ 11:

vector<MS> v = SomeSortedVectorofMSByFieldaT(); 
double a_key; 
auto it = std::lower_bound(v.begin(), 
          v.end(), 
          a_key, 
          []{const MS& m, const double& a) { 
          m.aT < a; 
          }); 

Y esto se puede utilizar también con otras funciones del algoritmo STL.