¿Cómo comparar estructuras genéricas en C ++?

13

Quiero comparar estructuras de forma genérica y he hecho algo como esto (no puedo compartir la fuente real, así que solicite más detalles si es necesario):

template<typename Data>
bool structCmp(Data data1, Data data2)
{
  void* dataStart1 = (std::uint8_t*)&data1;
  void* dataStart2 = (std::uint8_t*)&data2;
  return memcmp(dataStart1, dataStart2, sizeof(Data)) == 0;
}

Esto funciona principalmente según lo previsto, excepto que a veces devuelve falso a pesar de que las dos instancias de estructura tienen miembros idénticos (lo he comprobado con el depurador eclipse). Después de algunas búsquedas descubrí que memcmppuede fallar debido a que la estructura utilizada está rellenada.

¿Hay una forma más adecuada de comparar la memoria que es indiferente al relleno? No puedo modificar las estructuras utilizadas (son parte de una API que estoy usando) y las muchas estructuras diferentes utilizadas tienen algunos miembros diferentes y, por lo tanto, no se pueden comparar individualmente de forma genérica (que yo sepa).

Editar: desafortunadamente estoy atascado con C ++ 11. Debería haber mencionado esto antes ...

Fredrik Enetorp
fuente
¿Puedes mostrar un ejemplo donde esto falla? El relleno debe ser el mismo para todas las instancias de un tipo, ¿no?
idclev 463035818
1
@ idclev463035818 El relleno no está especificado, no puedes asumir que es un valor y creo que es UB para intentar leerlo (no estoy seguro en esa última parte).
François Andrieux
@ idclev463035818 El relleno está en los mismos lugares relativos en la memoria, pero puede tener datos diferentes. Se descarta en los usos normales de la estructura para que el compilador no se moleste en ponerla a cero.
NO_NAME
2
@ idclev463035818 El relleno tiene el mismo tamaño. El estado de los bits que constituyen ese relleno puede ser cualquier cosa. Cuando memcmpincluye esos bits de relleno en su comparación.
François Andrieux
1
Estoy de acuerdo con Yksisarvinen ... use clases, no estructuras e implemente el ==operador. El uso memcmpno es confiable, y tarde o temprano tendrás que lidiar con alguna clase que tiene que "hacerlo un poco diferente de las demás". Es muy limpio y eficiente implementar eso en un operador. El comportamiento real será polimórfico pero el código fuente estará limpio ... y, obviamente.
Mike Robinson

Respuestas:

7

No, memcmpno es adecuado para hacer esto. Y la reflexión en C ++ es insuficiente para hacer esto en este momento (habrá compiladores experimentales que admitirán la reflexión lo suficientemente fuerte como para hacerlo ya, y podría tener las características que necesita).

Sin una reflexión incorporada, la forma más fácil de resolver su problema es hacer una reflexión manual.

Toma esto:

struct some_struct {
  int x;
  double d1, d2;
  char c;
};

queremos hacer la mínima cantidad de trabajo para poder comparar dos de estos.

Si tenemos:

auto as_tie(some_struct const& s){ 
  return std::tie( s.x, s.d1, s.d2, s.c );
}

o

auto as_tie(some_struct const& s)
-> decltype(std::tie( s.x, s.d1, s.d2, s.c ))
{
  return std::tie( s.x, s.d1, s.d2, s.c );
}

para , entonces:

template<class S>
bool are_equal( S const& lhs, S const& rhs ) {
  return as_tie(lhs) == as_tie(rhs);
}

hace un trabajo bastante decente.

Podemos extender este proceso para que sea recursivo con un poco de trabajo; en lugar de comparar vínculos, compare cada elemento envuelto en una plantilla, y esa plantilla operator==aplica esta regla de manera recursiva (ajustando el elemento as_tiepara comparar) a menos que el elemento ya tenga un funcionamiento ==y maneje matrices.

Esto requerirá un poco de una biblioteca (¿100 líneas de código?) Junto con la escritura de un poco de datos de "reflexión" manuales por miembro. Si el número de estructuras que tiene es limitado, podría ser más fácil escribir el código por estructura manualmente.


Probablemente hay formas de obtener

REFLECT( some_struct, x, d1, d2, c )

para generar la as_tieestructura usando macros horribles. Pero as_tiees lo suficientemente simple. En la repetición es molesta; esto es útil:

#define RETURNS(...) \
  noexcept(noexcept(__VA_ARGS__)) \
  -> decltype(__VA_ARGS__) \
  { return __VA_ARGS__; }

En esta situación y en muchas otras. Con RETURNS, la escritura as_tiees:

auto as_tie(some_struct const& s)
  RETURNS( std::tie( s.x, s.d1, s.d2, s.c ) )

eliminando la repetición.


Aquí hay una puñalada para hacerlo recursivo:

template<class T,
  typename std::enable_if< !std::is_class<T>{}, bool>::type = true
>
auto refl_tie( T const& t )
  RETURNS(std::tie(t))

template<class...Ts,
  typename std::enable_if< (sizeof...(Ts) > 1), bool>::type = true
