Подтвердить что ты не робот

Определение оператора <для структуры

Я иногда использую маленькие structs как ключи на картах, поэтому мне нужно определить operator< для них. Обычно это выглядит примерно так:

struct MyStruct
{
    A a;
    B b;
    C c;

    bool operator<(const MyStruct& rhs) const
    {
        if (a < rhs.a)
        {
           return true;
        }
        else if (a == rhs.a)
        {
            if (b < rhs.b)
            {
                return true;
            }
            else if (b == rhs.b)
            {
                return c < rhs.c;
            }
        }

        return false;
    }
};

Это кажется ужасно подробным и подверженным ошибкам. Есть ли лучший способ или простой способ автоматизировать определение operator< для struct или class?

Я знаю, что некоторым людям нравится просто использовать что-то вроде memcmp(this, &rhs, sizeof(MyStruct)) < 0, но это может работать некорректно, если между членами есть пробельные байты или существуют массивы строк char, которые могут содержать мусор после нулевых терминаторов.

4b9b3361

ОТВЕТЫ

Ответ 1

Это довольно старый вопрос, и, как следствие, все ответы здесь устарели. С++ 11 позволяет более элегантное и эффективное решение:

bool operator <(const MyStruct& x, const MyStruct& y) {
    return std::tie(x.a, x.b, x.c) < std::tie(y.a, y.b, y.c);
}

Почему это лучше, чем использование boost::make_tuple? Поскольку make_tuple создаст копии всех членов данных, что может быть дорогостоящим. std::tie, напротив, просто создаст тонкую оболочку ссылок (что компилятор, вероятно, полностью оптимизирует).

Фактически, приведенный выше код теперь должен рассматриваться как идиоматическое решение для реализации лексикографического сравнения для структур с несколькими членами данных.

Ответ 2

Другие упомянули boost::tuple, что дает вам лексикографическое сравнение. Если вы хотите сохранить его как структуру с именованными элементами, вы можете создать временные кортежи для сравнения:

bool operator<(const MyStruct& x, const MyStruct& y)
{
    return boost::make_tuple(x.a,x.b,x.c) < boost::make_tuple(y.a,y.b,y.c);
}

В С++ 0x это становится std::make_tuple().

UPDATE: И теперь С++ 11 здесь, он становится std::tie(), чтобы сделать кортеж ссылок без копирования объектов. См. Новый ответ Конрада Рудольфа.

Ответ 3

Я бы сделал это:

#define COMPARE(x) if((x) < (rhs.x)) return true; \
                   if((x) > (rhs.x)) return false;
COMPARE(a)
COMPARE(b)
COMPARE(c)
return false;
#undef COMPARE

Ответ 4

В этом случае вы можете использовать boost::tuple<int, int, int> - оператор < работает так, как вы хотите.

Ответ 5

Лучший способ, которым я знаю, - использовать boost tuple. Он предлагает, среди прочего, встроенное сравнение и конструкторы.

#include <boost/tuple/tuple.hpp>
#include <boost/tuple/tuple_comparison.hpp>

typedef boost::tuple<int,int,int> MyStruct;

MyStruct x0(1,2,3), x1(1,2,2);
if( x0 < x1 )
   ...

Мне также нравится предложение Майка Сейморса использовать временные кортежи через boost make_tuple

Ответ 6

Я думаю, что самый простой способ - придерживаться < оператора для всех сравнений и не использовать > или ==. Ниже приведен образец, за которым следую, и вы можете следить за всеми своими структурами.

typedef struct X
{
    int a;
    std::string b;
    int c;
    std::string d;

    bool operator <( const X& rhs ) const
    {
        if (a < rhs.a) { return true; }
        else if ( rhs.a < a ) { return false; }

        // if neither of the above were true then 
        // we are consdidered equal using strict weak ordering
        // so we move on to compare the next item in the struct

        if (b < rhs.b) { return true; }
        if ( rhs.b < b ) { return false; }

        if (c < rhs.c) { return true; }
        if ( rhs.c < c ) { return false; }

        if (d < rhs.d) { return true; }
        if ( rhs.d < d ) { return false; }

        // if both are completely equal (based on strict weak ordering)
        // then just return false since equality doesn't yield less than
        return false;
    }
};

