Como comparar estruturas genéricas em C ++?

Quero comparar estruturas de uma maneira genérica e fiz algo parecido com isto (não posso compartilhar a fonte real, portanto, solicite mais detalhes, se necessário):

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

Isso funciona principalmente como planejado, exceto que, às vezes, retorna false, mesmo que as duas instâncias struct tenham membros idênticos (verifiquei com o depurador do eclipse). Depois de algumas pesquisas, descobri que memcmppode falhar devido ao uso da estrutura usada.

Existe uma maneira mais adequada de comparar a memória indiferente ao preenchimento? Não consigo modificar as estruturas usadas (elas fazem parte de uma API que estou usando) e as muitas estruturas diferentes usadas têm alguns membros diferentes e, portanto, não podem ser comparadas individualmente de maneira genérica (pelo que sei).

Edit: infelizmente estou preso com C ++ 11. Deveria ter mencionado isso antes ...

Não, memcmpnão é adequado para fazer isso. E a reflexão no C ++ é insuficiente para fazer isso neste momento (haverá compiladores experimentais que suportam a reflexão suficientemente forte para fazer isso, e o c ++ 23 pode ter os recursos necessários).

Sem reflexão interna, a maneira mais fácil de resolver seu problema é fazer uma reflexão manual.

Pegue isso:

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

queremos fazer a quantidade mínima de trabalho para comparar dois deles.

Se tiver-mos:

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

ou

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 c ++ 11 , então:

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

faz um trabalho bastante decente.

Podemos estender esse processo para ser recursivo com um pouco de trabalho; em vez de comparar laços, compare cada elemento envolvido em um modelo e o modelo operator==aplica recursivamente essa regra (envolvendo o elemento as_tiepara comparação), a menos que o elemento já tenha um funcionamento ==e lida com matrizes.

Isso exigirá um pouco de uma biblioteca (100 linhas de código?), Juntamente com a gravação de um pouco de dados manuais de "reflexão" por membro. Se o número de estruturas que você possui é limitado, pode ser mais fácil escrever o código por estrutura manualmente.

Provavelmente existem maneiras de obter

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

para gerar a as_tieestrutura usando macros horríveis. Mas as_tieé bastante simples. Em c ++ 11, a repetição é irritante; isso é útil:

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

nesta situação e em muitas outras. Com RETURNS, escrever as_tieé:

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

removendo a repetição.

Aqui está uma facada em torná-lo 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 ) )

c ++ 17 refl_tie (array) (totalmente recursivo, até suporta matrizes de matrizes):

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>{} ) )

Exemplo ao vivo .

Aqui eu uso um std::arraydos refl_tie. Isso é muito mais rápido que minha tupla anterior de refl_tie em tempo de compilação.

Além disso

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::crefaqui em vez de std::tiepoderia economizar em custos adicionais em tempo de compilação, como crefé uma classe muito mais simples que tuple.

Por fim, você deve adicionar

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

o que impedirá que os membros da matriz se deteriorem para ponteiros e retornem à igualdade de ponteiros (o que você provavelmente não deseja das matrizes).

Sem isso, se você passar uma matriz para uma estrutura não refletida, ela recai na estrutura ponteiro para não refletida refl_tie, que funciona e retorna um disparate.

Com isso, você acaba com um erro em tempo de compilação.

O suporte à recursão através dos tipos de biblioteca é complicado. Você poderia std::tie:

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

mas isso não suporta recursão por meio dele.

Você está certo de que o preenchimento interfere na comparação de tipos arbitrários dessa maneira.

Existem medidas que você pode tomar:

• Se você está no controle Data, por exemplo, o gcc possui __attribute__((packed)). Isso afeta o desempenho, mas pode valer a pena tentar. No entanto, devo admitir que não sei se packedpermite que você desaprove completamente o preenchimento. O documento do Gcc diz:

Este atributo, anexado à definição de tipo de estrutura ou união, especifica que cada membro da estrutura ou união é colocado para minimizar a memória necessária. Quando anexado a uma definição de enumeração, indica que o menor tipo integral deve ser usado.

• Se você não está no controle Data, pelo menos std::has_unique_object_representations<T>pode dizer se sua comparação produzirá resultados corretos:

Se T for TriviallyCopyable e se dois objetos do tipo T com o mesmo valor tiverem a mesma representação, o valor constante do membro será igual a true. Para qualquer outro tipo, o valor é falso.

e ainda mais:

Essa característica foi introduzida para possibilitar determinar se um tipo pode ser corretamente dividido por hash, hash sua representação de objeto como uma matriz de bytes.

PS: Abordei apenas o preenchimento, mas não esqueço que tipos que podem ser comparados em instâncias com diferentes representações na memória não são raros (por exemplo std::string, std::vectore muitos outros).

Em resumo: não é possível de maneira genérica.

O problema memcmpé que o preenchimento pode conter dados arbitrários e, portanto, memcmppode falhar. Se houvesse uma maneira de descobrir onde está o preenchimento, você poderia zerar esses bits e comparar as representações de dados, que verificariam a igualdade se os membros fossem trivialmente comparáveis ​​(o que não é o caso, ou seja, std::stringjá que duas strings podem contêm ponteiros diferentes, mas as duas matrizes apontadas são iguais). Mas não sei como chegar ao preenchimento de estruturas. Você pode tentar dizer ao seu compilador para compactar as estruturas, mas isso tornará os acessos mais lentos e não é realmente garantido que funcione.

A maneira mais limpa de implementar isso é comparar todos os membros. Obviamente, isso não é realmente possível de uma maneira genérica (até obtermos reflexões de tempo de compilação e meta classes no C ++ 23 ou posterior). A partir do C ++ 20 em diante, pode-se gerar um padrão, operator<=>mas acho que isso também só seria possível como uma função membro, portanto, novamente isso não é realmente aplicável. Se você tiver sorte e todas as estruturas que deseja comparar tiverem uma operator==definição, é claro que você pode apenas usar isso. Mas isso não é garantido.

EDIT: Ok, existe realmente uma maneira totalmente hacky e um tanto genérica para agregados. (Eu escrevi apenas a conversão para tuplas, elas têm um operador de comparação padrão). godbolt

C ++ 20 suporta comaparisons padrão

#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;
}

Supondo dados POD, o operador de atribuição padrão copia apenas bytes de membro. (na verdade, não tenho 100% de certeza disso, não aceite minha palavra)

Você pode utilizar isto para o seu benefício:

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

Acredito que você possa basear uma solução no vodu maravilhosamente desonesto de Antony Polukhin na magic_getbiblioteca - para estruturas, não para classes complexas.

Com essa biblioteca, podemos iterar os diferentes campos de uma estrutura, com seu tipo apropriado, no código de modelo puramente geral. Antony usou isso, por exemplo, para poder transmitir streams arbitrários para um stream de saída com os tipos corretos, de maneira completamente genérica. É lógico que a comparação também possa ser uma aplicação possível dessa abordagem.

... mas você precisaria de C ++ 14. Pelo menos é melhor que o C ++ 17 e sugestões posteriores em outras respostas :-P