>
auto refl_tie( Ts const&... ts )
  RETURNS(std::make_tuple(refl_tie(ts)...))

template<class T, std::size_t N>
auto refl_tie( T const(&t)[N] ) {
  // lots of work in C++11 to support this case, todo.
  // in C++17 I could just make a tie of each of the N elements of the array?

  // in C++11 I might write a custom struct that supports an array
  // reference/pointer of fixed size and implements =, ==, !=, <, etc.
}

struct foo {
  int x;
};
struct bar {
  foo f1, f2;
};
auto refl_tie( foo const& s )
  RETURNS( refl_tie( s.x ) )
auto refl_tie( bar const& s )
  RETURNS( refl_tie( s.f1, s.f2 ) )

refl_tie (array) (totalmente recursivo, incluso admite matrices de matrices):

template<class T, std::size_t N, std::size_t...Is>
auto array_refl( T const(&t)[N], std::index_sequence<Is...> )
  RETURNS( std::array<decltype( refl_tie(t[0]) ), N>{ refl_tie( t[Is] )... } )

template<class T, std::size_t N>
auto refl_tie( T(&t)[N] )
  RETURNS( array_refl( t, std::make_index_sequence<N>{} ) )

Ejemplo en vivo .

Aquí uso un std::arrayde refl_tie. Esto es mucho más rápido que mi tupla anterior de refl_tie en tiempo de compilación.

también

template<class T,
  typename std::enable_if< !std::is_class<T>{}, bool>::type = true
>
auto refl_tie( T const& t )
  RETURNS(std::cref(t))

usar std::crefaquí en lugar de std::tiepodría ahorrar tiempo de compilación, ya que crefes una clase mucho más simple que tuple.

Finalmente, deberías agregar

template<class T, std::size_t N, class...Ts>
auto refl_tie( T(&t)[N], Ts&&... ) = delete;

lo que evitará que los miembros de la matriz se descompongan en punteros y vuelvan a caer en la igualdad de puntero (que probablemente no desee de las matrices).

Sin esto, si pasa una matriz a una estructura no reflejada, recurre a una estructura de puntero a no reflejada refl_tie, que funciona y devuelve tonterías.

Con esto, terminas con un error en tiempo de compilación.


El soporte para la recursividad a través de tipos de biblioteca es complicado. Podrías std::tieellos:

template<class T, class A>
auto refl_tie( std::vector<T, A> const& v )
  RETURNS( std::tie(v) )

pero eso no admite la recursividad a través de él.

