Как сравнить generi c структуры в C ++? - PullRequest
13 голосов
/ 05 февраля 2020

Я хочу сравнить структуры общим образом c, и я сделал что-то вроде этого (я не могу поделиться фактическим источником, поэтому при необходимости попросите более подробную информацию):

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

Это в основном работает так, как задумано, за исключением того, что иногда он возвращает false, хотя два экземпляра структуры имеют идентичные члены (я проверял с помощью отладчика eclipse). После некоторых поисков я обнаружил, что memcmp может потерпеть неудачу из-за заполнения используемой структуры.

Есть ли более правильный способ сравнения памяти, который безразличен для заполнения? Я не могу изменить используемые структуры (они являются частью API, который я использую), и многие различные используемые структуры имеют несколько различных членов и, следовательно, не могут сравниваться по отдельности общим образом c (насколько мне известно ).

Редактировать: К сожалению, я застрял с C ++ 11. Должен был упомянуть об этом раньше ...

Ответы [ 6 ]

7 голосов
/ 05 февраля 2020

Нет, memcmp не подходит для этого. И рефлексии в C ++ недостаточно для того, чтобы сделать это на данный момент (будут экспериментальные компиляторы, которые уже достаточно сильны для рефлексии, чтобы сделать это, и может иметь необходимые вам функции).

Без встроенного отражения, самый простой способ решить вашу проблему - это сделать ручное отражение.

Возьмем это:

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

мы хотим сделать минимальное количество работы, чтобы мы могли сравнить два из них.

Если у нас есть:

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

или

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

для , тогда:

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

делает довольно приличную работу.

Мы можем расширить этот процесс, чтобы он был рекурсивным с небольшим количеством работы; вместо сравнения связей сравнивайте каждый элемент, обернутый в шаблон, и operator== этого шаблона рекурсивно применяет это правило (оборачивая элемент в as_tie для сравнения), если элемент уже не имеет работающего == и не обрабатывает массивы.

Для этого потребуется немного библиотеки (100i sh строк кода?) Вместе с записью небольшого количества ручных данных "отражения" для каждого члена. Если количество имеющихся у вас структур ограничено, возможно, было бы проще написать код для каждой структуры вручную.


Возможно, есть способы получить

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

для генерации as_tie структура с использованием ужасных макросов. Но as_tie достаточно просто. В повторение раздражает; это полезно:

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

в этой ситуации и многие другие. С RETURNS, запись as_tie означает:

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

удаление повторения.


Вот попытка сделать его рекурсивным:

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_t ie (массив) (полностью рекурсивный, даже поддерживает массивы массивов):

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

Живой пример .

Здесь я использую std::array из refl_tie. Это намного быстрее, чем мой предыдущий кортеж refl_t ie во время компиляции.

Также

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

с использованием std::cref здесь вместо std::tie может сэкономить на издержках времени компиляции , поскольку cref является гораздо более простым классом, чем tuple.

Наконец, вы должны добавить

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

, что предотвратит распад членов массива на указатели и откат к указателю. равенство (которое вы, вероятно, не хотите использовать для массивов).

Без этого, если вы передадите массив в неотраженную структуру, он возвращается к указателю на неотраженную структуру refl_tie , который работает и возвращает бессмыслицу.

При этом вы получите ошибку времени компиляции.


Поддержка рекурсии по типам библиотек довольно сложна. Вы можете std::tie их:

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

, но это не поддерживает рекурсию через него.

7 голосов
/ 05 февраля 2020

Вы правы, что заполнение мешает вам сравнивать произвольные типы таким способом.

Вы можете предпринять следующие меры:

  • Если вы контролируете Data, то, например, g cc имеет __attribute__((packed)). Это влияет на производительность, но, возможно, стоит попробовать. Однако я должен признать, что не знаю, позволяет ли packed полностью запретить заполнение. G cc do c говорит:

Этот атрибут, прикрепленный к определению типа структуры или объединения, указывает, что каждый член структуры или объединения размещается чтобы минимизировать требуемую память. При присоединении к определению перечисления это означает, что следует использовать наименьший целочисленный тип.

  • Если вы не управляете Data, то по крайней мере std::has_unique_object_representations<T> может сказать вам, если ваше сравнение даст правильные результаты:

Если T является TriviallyCopyable и если любые два объекта типа T с одинаковым значением имеют одинаковое представление объекта, предоставляет член постоянное значение равно истине. Для любого другого типа значение равно false.

и далее:

Эта черта была введена, чтобы дать возможность определить, можно ли правильно хешировать тип, хэшируя его представление объекта в виде байтового массива.

PS: я занимался только заполнением, но не забывайте, что типы, которые могут сравнивать одинаковые для экземпляров с различным представлением в памяти, ни в коем случае не редкость (например, std::string, std::vector и многие другие) .

6 голосов
/ 05 февраля 2020

Вкратце: невозможно в общем случае c.

Проблема с memcmp заключается в том, что заполнение может содержать произвольные данные и, следовательно, memcmp может завершиться ошибкой. Если бы был способ выяснить, где находится заполнение, вы могли бы обнулить эти биты и затем сравнить представления данных, что проверило бы на равенство, если бы члены были тривиально сопоставимы (что не так, т.е. для std::string, так как две строки могут содержать разные указатели, но два указанных символьных массива равны). Но я не знаю способа добраться до заполнения структур. Вы можете попросить ваш компилятор упаковать структуры, но это замедлит доступ и на самом деле не гарантирует его работу.

Самый простой способ реализовать это - сравнить все элементы. Конечно, это не возможно в общем случае c (пока мы не получим отражения времени компиляции и мета-классы в C ++ 23 или более поздней версии). Начиная с C ++ 20, можно генерировать значение по умолчанию operator<=>, но я думаю, что это также возможно только в качестве функции-члена, поэтому, опять же, это не совсем применимо. Если вам повезло, и все структуры, которые вы хотите сравнить, имеют operator==, вы, конечно, можете просто использовать это. Но это не гарантируется.

РЕДАКТИРОВАТЬ: Хорошо, на самом деле есть совершенно хакерский и несколько общий c способ для агрегатов. (Я только написал преобразование в кортежи, у них есть оператор сравнения по умолчанию). godbolt

2 голосов
/ 05 февраля 2020

C ++ 20 поддерживает сопоставления по умолчанию

#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;
}
1 голос
/ 05 февраля 2020

Предполагая данные POD, оператор присваивания по умолчанию копирует только байты-члены. (на самом деле не уверен на 100%, не поверьте мне на слово)

Вы можете использовать это в своих интересах:

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; 
}
0 голосов
/ 29 февраля 2020

Я полагаю, что вы можете основать решение на удивительно коварном вуду Антония Полухина в библиотеке magic_get - для структур, а не для сложных классов.

С этой библиотекой, мы можем перебирать различные поля структуры с их соответствующим типом в чисто общем шаблонном коде. Энтони, например, использовал это, чтобы иметь возможность потоковой передачи произвольных структур в выходной поток с правильными типами, совершенно обобщенно. Само собой разумеется, что сравнение также может быть возможным применением этого подхода.

... но вам потребуется C ++ 14. По крайней мере, это лучше, чем C ++ 17 и последующие предложения в других ответах: -P

...