nth_element 예제

std::nth_element 알고리즘은 세 개의 이터레이터를 시작, n번째 위치 및 끝에 대한 이터레이터를 취합니다. 함수가 반환되면 n번째 요소(순서별)는 9번째 가장 작은 요소가 됩니다. (이 함수에는 더 정교한 오버로드가 있습니다(예: 일부 비교 functors; 모든 변형에 대한 위의 링크를 참조하십시오.) std::nth_element()는 STL 알고리즘으로, 목록을 정렬할 경우 n번째 위치에 있는 요소가 해당 위치에 있어야 하는 요소와 같은 방식으로 목록을 다시 정렬합니다. C++ 알고리즘 nth_element() 함수는 오름차순으로 첫 번째 요소와 n번째 요소 사이의 요소를 정렬하는 데 사용되며 n번째와 마지막 사이의 요소는 정렬되지 않습니다. 그러나 n번째와 마지막 사이에 있는 요소는 첫 번째 요소와 9번째 요소 사이의 요소보다 작습니다. 이 예제를 위해 길이 n 시퀀스의 중앙값을 위치 n/2에 있는 요소로 정의해 보겠습니다. 예를 들어 길이 5 시퀀스의 중앙값은 3번째로 작은 요소이며 길이 6 시퀀스의 중앙값도 마찬가지입니다. 이진 함수 구성 요소: std::nth_element는 조건 *i 예를 들어 UI 대화 상자의 항목 목록을 상상할 수 있도록 오름차순으로 [첫 번째, 마지막] 범위를 부분적으로 정렬합니다. 사용자는 연속 범위를 선택한 다음 알고리즘이 이 범위를 가져와 목록의 다른 장소로 이동합니다. C ++ 표준 라이브러리의 알고리즘이 많이 사용되는 코드 예제를 몇 가지 보여 주어 보았습니다.

다음번에는 못생긴 코드를 작성할 때 잠시 멈추고 기존 알고리즘/함수를 호출할 수 있습니다. 나는 빠른 정렬 알고리즘을 설명하지 않습니다 … 당신은 이미 어떻게 작동하는지 알아야합니다! 이 구현에서 std::nth_element는 대부분의 작업을 수행하는 데 사용됩니다. 이 함수는 주어진 n-th 요소가 적절한 위치에 배치되도록 범위를 부분적으로 정렬합니다. n-th 요소 이전의 모든 요소는 n-th 요소 다음의 요소보다 적거나 동일합니다. 물론. 슬라이드와 수집 : 나는 원래 “C ++ 조미료”이야기에서 두 가지 눈에 띄는 예를 건너 뛸 수 없습니다. 더 공식적으로, nth_element부분적으로 범위를 정렬 [첫 번째, 마지막) 오름차순으로 조건이 되도록! (*j < *i) ((1-2) 또는 comp(*j, *i) == false에 대한 (3-4)) 범위 [첫 번째, n번째)]의 모든 i및 [nth, last) 범위의 모든 j에 대해 충족됩니다. 범위가 완전히 정렬된 경우 n번째 위치에 배치된 요소는 정확히 이 위치에서 발생하는 요소입니다.

void nth_element (RandomIt 첫 번째, RandomIt nth, RandomIt 마지막, 몇 시간 전에 나는 CppCon에서 영감을 이야기를 보았다 2013: 숀 부모에 의해 “C ++ 조미료”. 이 프레젠테이션의 주요 포인트 중 하나는 원시 루프를 사용하지 않는 것이었습니다. 대신 기존 알고리즘을 사용하거나 이러한 루프를 `래핑`하는 함수를 작성하는 것을 선호합니다. 나는이 아이디어에 대해 궁금했고 좋은 코드 예제를 검색했습니다. 다음은 더 나은 코드를 작성하는 데 도움이 될 수있는 C ++ std 라이브러리의 알고리즘 사용에 대한 짧은 목록입니다. 이 코드에서는 std:::nth_element의 두 번째 인수에서 가리키는 nth 요소가 배열 v의 여섯 번째 요소이므로 std::nth_element를 적용한 후 배열의 여섯 번째 요소가 전체의 경우 존재했을 수 있는 요소여야 합니다. 레이는 정렬되었다, 즉, 45. 좀 더 흥미로운 예를 알고 계십니까? 내 목록, 확실히, 그들 모두를 표시하지 않습니다! nth_element는 [첫 번째, 마지막)에서 요소를 재정렬하는 부분 정렬 알고리즘입니다: std::nth_element(): O(n)의 시간 복잡성, n은 첫 번째와 마지막 사이의 거리입니다.