표준::정렬()이 범위를 벗어난 주소에 액세스하는 원인

Question

나는 표준::정렬()을 사용하려면 비교 기능이 엄격한 약한 순서 여야한다는 것을 이해합니다.(https://gcc.gnu.org/ml/gcc-bugs/2013-12/msg00333.html)

그러나 비교 함수가 엄격한 약한 순서가 아닌 경우 표준::정렬()이 바인딩되지 않은 주소에 액세스하는 이유는 무엇입니까?그것은 무엇을 비교하려고 하는가?

또한 내가 알아야 할 다른 함정이 있는지 궁금합니다.

Answer 1

첫 번째 것은 요구 사항을 준수하지 않는 비교기로 알고리즘을 호출하는 것은 정의되지 않은 행동이며 아무 것도 진행되지 않는다는 것입니다...

그러나 그 외에는 비교기가 나쁜 경우 어떤 유형의 구현이 범위를 벗어나 액세스 할 수 있는지 아는 데 관심이 있다고 가정합니다. 구현은 먼저 요소에 액세스하기 전에 경계를 확인해야합니까?즉비교기를 호출하기 전에

대답은 성능이며,이것은 이러한 유형의 문제로 이어질 수있는 가능한 것 중 하나 일뿐입니다.정렬 알고리즘의 구현은 다양하지만,그보다 더 자주, std::sort 퀴크소트의 변종 위에 구축되어 있으며,이는 퀴크소트의 최악의 경우 성능을 피하기 위해 병합소트와 같은 다른 정렬 알고리즘에서 퇴화됩니다.

퀴크소트의 구현은 피벗을 선택하고 피벗을 중심으로 입력을 분할한 다음 양쪽을 독립적으로 정렬합니다.피벗을 선택하는 데는 다른 전략이 있지만 일반적인 전략은 3 의 중간값입니다.:알고리즘은 첫 번째,마지막 및 중간 요소의 값을 가져오고 세 요소의 중앙값을 선택하고 피벗 값으로 사용합니다.

개념적으로 분할은 피보트보다 작지 않은 요소를 찾을 때까지 왼쪽에서 걷고,피보트보다 작은 요소를 찾으려고 오른쪽에서 걷습니다.두 커서가 만나는 경우 파티션이 완료되었습니다.잘못된 요소가 발견되면 값이 교환되고 프로세스가 두 커서에 의해 결정된 범위에서 계속됩니다.교환할 요소를 찾기 위해 왼쪽에서 걷는 루프는 다음과 같습니다.:

while (pos < end && value(pos) < pivot) { ++pos; }

일반적으로 파티션에서는 피벗 값이 범위에 있다고 가정할 수 없지만,빠른 정렬은 알고 즉,결국 이 범위의 요소 중 피벗을 선택했습니다.이 경우 일반적인 최적화는 루프의 마지막 요소에 있는 중간값의 값을 교환하는 것입니다.이것은 value(pos) < pivot 사실이 될 것입니다 이전 pos == end (최악의 경우: pos == end - 1).여기서 암시하는 것은 우리가 범위의 끝을 위한 검사를 떨어뜨릴 수 있다는 것입니다.그리고 우리는 unchecked_partition 간단한 빠른 조건(이름의 선택을 선택):

while (/*pos < end &&*/ value(pos) < pivot) ++pos;

모든 것을 제외하고 완벽하게 좋은 < 표기법 comparator(value(pos), pivot).이제 만약 comparator 잘못 구현되어 결국 comparator(pivot,pivot) == true 그리고 커서가 범위를 벗어날 것입니다.

이것은 성능에 대한 경계 검사를 제거 할 수있는 알고리즘의 최적화의 한 예일뿐입니다:유효한 순서를 가정하면, 불가능 빠른 정렬이 피벗을 마지막 요소로 설정하면 위의 루프에서 배열을 벗어나려면 이전 이 수정 된 파티션을 호출합니다.

질문으로 돌아 가기:

구현은 먼저 요소에 액세스하기 전에 경계를 확인해야합니까?즉비교기를 호출하기 전에

아니,그것이 배열 밖으로 나가지 않을 것이라는 것을 증명함으로써 경계 검사를 제거 한 것이 아니라,그 증명은 비교기가 유효하다는 전제에 기반을두고 있습니다.

Answer 2

std::sort는 실제로 주어진 비교기가 엄격한 약한 주문을 설정하도록 요구합니다. 그렇지 않으면 정렬은 실제로 많은 의미가 없습니다.

범위를 벗어나면 게시 된 링크는 버그 보고서에 대한 것입니다. 즉, 실제로이 작업을 수행하지 않아도됩니다. 다른 소프트웨어와 마찬가지로 컴파일러는 버그가있을 수 있습니다. 아담에 의해 언급 했듯이이 특별한 버그 보고서는 실제로 버그가 아니기 때문에 거부되었습니다.

엄격한 약한 주문이없는 경우 정확히 일어나는 일은 표준에 의해 정의되지 않으면 그 일을하는 것이 좋지 않으며 따라서 표준에 의해 제외됩니다. 그러므로 누락에 의해 정의되지 않은 입니다. undefined 은 범위를 벗어나면서도 아무 것도 액세스 할 수 있음을 의미합니다.

"함정"을 피하는 것은 당신이 사용하는 알고리즘과 기능의 요구 사항을 알고 있어야합니다. C ++의 경우 일반적으로 사용하는 좋은 참조 사이트가 있습니다 : cppreference

std::sort 페이지가 말합니다 :

comp - 비교 함수 객체 (즉, 첫 번째 인수가 초) 미만인 경우 true를 반환하는 비교 함수 (즉, I.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.)

비교