연산자 <및 엄격한 약한 주문

StackOverflow https://stackoverflow.com/questions/979759

  •  13-09-2019
  •  | 
  •  

문제

정의하는 방법 operator< n- 튜플 (예 : 3- 튜플)에서 만족하도록 엄격한 약한 주문 개념 ? 부스트 라이브러리에 올바르게 정의 된 튜플 클래스가 있다는 것을 알고 있습니다. operator< 그러나 어떤 이유로 나는 그것을 사용할 수 없습니다.

도움이 되었습니까?

해결책 

if (a1 < b1)
  return true;
if (b1 < a1)
  return false;

// a1==b1: continue with element 2
if (a2 < b2)
  return true;
if (b2 < a2)
  return false;

// a2 == b2: continue with element 3
if (a3 < b3)
  return true;
return false; // early out

이것은 A1의 요소를 가장시기 적이며 A3의 가장 중요하다는 것을 명령합니다.

이것은 계속해서 ad infinitum 일 수 있으며, 예를 들어, t의 벡터에 적용 할 수도 있습니다. 알고리즘의 대체 표현은 "동일하게 건너 뛰고 비교"입니다.

while (i<count-1 && !(a[i] < a[i+1]) && !(a[i+1] < a[i])
  ++i;
return i < count-1 && a[i] < a[i+1];

물론 비교가 비싸면 비교 결과를 캐시 할 수 있습니다.

편집] 잘못된 코드를 제거했습니다

편집] 단지 이상의 경우 operator< 사용할 수 있습니다. 패턴을 사용하는 경향이 있습니다

if (a1 != b1)
  return a1 < b1;

if (a2 != b2)
  return a2 < b2;

...

다른 팁

엄격한 약한 주문

이것은 두 객체 사이의 관계를 정의하는 수학적 용어입니다.
그것의 정의는 다음과 같습니다.

f (x, y)와 f (y, x)가 모두 false 인 경우 두 개의 객체 x와 y가 동일합니다. 객체는 항상 (비정형 적 불변으로) 그 자체와 동등합니다.

C ++의 관점에서 이것은 주어진 유형의 두 객체가있는 경우 연산자 <와 비교할 때 다음 값을 반환해야합니다.

X    a;
X    b;

Condition:                  Test:     Result
a is equivalent to b:       a < b     false
a is equivalent to b        b < a     false

a is less than b            a < b     true
a is less than b            b < a     false

b is less than a            a < b     false
b is less than a            b < a     true

동등한/덜 정의하는 방법은 객체의 유형에 전적으로 의존합니다.

공식 정의 :
엄격한 약한 주문

컴퓨터 과학 :
엄격한 약한 주문

운영자와 관련된 방법 :
비교기

... 아주 오래된 질문에 대한 새로운 답변이지만 기존 답변은 C ++ 11의 쉬운 솔루션을 놓치고 있습니다.

C ++ 11 솔루션

C ++ 11 이후에 제공됩니다 std::tuple<T...>, 데이터를 저장하는 데 사용할 수 있습니다. tuples는 일치합니다 operator< 처음에는 왼쪽 요소를 비교 한 다음 결과가 명확해질 때까지 튜플을 따라 작동합니다. 그것은 그것을 제공하기에 적합합니다 엄격한 약한 주문 예를 들어 예상 std::set 그리고 std::map.

다른 변수에 데이터가있는 경우 (예 : 필드 struct), 당신은 심지어 사용할 수 있습니다 std::tie() 튜플을 만듭니다 참고 문헌, 그런 다음 다른 튜플과 비교할 수 있습니다. 그것은 글을 쉽게 작성할 수있게합니다 operator< 사용자 정의의 특정 멤버 데이터 필드 용 class/struct 유형:

struct My_Struct
{
    int a_;
    double b_;
    std::string c_;
};

bool operator<(const My_Struct& lhs, const My_Struct& rhs)
{
    return std::tie(lhs.a_, lhs.b_, lhs.c_) < std::tie(rhs.a_, rhs.b_, rhs.c_);
}

당신은 단순히 3 가지 요소 벡터를 사용할 수 있으며, 이는 이미 연산자 <()에 적절하게 정의되어 있습니다. 이것은 당신이 아무것도 할 필요없이 n- 요소로 확장된다는 이점이 있습니다.

기본 흐름은 다음의 선을 따라야합니다. Kth 요소가 다르면 더 작은 리턴은 다음 요소로 이동합니다.. 다음 코드가 귀하를 가정합니다 ~하지 않다 그렇지 않으면 튜플을 부스트하십시오 get<N>(tuple) 시작할 문제가 없습니다.

if (lhs.first != rhs.first)
    return lhs.first < rhs.first;                
if (lhs.second != rhs.second)
    return lhs.second< rhs.second;
return lhs.third < rhs.third;

부스트 버전을 사용할 수 없더라도 코드를 닉 할 수 있어야합니다. 나는 이것을 std :: 쌍에서 닉했다 - 3 튜플은 내가 생각한다.

return (_Left.first < _Right.first ||
        !(_Right.first < _Left.first) && _Left.second < _Right.second);

편집 : 두 사람이 지적했듯이, 코드에서 사용하기 위해 표준 라이브러리에서 코드를 훔치면이 이름이 예약되어 있으므로 앞면에 밑줄이있는 것을 바꿔야합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top