c++ - electronica - ¿Qué son los comparadores transparentes?

comparador electronica

Question

En C ++ 14, los contenedores asociativos parecen haber cambiado de C ++ 11 - [asociative.reqmts] / 13 dice:

Las plantillas de función miembro find , count , lower_bound , upper_bound e equal_range no participarán en la resolución de sobrecarga a menos que exista el tipo Compare::is_transparent .

¿Cuál es el propósito de hacer un comparador "transparente"?

C ++ 14 también proporciona plantillas de biblioteca como esta:

template <class T = void> struct less {
    constexpr bool operator()(const T& x, const T& y) const;
    typedef T first_argument_type;
    typedef T second_argument_type;
    typedef bool result_type;
};

template <> struct less<void> {
    template <class T, class U> auto operator()(T&& t, U&& u) const
    -> decltype(std::forward<T>(t) < std::forward<U>(u));
    typedef *unspecified* is_transparent;
};

Entonces, por ejemplo, std::set<T, std::less<T>> no tendría un comparador transparente, pero std::set<T, std::less<>> tendría uno.

¿Qué problema soluciona esto y cambia esto cómo funcionan los contenedores estándar? Por ejemplo, los parámetros de plantilla de std::set siguen siendo Key, Compare = std::less<Key>, ... , ¿el conjunto predeterminado pierde sus miembros de find , count , etc.?

Answer 1

¿Qué problema soluciona esto?

Ver la respuesta de Dietmar y Remyabel.

y ¿esto cambia el funcionamiento de los contenedores estándar?

No, no de forma predeterminada.

Las sobrecargas de plantilla de función de miembro nuevo, etc., le permiten usar un tipo que sea comparable con la clave del contenedor, en lugar de utilizar el tipo de clave en sí. Ver N3465 por Joaquín Mª López Muñoz para una explicación razonada y una propuesta detallada y cuidadosamente escrita para agregar esta característica.

En la reunión de Bristol, el LWG acordó que la característica de búsqueda heterogénea era útil y deseable, pero no podíamos estar seguros de que la propuesta de Joaquín fuera segura en todos los casos. La propuesta N3465 habría causado serios problemas para algunos programas (consulte la sección Impacto en el código existente ). Joaquín preparó un proyecto de propuesta actualizado con algunas implementaciones alternativas con diferentes intercambios, lo que fue muy útil para ayudar al LWG a entender los pros y los contras, pero todos se arriesgaron a romper algunos programas de alguna manera, por lo que no hubo consenso para agregar la función. Decidimos que, si bien no sería seguro agregar la función de manera incondicional, sería seguro si se desactivara de manera predeterminada y solo "optara".

La diferencia clave de la propuesta N3657 (que fue una revisión de último minuto por mí y STL basada en N3465 y un borrador posterior no publicado de Joaquín) fue agregar el tipo is_transparent como el protocolo que se puede usar para is_transparent la nueva funcionalidad .

Si no utiliza un "functor transparente" (es decir, uno que defina un tipo is_transparent ), los contenedores se comportarán de la misma manera que siempre lo han hecho, y eso sigue siendo el predeterminado.

Si elige usar std::less<> (que es nuevo para C ++ 14) u otro tipo de "functor transparente", obtendrá la nueva funcionalidad.

Usar std::less<> es fácil con plantillas de alias:

template<typename T, typename Cmp = std::less<>, typename Alloc = std::allocator<T>>
  using set = std::set<T, Cmp, Alloc>;

