C++11 std::set función de comparación lambda

Question 1

quiero crear un std::set con una función de comparación personalizada. Podría definirlo como una clase con operator()pero quería disfrutar de la capacidad de definir una lambda donde se usa, así que decidí definir la función lambda en la lista de inicialización del constructor de la clase que tiene el std::set Como un miembro. Pero no puedo obtener el tipo de lambda. Antes de continuar, aquí hay un ejemplo:

class Foo
{
private:
     std::set<int, /*???*/> numbers;
public:
     Foo () : numbers ([](int x, int y)
                       {
                           return x < y;
                       })
     {
     }
};

Encontré dos soluciones después de buscar: una, usando std::function. Simplemente haga que el tipo de función de comparación establecida sea std::function<bool (int, int)> y pase la lambda exactamente como lo hice yo. La segunda solución es escribir una función make_set, como std::make_pair.

SOLUCIÓN 1:

class Foo
{
private:
     std::set<int, std::function<bool (int, int)> numbers;
public:
     Foo () : numbers ([](int x, int y)
                       {
                           return x < y;
                       })
     {
     }
};

SOLUCIÓN 2:

template <class Key, class Compare>
std::set<Key, Compare> make_set (Compare compare)
{
     return std::set<Key, Compare> (compare);
}

La pregunta es, ¿tengo una buena razón para preferir una solución sobre la otra? Prefiero la primera porque hace uso de funciones estándar (make_set no es una función estándar), pero me pregunto: ¿usar std::function hacer el código (potencialmente) más lento? Quiero decir, ¿reduce la posibilidad de que el compilador inserte la función de comparación, o debería ser lo suficientemente inteligente como para comportarse exactamente igual que si fuera un tipo de función lambda y no std::function (Lo sé, en este caso no puede ser un tipo lambda, pero ya sabes, estoy preguntando en general)?

(Uso GCC, pero me gustaría saber qué hacen los compiladores populares en general)

RESUMEN, DESPUÉS DE OBTENER MUCHAS RESPUESTAS EXCELENTES:

Si la velocidad es crítica, la mejor solución es usar una clase con operator() también conocido como funtor. Es más fácil para el compilador optimizar y evitar cualquier indirección.

Para un fácil mantenimiento y una mejor solución de propósito general, usando las características de C++11, use std::function. Todavía es rápido (solo un poco más lento que el functor, pero puede ser insignificante) y puede usar cualquier función: std::functionlambda, cualquier objeto invocable.

También hay una opción para usar un puntero de función, pero si no hay un problema de velocidad, creo std::function es mejor (si usa C++ 11).

Hay una opción para definir la función lambda en otro lugar, pero luego no gana nada con que la función de comparación sea una expresión lambda, ya que también podría convertirla en una clase con operator() y la ubicación de la definición no sería la construcción del conjunto de todos modos.

Hay más ideas, como usar la delegación. Si desea una explicación más detallada de todas las soluciones, lea las respuestas 🙂

Question 2

Es poco probable que el compilador pueda alinear una llamada std::function, mientras que cualquier compilador que admita lambdas seguramente alinearía la versión del funtor, incluso si ese funtor es un lambda no oculto por un std::function.

podrías usar decltype para obtener el tipo de comparador de lambda:

#include <set>
#include <iostream>
#include <iterator>
#include <algorithm>

int main()
{
   auto comp = [](int x, int y){ return x < y; };
   auto set  = std::set<int,decltype(comp)>( comp );

   set.insert(1);
   set.insert(10);
   set.insert(1); // Dupe!
   set.insert(2);

   std::copy( set.begin(), set.end(), std::ostream_iterator<int>(std::cout, "\n") );
}

Que imprime:

1
2
10

Véalo en vivo en Colirú.

Question 3

Sí un std::function introduce un desvío casi inevitable a su set. Si bien el compilador siempre puede, en teoría, darse cuenta de que todo uso de su set‘s std::function implica invocarlo en una lambda que es siempre exactamente la misma lambda, que es a la vez dura y extremadamente frágil.

Frágil, porque antes de que el compilador pueda probarse a sí mismo que todas las llamadas a ese std::function en realidad son llamadas a su lambda, debe probar que no tiene acceso a su std::set alguna vez establece el std::function a cualquier cosa menos a tu lambda. Lo que significa que tiene que rastrear todas las rutas posibles para llegar a su std::set en todas las unidades de compilación y probar que ninguno de ellos lo hace.

Esto podría ser posible en algunos casos, pero cambios relativamente inocuos podrían romperlo incluso si su compilador logró probarlo.

Por otro lado, un funtor con un stateless operator() tiene un comportamiento fácil de probar, y las optimizaciones que involucran eso son cosas cotidianas.

Así que sí, en la práctica sospecharía std::function podría ser más lento. Por otra parte, std::function La solución es más fácil de mantener que la make_set one, e intercambiar el tiempo del programador por el rendimiento del programa es bastante fungible.

make_set tiene la seria desventaja de que cualquier setEl tipo de debe inferirse de la llamada a make_set. A menudo un set almacena el estado persistente, y no algo que creas en la pila y luego lo dejas fuera de alcance.

Si creó una lambda sin estado estática o global auto MyComp = [](A const&, A const&)->bool { ... }puedes usar el std::set<A, decltype(MyComp)> sintaxis para crear un set que puede persistir, pero es fácil de optimizar para el compilador (porque todas las instancias de decltype(MyComp) son funtores sin estado) y en línea. Señalo esto, porque usted está pegando el set en un struct. (¿O su compilador admite

struct Foo {
  auto mySet = make_set<int>([](int l, int r){ return l<r; });
};

¡lo cual me parecería sorprendente!)

Finalmente, si le preocupa el rendimiento, tenga en cuenta que std::unordered_set es mucho más rápido (a costa de no poder iterar sobre los contenidos en orden, y tener que escribir/encontrar un buen hash), y que un ordenado std::vector es mejor si tiene un “insertar todo” de 2 fases y luego “consultar contenidos repetidamente”. Simplemente métalo en el vector primero luego sort unique eraseluego use el libre equal_range algoritmo.

Question 4

Una lambda sin estado (es decir, una sin capturas) puede decaer en un puntero de función, por lo que su tipo podría ser:

std::set<int, bool (*)(int, int)> numbers;

De lo contrario iría por el make_set solución. Si no usa una función de creación de una línea porque no es estándar, ¡no obtendrá mucho código escrito!

Question 5

Si estás decidido a tener la set como miembro de la clase, inicializando su comparador en el momento del constructor, entonces al menos un nivel de direccionamiento indirecto es inevitable. Considere que, por lo que sabe el compilador, podría agregar otro constructor:

 Foo () : numbers ([](int x, int y)
                   {
                       return x < y;
                   })
 {
 }

 Foo (char) : numbers ([](int x, int y)
                   {
                       return x > y;
                   })
 {
 }

Una vez que tenga un objeto de tipo Fooel tipo de set no contiene información sobre qué constructor inicializó su comparador, por lo que llamar a la lambda correcta requiere una indirección a la lambda seleccionada en tiempo de ejecución operator().

Como está usando lambdas sin captura, podría usar el tipo de puntero de función bool (*)(int, int) como su tipo de comparación, ya que las lambdas sin captura tienen la función de conversión adecuada. Por supuesto, esto implicaría una indirección a través del puntero de función.

Question 6

La diferencia depende en gran medida de las optimizaciones de su compilador. Si optimiza lambda en un std::function esos son equivalentes, si no introduces una indirección en el primero que no tendrás en el segundo.

¿Ha sido útil esta solución?