구조체에 대한 operator <정의

구조체에 대한 operator <정의

---

가끔 structs맵에서 키로 small 을 사용하기 때문에를 정의 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<A에 대한 struct또는 class?

나는 어떤 사람들이 그냥를 사용하는 것을 좋아한다는 것을 알고 memcmp(this, &rhs, sizeof(MyStruct)) < 0있지만 멤버 사이에 패딩 바이트가 있거나 charnull 종결 자 뒤에 가비지를 포함 할 수있는 문자열 배열 이있는 경우 올바르게 작동하지 않을 수 있습니다.

---

이것은 꽤 오래된 질문이며 결과적으로 여기에있는 모든 답변은 쓸모가 없습니다. 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반대로는 참조의 얇은 래퍼를 만듭니다 (컴파일러가 완전히 최적화 할 것임).

사실, 위 코드는 이제 여러 데이터 멤버가있는 구조에 대한 사전 비교를 구현하는 관용적 솔루션으로 간주되어야합니다.

---

다른 사람들은 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()에 있습니다. 객체를 복사하지 않고 참조의 튜플을 만들 수 있습니다. 자세한 내용은 Konrad Rudolph의 새로운 답변을 참조하십시오.

---

나는 이것을 할 것이다 :

#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

---

이 경우 사용할 수 있습니다 boost::tuple<int, int, int>-의 연산자는 < 당신이 원하는 방식으로 작동합니다.

---

가장 쉬운 방법은 모든 비교에 <연산자를 사용하고> 또는 ==를 사용하지 않는 것입니다. 아래는 내가 따르는 패턴이며 모든 구조체에 대해 따를 수 있습니다.

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

---

내가 아는 가장 좋은 방법은 부스트 튜플 을 사용하는 것 입니다. 내장 된 비교 및 ​​생성자를 제공합니다.

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

나는 또한 Mike Seymors가 boost의 make_tuple을 통해 임시 튜플을 사용하도록 제안하는 것을 좋아합니다.

---

나는 일반적으로 다음과 같은 방식으로 사전 순서를 구현합니다.

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

---

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

---

부스트를 사용할 수없는 경우 다음과 같이 시도해 볼 수 있습니다.

#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를 생성 한 다음 값 중 하나가 더 큰 경우 각 매개 변수에 대해 superflous 분기를 생성합니다.

편집하다:

주석에 따라 수정 된이 버전은 이제 단락되어야합니다. 이제 상태를 유지하기 위해 두 개의 bool을 사용합니다 (단일 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);
}

다양한 비교를 위해 이러한 펑터 모음을 구축하십시오.

---

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

모든 것을 병렬 구조로 설정하여 오류와 누락을 쉽게 발견 할 수 있기 때문에 좋아합니다.

하지만 물론, 당신은 어쨌든 이것을 단위 테스트하고 있습니까?

---

나를 돕기 위해 펄 스크립트를 작성했습니다. 예를 들면 다음과 같습니다.

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

---

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

---

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

---

If three-way comparisons are more expensive than two-way, and if the more-significant portions of the structures will often be equal, it may be helpful to define field comparison functions with a 'bias' parameter, such that if 'bias' is false, they will return true when a>b, and when bias is true, they will return true if a>=b. Then one can find out if a>b by doing something like:

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

Note that all comparisons will be performed, even if a.f1<>b.f1, but comparisons will be two-way instead of three-way.

ReferenceURL : https://stackoverflow.com/questions/3882467/defining-operator-for-a-struct