如何比较 C++ 中的泛型结构？

Question

我想以通用的方式比较结构，我已经做了这样的事情（我不能分享实际的来源，所以如果有必要，请询问更多细节）：

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

这主要按预期工作，但有时即使两个 struct 实例具有相同的成员（我已经使用 eclipse 调试器进行了检查），它也会返回 false。经过一番搜索，我发现memcmp由于使用的结构被填充，这可能会失败。

有没有更合适的方法来比较对填充无动于衷的内存？我无法修改使用的结构（它们是我正在使用的 API 的一部分），并且使用的许多不同结构具有一些不同的成员，因此无法以通用方式单独比较（据我所知）。

编辑：不幸的是，我被 C++11 困住了。应该早点提到这个...

Answer 1

你是对的，填充会妨碍你以这种方式比较任意类型。

您可以采取以下措施：

• 如果你在控制Data然后例如 gcc 有__attribute__((packed))。它对性能有影响，但可能值得一试。不过，我不得不承认，我不知道是否packed可以让您完全禁止填充。Gcc 文档说：

此属性附加到结构或联合类型定义，指定结构或联合的每个成员被放置以最小化所需的内存。当附加到枚举定义时，它表示应使用最小的整数类型。

• 如果您无法控制，Data那么至少std::has_unique_object_representations<T>可以告诉您您的比较是否会产生正确的结果：

如果 T 是 TriviallyCopyable 并且如果任何两个具有相同值的 T 类型对象具有相同的对象表示，则提供等于 true 的成员常量 value。对于任何其他类型，值为 false。

并进一步：

引入此特征是为了通过将其对象表示散列为字节数组来确定是否可以正确散列类型成为可能。

PS：我只解决了填充问题，但不要忘记，对于在内存中具有不同表示形式的实例，可以比较相等的类型绝非罕见（例如std::string，std::vector以及许多其他类型）。

Answer 2

No, memcmp is not suitable to do this. And reflection in C++ is insufficient to do this at this point (there are going to be experimental compilers that support reflection strong enough to do this already, and c++23 might have the features you need).

Without built-in reflection, the easiest way to solve your problem is to do some manual reflection.

Take this:

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

we want to do the minimal amount of work so we can compare two of these.

If we have:

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

or

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

for c++11, then:

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

does a pretty decent job.

We can extend this process to be recursive with a bit of work; instead of comparing ties, compare each element wrapped in a template, and that template's operator== recursively applies this rule (wrapping the element in as_tie to compare) unless the element already has a working ==, and handles arrays.

This will require a bit of a library (100ish lines of code?) together with writing a bit of manual per-member "reflection" data. If the number of structs you have is limited, it might be easier to write per-struct code manually.

There are probably ways to get

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

to generate the as_tie structure using horrible macros. But as_tie is simple enough. In c++11 the repetition is annoying; this is useful:

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

in this situation and many others. With RETURNS, writing as_tie is:

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

removing the repetition.

Here is a stab at making it recursive:

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) (fully recursive, even supports arrays-of-arrays):

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

Live example.

Here I use a std::array of refl_tie. This is much faster than my previous tuple of refl_tie at compile time.

Also

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

using std::cref here instead of std::tie could save on compile-time overhead, as cref is a much simpler class than tuple.

Finally, you should add

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

which will prevent array members from decaying to pointers and falling back on pointer-equality (which you probably don't want from arrays).

Without this, if you pass an array to a non-reflected struct in, it falls back on pointer-to-non-reflected struct refl_tie, which works and returns nonsense.

With this, you end up with a compile-time error.

Support for recursion through library types is tricky. You could std::tie them:

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

but that doesn't support recursion through it.

Answer 3

简而言之：不可能以通用的方式。

问题memcmp在于填充可能包含任意数据，因此memcmp可能会失败。如果有办法找出填充的位置，您可以将这些位清零，然后比较数据表示，如果成员是微不足道的，这将检查相等性（情况并非如此，即std::string因为两个字符串可以包含不同的指针，但指向的两个字符数组是相等的）。但我知道没有办法获得结构的填充。您可以尝试告诉您的编译器打包结构，但这会使访问变慢并且不能真正保证工作。

实现这一点的最简洁方法是比较所有成员。当然，这在通用方式中是不可能的（直到我们在 C++23 或更高版本中获得编译时反射和元类）。从 C++20 开始，可以生成默认值，operator<=>但我认为这也只能作为成员函数使用，因此，这又不是真的适用。如果你很幸运并且你想要比较的所有结构都有一个operator==定义，你当然可以使用它。但这并不能保证。

编辑：好的，实际上有一种完全hacky且有点通用的聚合方式。（我只写了对元组的转换，那些有一个默认的比较运算符）。神箭