El nombre is_transparent proviene de STL N3421 que agregó los "operadores de diamantes" a C ++ 14. Un "functor transparente" es aquel que acepta cualquier tipo de argumento (que no tiene que ser el mismo) y simplemente reenvía esos argumentos a otro operador. Tal functor resulta ser exactamente lo que desea para la búsqueda heterogénea en contenedores asociativos, por lo que el tipo is_transparent se agregó a todos los operadores de diamantes y se utilizó como tipo de etiqueta para indicar que la nueva funcionalidad debe habilitarse en contenedores asociativos. Técnicamente, los contenedores no necesitan un "functor transparente", solo uno que permite llamarlo con tipos heterogéneos (por ejemplo, el tipo pointer_comp en https://.com/a/18940595/981959 no es transparente según la definición de STL, pero definir pointer_comp::is_transparent permite que se use para resolver el problema). Si solo busca en su std::set<T, C> con las claves de tipo T o int entonces C solo necesita ser invocable con argumentos de tipo T e int (en cualquier orden), no es necesario que sea verdaderamente transparente. Usamos ese nombre en parte porque no pudimos encontrar un nombre mejor (hubiera preferido is_polymorphic porque esos funtores usan polimorfismo estático, pero ya existe un rasgo de tipo std::is_polymorphic que se refiere al polimorfismo dinámico).

Answer 2

En C ++ 11 no hay plantillas miembro find() , lower_bound() , etc. Es decir, nada se pierde con este cambio. Las plantillas miembro se introdujeron con n3657 para permitir el uso de claves heterogéneas con los contenedores asociativos. ¡No veo ningún ejemplo concreto donde esto sea útil, excepto por el ejemplo que es bueno y malo!

El uso de is_transparent está destinado a evitar conversiones no deseadas. Si las plantillas miembro no estaban restringidas, el código existente puede pasar directamente a través de los objetos que se habrían convertido sin las plantillas miembro. El caso de uso de ejemplo de n3657 es localizar un objeto en std::set<std::string> usando un literal de cadena: con la definición de C ++ 11 se construye un objeto std::string al pasar un literal de cadena al función miembro correspondiente. Con el cambio, es posible utilizar la cadena literal directamente. Si el objeto de la función de comparación subyacente se implementa exclusivamente en términos de std::string eso es malo porque ahora se crearía una std::string para cada comparación. Por otro lado, si el objeto de la función de comparación subyacente puede tomar una std::string y una cadena literal, eso puede evitar la construcción de un objeto temporal.

El tipo is_transparent anidado en el objeto de función de comparación proporciona una forma de especificar si se debe usar la función de miembro con plantilla: si el objeto de función de comparación puede tratar con argumentos heterogéneos, define este tipo para indicar que puede tratar diferentes argumentos de manera eficiente. Por ejemplo, los nuevos objetos de la función del operador simplemente delegan al operator<() y afirman ser transparentes. Eso, al menos, funciona para std::string que se ha sobrecargado menos que los operadores que toman char const* como argumento. Dado que estos objetos de función también son nuevos, incluso si hacen lo incorrecto (es decir, requieren una conversión para algún tipo), al menos no sería un cambio silencioso que daría lugar a una degradación del rendimiento.

Answer 3

Stephan T Lavavej habla sobre problemas donde el compilador sigue creando temporarios, y cómo su propuesta de funtores de operadores transparentes resolverá esto en c ++ 1a

GoingNative 2013 - No ayudes al compilador (alrededor de la hora marcada)

Answer 4

_{Lo siguiente es todo copia de pasta de N3657 .}

P. ¿Cuál es el propósito de hacer un comparador "transparente"?

R. Las funciones de búsqueda asociativa de contenedor (find, lower_bound, upper_bound, equal_range) solo toman un argumento de key_type, requiriendo que los usuarios construyan (implícita o explícitamente) un objeto de key_type para hacer la búsqueda. Esto puede ser costoso, por ejemplo, construir un objeto grande para buscar en un conjunto cuando la función del comparador solo mira un campo del objeto. Existe un fuerte deseo entre los usuarios de poder buscar utilizando otros tipos que son comparables con el tipo_clave.

Q. ¿Qué problema soluciona esto?

A. El LWG tenía dudas sobre el código como el siguiente:

std::set<std::string> s = /* ... */;
s.find("key");

En C ++ 11 esto construirá un único std :: string temporal y luego lo comparará con los elementos para encontrar la clave.

Con el cambio propuesto por N3465, la función std :: set :: find () sería una plantilla no restringida que pasaría el const char * a través de la función del comparador, std :: less, que construiría un std :: string temporal para cada comparación El LWG consideró este problema de rendimiento como un problema serio. La función find () de plantilla también evitaría encontrar NULL en un contenedor de punteros, lo que hace que el código previamente válido ya no se compile, pero esto se vio como un problema menos grave que la regresión del rendimiento silencioso

Q. ¿esto cambia el funcionamiento de los contenedores estándar?

R. Esta propuesta modifica los contenedores asociativos en y sobrecargando las funciones del miembro de búsqueda con plantillas de funciones miembro. No hay cambios de idioma

Q. también lo hace el conjunto predeterminado pierde sus miembros find, count, etc.

R. Casi todos los códigos existentes de C ++ 11 no se ven afectados porque las funciones miembro no están presentes a menos que se utilicen nuevas funciones de la biblioteca C ++ 14 como funciones de comparación.

Para citar a Yakk ,

En C ++ 14, std :: set :: find es una función de plantilla si existe Compare :: is_transparent. El tipo que ingrese no necesita ser clave, solo equivalente bajo su comparador.

y n3657,

Agregue el párrafo 13 en 23.2.4 [asociative.reqmts]: las plantillas de función miembro find, lower_bound, upper_bound e equal_range no participarán en la resolución de sobrecarga a menos que exista el tipo Compare :: is_transparent does exists.

n3421 proporciona un ejemplo de "Funcionadores de operador transparente" .

El código completo está aquí .