Ответ 7

Обычно я использую лексикографическое упорядочение следующим образом:

bool operator < (const MyObject& obj)
{
    if( first != obj.first ){
        return first < obj.first;
    }
    if( second != obj.second ){
        return second < obj.second;
    }
    if( third != obj.third ){
        return third < obj.third
    }
    ...
}

Имейте в виду, что вам нужно дополнительное внимание к значениям с плавающей запятой (предупреждения g++), для тех, что это было бы лучше:

bool operator < (const MyObject& obj)
{
    if( first < obj.first ){
        return true;
    }
    if( first > obj.first ){
        return false;
    }
    if( second < obj.second ){
        return true;
    }
    if( second > obj.second ){
        return false;
    }
    ...
}

Ответ 8

#include <iostream>

#include <boost/fusion/include/adapt_struct.hpp>
#include <boost/fusion/include/less.hpp>

struct MyStruct {
   int a, b, c;
};

BOOST_FUSION_ADAPT_STRUCT( MyStruct,
                           ( int, a )
                           ( int, b )
                           ( int, c )
                          )

bool operator<( const MyStruct &s1, const MyStruct &s2 )
{
   return boost::fusion::less( s1, s2 );
}

int main()
{
   MyStruct s1 = { 0, 4, 8 }, s2 = { 0, 4, 9 };
   std::cout << ( s1 < s2 ? "is less" : "is not less" ) << std::endl;
}

Ответ 9

Если вы не можете использовать boost, вы можете попробовать что-то вроде:

#include <iostream>

using namespace std;

template <typename T>
struct is_gt
{
  is_gt(const T& l, const T&r) : _s(l > r) {}

  template <typename T2>
  inline is_gt<T>& operator()(const T2& l, const T2& r)
  {
    if (!_s)
    {
      _s = l > r;
    }
    return *this;
  }

  inline bool operator!() const { return !_s; }

  bool _s;
};

struct foo
{
  int a;
  int b;
  int c;

  friend bool operator<(const foo& l, const foo& r);
};

bool operator<(const foo& l, const foo& r)
{
  return !is_gt<int>(l.a, r.a)(l.b, r.b)(l.c, r.c);
}

int main(void)
{
  foo s1 = { 1, 4, 8 }, s2 = { 2, 4, 9 };
  cout << "s1 < s2: " << (s1 < s2) << endl;
  return 0;
}

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

Edit:

Модифицированный на основе комментариев, эта версия также должна быть короткозамкнута, теперь использует два элемента управления bools для сохранения состояния (не уверен, что есть способ сделать это с помощью одного bool).

template <typename T>
struct is_lt
{
  is_lt(const T& l, const T&r) : _s(l < r), _e(l == r) {}

  template <typename T2>
  inline bool operator()(const T2& l, const T2& r)
  {
    if (!_s && _e)
    {
      _s = l < r;
      _e = l == r;
    }
    return _s;
  }

  inline operator bool() const { return _s; }

  bool _s;
  bool _e;
};

и

bool operator<(const foo& l, const foo& r)
{
  is_lt<int> test(l.a, r.a);
  return test || test(l.b, r.b) || test(l.c, r.c);
}

просто создайте коллекцию таких функторов для различных сравнений.

Ответ 10

Я только что узнал трюк boost::tuple, спасибо, @Mike Seymour!

Если вы не можете позволить себе Boost, моя любимая идиома:

bool operator<(const MyStruct& rhs) const
{
    if (a < rhs.a)  return true;
    if (a > rhs.a)  return false;

    if (b < rhs.b)  return true;
    if (b > rhs.b)  return false;

    return (c < rhs.c);
}

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

Но, конечно же, вы все равно тестируете устройство, верно?

Ответ 11

Я написал perl script, чтобы помочь мне. Например:

