ranges::nth_element
ranges::nth_element (n번째 원소 — ranges)
범위를 재배열해 nth 위치의 원소가 정렬했을 때 그 위치에 올 원소가 되도록 하는 ranges 버전 알고리즘이에요. <algorithm> 헤더에 있어요.
출처: cppreference
본문
std::ranges::nth_element는 [first, last)의 요소를 재배열해, nth 위치에 정렬 순서상 올 원소를 놓아요.
namespace std::ranges {
template< std::random_access_iterator I, std::sentinel_for<I> S,
class Comp = ranges::less, class Proj = std::identity >
requires std::sortable<I, Comp, Proj>
constexpr I nth_element( I first, I nth, S last, Comp comp = {}, Proj proj = {} );
}
nth앞에는 그보다 작거나 같은 원소들, 뒤에는 크거나 같은 원소들이 오지만 내부는 정렬되지 않아요.- 평균 복잡도:
last - first에 선형.
std::vector<int> v{9, 2, 7, 1, 5, 3, 8};
std::ranges::nth_element(v, v.begin() + 3);
// v[3]은 정렬 시 4번째로 작은 값
전체 정렬 없이 "k번째로 작은 원소"를 찾는 ranges 버전이에요.