stl 순서 - 엄격한 약한 순서

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

문제

STL이 비교 기능과 함께 작동하는 이유는 무엇입니까? 엄격한 약한 순서?왜 부분주문이 안되나요?

도움이 되었습니까?

해결책

ㅏ 부분 순서 정렬 알고리즘과 같은 일부 알고리즘을 구현하기에는 충분하지 않습니다. 부분적으로 주문한 세트가 반드시 세트의 모든 요소 간의 관계를 정의 할 필요는 없으므로 부분 순서 내에서 주문 관계가없는 두 항목 목록을 어떻게 정렬합니까?

다른 팁

간단히 말해서 엄격한 약한 순서는 다음과 같은 순서로 정의됩니다. (계산 가능한) 동치 관계를 정의합니다..동등 클래스는 엄격한 약한 순서로 정렬됩니다. 엄격한 약한 순서는 동등 클래스에 대한 엄격한 순서입니다..

부분 순서(즉, 엄격한 약한 순서가 아님)는 동등 관계를 정의하지 않으므로 "동등한 요소" 개념을 사용하는 모든 사양은 엄격한 약한 정렬이 아닌 부분 정렬에서는 의미가 없습니다. 모든 STL 연관 컨테이너는 어느 시점에서 이 개념을 사용하므로 엄격한 약한 정렬이 아닌 부분 정렬에서는 이러한 모든 사양이 의미가 없습니다.

부분 순서(엄격한 약한 순서가 아님)가 반드시 엄격한 순서를 정의하는 것은 아니기 때문에 부분 순서에 따라 상식적으로 "요소를 정렬"할 수 없습니다. 할 수 있는 일은 더 약한 속성을 갖는 "위상 정렬"뿐입니다. ).

주어진

  • 수학적 집합 S
  • 부분 주문 < ~ 위에 S
  • 가치 x ~에 S

파티션을 정의할 수 있습니다. S (모든 요소 S 다음 중 하나에 있습니다. L(x), I(x) 또는 G(x)):

L(x) = { y in S | y<x }
I(x) = { y in S | not(y<x) and not(x<y) }
G(x) = { y in S | x<y }

 L(x) : set of elements less than x
 I(x) : set of elements incomparable with x
 G(x) : set of elements greater than x

순서는 다음과 같이 정렬됩니다. < iff 모든 x 순서대로, 요소 L(x) 시퀀스에서 처음으로 나타나고 그 뒤에 다음의 요소가 나타납니다. I(x), 그 뒤에 다음의 요소가 옵니다. G(x).

시퀀스는 위상적으로 정렬됩니다. iff 모든 요소에 대해 y 다른 요소 뒤에 나타나는 x 순서대로, y 보다 작지 않습니다 x.정렬되는 것보다 약한 제약 조건입니다.

모든 요소가 다음과 같다는 것을 증명하는 것은 쉽지 않습니다. L(x) 의 어떤 요소보다 작습니다. G(x).요소들 사이에는 일반적인 관계가 없습니다. L(x) 및 요소 I(x), 또는 요소 사이 I(x) 및 요소 G(x).그러나 만일 < 의 모든 요소보다 엄격한 약한 순서입니다. L(x) 의 어떤 요소보다 작습니다. I(x), 그리고 의 어떤 요소보다 I(x) 의 어떤 요소보다 작습니다. G(x).

만약에 < 엄격한 약한 순서이며, x<y 그런 다음 L(x) U I(x) 어떤 요소보다 작습니다. I(y) U G(y):다음보다 크지 않은 모든 요소 x 그 이하도 아닌 어떤 요소보다 작습니다. y. 이는 부분 주문의 경우 반드시 적용되는 것은 아닙니다.

주어진 답변을 인용합니다 여기:

내부적으로 이러한 알고리즘 구현 "은" !(a < b) && !(b < a).

사용한 경우 <= 연산자보다 적은 운영자를 구현하려면 위의 내용은 a == b. 평등이 깨진 점검은 거의 모든 알고리즘을 망칠 것입니다.

마찬가지로, 그들은 구현 "과 동일하지 않습니다. (a < b) || (b < a), 그리고 다시 한 번, 당신이 구현했다면 < 운영자 사용 <=, 그러면 실제로 동등하지 않을 때 서로 동등 할 때 사실이 반환됩니다. 따라서 평등 점검은 양방향으로 끊어집니다.

라이브러리를 덜 운영자로 제한하는 요점은 모든 논리 연산자가 IT 측면에서 구현 될 수 있다는 것입니다.

  • <(a, b): (a < b)
  • <=(a, b): !(b < a)
  • ==(a, b): !(a < b) && !(b < a)
  • !=(a, b): (a < b) || (b < a)
  • >(a, b): (b < a)
  • >=(a, b): !(a < b)

제공된 운영자가 엄격한 약한 주문의 조건을 충족하는 한 작동합니다. 표준 <= 그리고 >= 운영자는 그렇지 않습니다.

부분 순서로 바이너리 검색을 수행 할 수 없습니다. 부분 순서로 이진 검색 트리를 만들 수 없습니다. 기능/데이터 유형 연산 주문이 필요하고 부분 주문과 함께 작동 할 수 있습니까?

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