class A
{
int a;
int b;
int c;

Он испустит:

bool operator<(const A& left, const A& right)
{
    bool result(false);

    if(left.a != right.a)
    {
        result = left.a < right.a;
    }
    else if(left.b != right.b)
    {
        result = left.b < right.b;
    }
    else
    {
        result = left.c < right.c;
    }

    return result;
}

Код (он немного длинный):

#!/usr/bin/perl

use strict;

main:

my $line = <>;
chomp $line;
$line =~ s/^ *//;

my ($temp, $line, $temp) = split / /, $line;

print "bool operator<(const $line& left, const $line& right)\n{\n";
print "    bool result(false);\n\n";

my $ifText = "if";

$line = <>;

while($line)
{
    if($line =~ /{/)
    {
        $line = <>;
        next;
    }
    if($line =~ /}/)
    {
        last;
    }

    chomp $line;
    $line =~ s/^ *//;

    my ($type, $name) = split / /, $line;
    $name =~ s/; *$//;

    $line = <>;
    if($line && !($line =~ /}/))
    {
        print "    $ifText(left.$name != right.$name)\n";
        print "    {\n";
        print "        result = left.$name < right.$name;\n";
        print "    }\n";

        $ifText = "else if";
    }
    else
    {
        print "    else\n";
        print "    {\n";
        print "        result = left.$name < right.$name;\n";
        print "    }\n";

        last;
    }
}

print "\n    return result;\n}\n";

Ответ 12

bool operator <(const A& l, const A& r)
{

    int[] offsets = { offsetof(A, a), offsetof(A, b), offsetof(A, c) };
    for(int i = 0; i < sizeof(offsets)/sizeof(int); i++)
    {
        int ta = *(int*)(((const char*)&l)+offsets[i]);
        int tb = *(int*)(((const char*)&r)+offsets[i]);

        if (ta < tb)
             return true;
        else if (ta > tb)
             break;

    }
    return false;
}

Ответ 13

Когда вы можете создавать итераторы над элементами, определяющими лексикографический порядок, вы можете использовать std::lexicographic_compare, от <algorithm>.

В противном случае я предлагаю использовать сравнения для старых трехзначных функций сравнения, например. следующим образом:

#include <iostream>

int compared( int a, int b )
{
    return (a < b? -1 : a == b? 0 : +1);
}

struct MyStruct
{
    friend int compared( MyStruct const&, MyStruct const& );
    int a;
    int b;
    int c;

    bool operator<( MyStruct const& rhs ) const
    {
        return (compared( *this, rhs ) < 0);
    }
};

int compared( MyStruct const& lhs, MyStruct const& rhs )
{
    if( int x = compared( lhs.a, rhs.a ) ) { return x; }
    if( int x = compared( lhs.b, rhs.b ) ) { return x; }
    if( int x = compared( lhs.c, rhs.c ) ) { return x; }
    return 0;
}

int main()
{
    MyStruct const  s1 = { 0, 4, 8 };
    MyStruct const  s2 = { 0, 4, 9 };
    std::cout << ( s1 < s2 ? "is less" : "is not less" ) << std::endl;
}

Я включил последние if и return в функцию compare только для общности. Я предполагаю, что это может помочь поддерживать очень жестко придерживаться единой системы. В противном случае вы можете просто сделать return compared( lhs.c, rhs.c ) там (и, возможно, вам это нравится).

Приветствия и hth.,

- Alf

Ответ 14

Если трехстороннее сравнение более дорогостоящее, чем двухстороннее, и если более значимые части структур будут часто равными, может оказаться полезным определить функции сравнения поля с параметром "смещения", так что если "смещение" ложно, они вернут true, когда a > b, и когда смещение истинно, они вернут true, если a >= b. Затем можно узнать, если a > b, выполнив что-то вроде:

  return compare1(a.f1,b.f1, compare2(a.f2,b.f2, compare3(a.f3,b.f3,false)));

Обратите внимание, что все сравнения будут выполнены, даже если a.f1 < > b.f1, но сравнения будут двухсторонними, а не трехсторонними.