std::list::sort(): 왜 하향식 병합 정렬로 전환합니까?

std::list<>::sort(): 갑자기 하향식 전략으로 전환한 이유는 무엇입니까?

보다 강력하고 예외로부터 안전한 정렬에 대한 요구를 해결하기 위해 std::list<>::sort()에서 상향식에서 하향식 병합 정렬로의 병합 정렬이 등장했습니다. 이전 구현에서는 내부 목록 배열을 사용했지만 VS2015에서 기본이 아닌 생성 가능 및 상태 저장 할당자의 도입으로 인해 문제가 발생할 수 있습니다.

이를 우회하기 위해 Microsoft의 Stephan T. Lavavej는 반복자를 사용하여 다음을 수행할 것을 제안했습니다. 원래 연결 목록 내에서 실행 경계를 추적합니다. 이를 통해 병합 작업 중에 목록 내에서 노드를 이동하기 위해 std::list::splice를 사용할 수 있어 예외 안전성이 보장됩니다. 이러한 변경으로 견고성은 향상되지만 연결 목록을 통해 중간점을 찾는 것이 비효율적일 수 있으므로 성능 비용이 발생합니다.

그러나 Visual Studio 2022 업데이트에서 Microsoft는 다음을 통해 하향식 구현을 향상했습니다. 목록을 반복하는 대신 정수 크기를 단순히 절반으로 줄이는 보다 효율적인 재귀 전략으로 전환합니다. 이 수정은 예외 안전성의 이점을 유지하고 std::next에 대한 반복 호출로 인한 성능 저하를 방지합니다.

하향식 접근 방식의 대안으로 일부 개발자는 다음과 같은 상향식 병합 정렬 사용을 제안했습니다. 이 문서의 앞부분에서 소개한 반복자입니다. 이 접근 방식도 반복자를 사용하지만 상향식 방식으로 작동하므로 중간점을 찾기 위해 목록을 스캔할 필요가 없습니다. 구체적인 구현은 목록의 크기와 노드의 분포에 따라 달라지며 시간과 공간의 복잡성 사이의 균형을 유지합니다.

하향식 병합 정렬은 std::list<>의 기본값으로 유지됩니다. ::sort(), VS2022의 수정된 구현은 효율성과 예외 안전성의 균형을 제공하는 것을 목표로 합니다. 개발자는 애플리케이션의 특정 요구 사항에 따라 반복자를 사용한 상향식 병합 정렬과 같은 대체 구현을 모색할 수 있습니다.

위 내용은 std::list::sort(): 왜 하향식 병합 정렬로 전환합니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!