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

Я иногда использую маленький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 строковые массивы, которые могут содержать мусор после нулевых терминаторов.

 Jon Purdy07 окт. 2010 г., 16:23
Вы можете иметь краткость, которая значительно не подвержена ошибкам:return (a < rhs.a || (a == rhs.a && (b < rhs.b || (b == rhs.b && c < rhs.c))));

Ответы на вопрос(14)

Решение Вопроса

и поэтому все ответы здесь устарели. C ++ 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напротив, просто создаст тонкую оболочку ссылок (которую компилятор, вероятно, полностью оптимизирует).

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

 Riot02 февр. 2014 г., 02:25
Достаточно справедливо - я просто использовал код в оригинальном вопросе.
 Renaud24 июн. 2015 г., 14:32
С большой структурой и c ++ 1y, вы можете добавить функциюauto AsTuple(const MyStruct & s) { return std::tie(s.x, s.y); }, Это позволит избежать повторения полей структуры вoperator<.... к сожалению, я не видел в любом случае, чтобы сделать это в C ++ 11.
 Riot01 февр. 2014 г., 03:35
Стоит отметить, что приведенный выше код не будет работать - оператор <принимает только один аргумент.operator<(const MyStruct& rhs)
 Konrad Rudolph01 февр. 2014 г., 13:11
@Riot Нет, код работает просто отлично. Это, однако, должно быть определено за пределамиMyStruct - в любом случае это лучшая практика.
 Konrad Rudolph24 июн. 2015 г., 17:16
@Renaud В C ++ 11 вы можете использовать лямбду (auto as_tuple = [](MyStruct const& s) {return std::tie(s.x, s.y);};), потому что это может вывести тип возвращаемого значения.

Другие упоминали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);
}

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

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

 Timo07 окт. 2010 г., 16:30
Мне интересно, насколько создание этих объектов кортежа влияет на производительность.
 Mike Seymour07 окт. 2010 г., 16:38
@ Тимо: строительство и сравнениедолжен быть встроенным, так что я бы удивился, если бы это было медленнее, чем прямое сравнение значений. Но единственный способ убедиться в этом - это измерить.

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

#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 )
   ...

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

 Peter G.07 окт. 2010 г., 16:18
Почему это не должно быть хорошо? Работа происходит во время компиляции.
 Benoit07 окт. 2010 г., 16:14
Да ... но хорошо ли это тогда, когда речь идет о сложных структурах?

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

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

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

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

 Kristopher Johnson07 окт. 2010 г., 19:11
Обратите внимание, что это по сути то же самое, что и ответ @ Benoit, без макросов, поэтому комментарии к этому ответу также применимы и здесь.
 mskfisher12 окт. 2010 г., 16:15
Благодарю. @ Марк Рэнсом о единственном использовании< должным образом отмечено.

чем двухсторонние, и если более значимые части структур часто будут равны, может быть полезно определить функции сравнения полей с параметром 'смещения', например, если 'смещение' ложь, они вернут истину, когда a> b, а когда смещение истинно, они вернут истину, если 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, но сравнения будут двухсторонними, а не трехсторонними.

boost::tuple<int, int, int> - егооператор < работает так, как вы хотите.

Я написал Perl-скрипт, чтобы помочь мне. Например, учитывая:

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";
 Roger Pate08 окт. 2010 г., 22:28
if (left.a != left.b) { return left.a < left.b; } становитсяif (left.a < left.b) return true; else if (left.a != left.b) return false; (или вы можете использовать переменную результата, тоже самое)
 Roger Pate08 окт. 2010 г., 20:22
Обычно объекты чаще бывают неодинаковыми, поэтому я бы изменил ваши сравнения для проверки с использованием op <first.
 Mark B08 окт. 2010 г., 20:55
@ Роджер Пейт согласился, но я не могу представить, как будет выглядеть код, не могли бы вы вкратце рассказать?
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;
}
 Roger Pate08 окт. 2010 г., 20:29
Если вы собираетесь использовать это для реализации op <, вы могли бы также превратить элементы в массив в первую очередь, тогда сравнение будет прямым (просто используйте std :: lexicographic_compare для обоих массивов). Это плохое решение.
 nothrow07 окт. 2010 г., 17:31
просто -> просто добавьте их смещения кoffsets массив
 Yogesh Arora07 окт. 2010 г., 16:36
Что делать, если более 3 членов

определяющих лексикографический порядок, вы можете использовать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.,

Альф

 Cheers and hth. - Alf24 авг. 2012 г., 14:09
@ downvoter: пожалуйста, объясните причину вашего отрицательного голоса, чтобы другие могли извлечь выгоду из вашего понимания или увидеть, что они могут игнорировать понижающее голосование

вы можете попробовать что-то вроде:

#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, а затем избыточных ветвей для каждого параметра, если одно из значений больше ...

Редактировать:

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

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

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

 mskfisher07 окт. 2010 г., 18:18
Этот подход не учитывает оценку короткого замыкания - есть ли способ работать с этим?
 Kristopher Johnson07 окт. 2010 г., 17:26
Будет ли это работать правильно, если две структуры равны? Оператор <() должен вернуть false в этом случае, но мне кажется, что вы проверяете только не более чем.
 Nim08 окт. 2010 г., 10:03
@mskfisher, упс, вы правы - долгий день ... окончательное редактирование должно иметь закороченную версию, теперь оператор не является одним вкладышем ...
 mskfisher07 окт. 2010 г., 22:16
Что новый|| метод не работает для случая, когдаl.a > r.a а такжеl.b < r.b - должно вернутьсяfalse, но он вернетсяtrue.
 Nim07 окт. 2010 г., 17:47
хорошо ... :) это довольно тривиально, чтобы изменить это! :) отредактировано ...
 Nim07 окт. 2010 г., 21:12
@mskfisher - могу ли я догадаться, но, подумав об этом еще немного ... все эти действительно сложные методы бессмысленны, вам нужна || оператор! то есть вернуть l.a <r.a || l.b <r.b || l.c <r.c; см. правку выше ...

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

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;
    }
};
 ackb05 мая 2011 г., 10:26
Для чего вам нужны остальные?
 ceorron11 авг. 2016 г., 19:29
Очень нравится идея, что <оператор должен быть определен в терминах самого себя.
#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;
}

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

#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
 Benoit07 окт. 2010 г., 20:30
Ты прав. Это вопрос компромисса между легкостью чтения и эффективностью.
 Rune FS08 окт. 2010 г., 10:27
если вы не заботитесь о читабельности, почему, если? СРАВНИТЬ (X, def) (! (Rhs.x <x) && (x <rhs.x)) && def; вернуть СРАВНИТЬ (a, СРАВНИТЬ (b, СРАВНИТЬ (c, true))); Но опять же зачем пытаться угадать, что быстрее. код, компилировать, время и затемпотенциально оптимизировать и читаемый код гораздо проще оптимизировать
 Mark Ransom07 окт. 2010 г., 17:41
Просто такие вещи, которые не могут быть заменены шаблонами, потому что вам нужно вернуться из включающей функции. Одно предложение: заменить(x) > (rhs.x) с(rhs.x) < (x) полагаться только наoperator< на членов. Кроме того, я думаю, что круглые скобки являются избыточными, я не вижу, как этот макрос будет работать должным образом с вводом, который требовал их.
 Kristopher Johnson07 окт. 2010 г., 19:13
Я бы заменил финалCOMPARE(c); return false; сreturn c < rhs.c, чтобы избежать постороннего> сравнения.

Ваш ответ на вопрос