Yakk - Adam Nevraumont
fuente
Me gustaría buscar este tipo de solución con reflexiones manuales. El código que proporcionó no parece funcionar con C ++ 11. ¿Alguna posibilidad de que puedas ayudarme con eso?
Fredrik Enetorp
1
La razón por la que esto no funciona en C ++ 11 es la falta de tipo de retorno final as_tie. A partir de C ++ 14, esto se deduce automáticamente. Puede usar auto as_tie (some_struct const & s) -> decltype(std::tie(s.x, s.d1, s.d2, s.c));en C ++ 11. O indique explícitamente el tipo de retorno.
Darhuuk
1
@FredrikEnetorp Corregido, más una macro que facilita la escritura. El trabajo para lograr que funcione de forma totalmente recursiva (por lo que una estructura de estructura, donde las subestructuras tienen as_tiesoporte, funciona automáticamente) y los miembros de la matriz de soporte no están detallados, pero es posible.
Yakk - Adam Nevraumont
Gracias. Hice las macros horribles de manera ligeramente diferente, pero funcionalmente equivalente. Solo un problema más. Estoy tratando de generalizar la comparación en un archivo de encabezado separado e incluirlo en varios archivos de prueba de gmock. Esto da como resultado el mensaje de error: definición múltiple de `as_tie (Test1 const &) 'Estoy tratando de alinearlos pero no puedo hacer que funcione.
Fredrik Enetorp
1
@FredrikEnetorp La inlinepalabra clave debería hacer que desaparezcan los errores de definición múltiple. Use el botón [preguntar] después de obtener un ejemplo reproducible mínimo
Yakk - Adam Nevraumont
7

Tiene razón en que el relleno interfiere en su forma de comparar tipos arbitrarios de esta manera.

Hay medidas que puede tomar:

  • Si usted tiene el control de Data, por ejemplo, gcc tiene __attribute__((packed)). Tiene impacto en el rendimiento, pero puede valer la pena intentarlo. Sin embargo, debo admitir que no sé si le packedpermite no permitir el relleno por completo. Gcc doc dice:

Este atributo, asociado a la definición de tipo de estructura o unión, especifica que cada miembro de la estructura o unión se coloca para minimizar la memoria requerida. Cuando se adjunta a una definición de enumeración, indica que se debe usar el tipo integral más pequeño.

Si T es TriviallyCopyable y si dos objetos del tipo T con el mismo valor tienen la misma representación de objeto, proporciona el valor constante del miembro igual a verdadero. Para cualquier otro tipo, el valor es falso.

y además:

Este rasgo se introdujo para que sea posible determinar si un tipo se puede cifrar correctamente mediante el hash de su representación de objeto como una matriz de bytes.

PD: solo abordé el relleno, pero no olvide que los tipos que se pueden comparar para instancias con representación diferente en la memoria no son raros (por ejemplo std::string, std::vectory muchos otros).

idclev 463035818
fuente
1
Me gusta esta respuesta Con este rasgo de tipo, puede usar SFINAE para usar memcmpen estructuras sin relleno e implementar operator==solo cuando sea necesario.
Yksisarvinen
OK gracias. Con esto puedo concluir con seguridad que necesito hacer algunas reflexiones manuales.
Fredrik Enetorp
6

En resumen: no es posible de forma genérica.

El problema memcmpes que el relleno puede contener datos arbitrarios y, por lo tanto, memcmppuede fallar. Si hubiera una manera de averiguar dónde está el relleno, podría poner a cero esos bits y luego comparar las representaciones de datos, eso verificaría la igualdad si los miembros son trivialmente comparables (lo cual no es el caso, es decir, std::stringya que dos cadenas pueden contienen punteros diferentes, pero los dos conjuntos de caracteres puntiagudos son iguales). Pero no conozco ninguna forma de llegar al relleno de estructuras. Puede intentar decirle a su compilador que empaque las estructuras, pero esto hará que los accesos sean más lentos y realmente no está garantizado para funcionar.

La forma más limpia de implementar esto es comparar a todos los miembros. Por supuesto, esto no es realmente posible de forma genérica (hasta que obtengamos reflexiones de tiempo de compilación y metaclases en C ++ 23 o posterior). Desde C ++ 20 en adelante, uno podría generar un valor predeterminado, operator<=>pero creo que esto también solo sería posible como función miembro, por lo que, nuevamente, esto no es realmente aplicable. Si tiene suerte y todas las estructuras que desea comparar tienen una operator==definida, puede, por supuesto, usarla. Pero eso no está garantizado.

EDITAR: Ok, en realidad hay una forma totalmente hacky y algo genérica para los agregados. (Solo escribí la conversión a tuplas, esas tienen un operador de comparación predeterminado). perno

n314159
fuente
Buen truco! Desafortunadamente, estoy atascado con C ++ 11, así que no puedo usarlo.
Fredrik Enetorp
2

C ++ 20 admite comaparisons predeterminados

#include <iostream>
#include <compare>

struct XYZ
{
    int x;
    char y;
    long z;

    auto operator<=>(const XYZ&) const = default;
};

int main()
{
    XYZ obj1 = {4,5,6};
    XYZ obj2 = {4,5,6};

    if (obj1 == obj2)
    {
        std::cout << "objects are identical\n";
    }
    else
    {
        std::cout << "objects are not identical\n";
    }
    return 0;
}
selbie
fuente
1
Si bien esa es una característica muy útil, no responde la pregunta como se le preguntó. El OP dijo "No puedo modificar las estructuras utilizadas", lo que significa que, incluso si los operadores de igualdad predeterminados de C ++ 20 estuvieran disponibles, el OP no podría usarlos ya que los operadores predeterminados ==o <=>solo se pueden hacer en el alcance de la clase.
Nicol Bolas
Como dijo Nicol Bolas, no puedo modificar las estructuras.
Fredrik Enetorp
1

Suponiendo datos POD, el operador de asignación predeterminado copia solo los bytes miembros. (en realidad no estoy 100% seguro de eso, no confíes en mi palabra)

Puedes usar esto a tu favor:

template<typename Data>
bool structCmp(Data data1, Data data2) // Data is POD
{
  Data tmp;
  memcpy(&tmp, &data1, sizeof(Data)); // copy data1 including padding
  tmp = data2;                        // copy data2 only members
  return memcmp(&tmp, &data1, sizeof(Data)) == 0; 
}
Kostas
fuente
@walnut Tienes razón, esa fue una respuesta terrible. Reescribió uno.
Kostas
¿El estándar garantiza que la asignación deja intactos los bytes de relleno? También existe una preocupación por las representaciones de objetos múltiples para el mismo valor en tipos fundamentales.
nogal
@walnut Creo que sí .
Kostas
1
Los comentarios debajo de la respuesta superior en ese enlace parecen indicar que no es así. La respuesta en sí sólo dice que el relleno no tiene por qué ser copiado, pero no que no debes . Sin embargo, tampoco estoy seguro.
nogal
Ahora lo he probado y no funciona. La asignación no deja los bytes de relleno intactos.
Fredrik Enetorp
0

Creo que puede basar una solución en el vudú maravillosamente tortuoso de Antony Polukhin en la magic_getbiblioteca, para estructuras, no para clases complejas.

Con esa biblioteca, podemos iterar los diferentes campos de una estructura, con su tipo apropiado, en código de plantilla puramente general. Antony ha utilizado esto, por ejemplo, para poder transmitir estructuras arbitrarias a una secuencia de salida con los tipos correctos, de forma completamente genérica. Es lógico pensar que la comparación también podría ser una posible aplicación de este enfoque.

... pero necesitarías C ++ 14. Al menos es mejor que las sugerencias de C ++ 17 y posteriores en otras respuestas :-P

einpoklum
fuente