STL - sort

sort

범위의 요소 정렬

std::invoke(comp, std::invoke(proj, *(it + n)), std::invoke(proj, *it))

1. 요소는 주어진 comp 비교 함수를 통해 비교가 진행됨
2. 이때, ranges::begin(r) ~ ranges::end(r)로 범위를 표현할 수 있음

 

Time Complexity

O(Nlog(N))

이때, N = ranges::distance(first, last)이다.

 

struct sort_fn
{
    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
        operator()(I first, S last, Comp comp = {}, Proj proj = {}) const
    {
        if (first == last)
            return first;
 
        I last_iter = ranges::next(first, last);
        ranges::make_heap(first, last_iter, std::ref(comp), std::ref(proj));
        ranges::sort_heap(first, last_iter, std::ref(comp), std::ref(proj));
 
        return last_iter;
    }
 
    template<ranges::random_access_range R, class Comp = ranges::less,
             class Proj = std::identity>
    requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
    constexpr ranges::borrowed_iterator_t<R>
        operator()(R&& r, Comp comp = {}, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r), std::move(comp), std::move(proj));
    }
};
 
inline constexpr sort_fn sort {};