std::ranges:: inplace_merge

Объединяет два последовательных отсортированных диапазона [ first , middle ) и [ middle , last ) в один отсортированный диапазон [ first , last ) .

Последовательность называется отсортированной относительно компаратора comp и проекции proj , если для любого итератора it , указывающего на последовательность, и любого неотрицательного целого числа n такого, что it + n является допустимым итератором, указывающим на элемент последовательности, std:: invoke ( comp, std:: invoke ( proj, * ( it + n ) ) , std:: invoke ( proj, * it ) ) ) вычисляется в false .

Эта функция слияния является стабильной , что означает, что для эквивалентных элементов в исходных двух диапазонах, элементы из первого диапазона (сохраняя свой исходный порядок) предшествуют элементам из второго диапазона (сохраняя свой исходный порядок).

Функциональные сущности, описанные на этой странице, являются алгоритмическими функциональными объектами (неформально известными как niebloids ), то есть:

• Явные списки аргументов шаблона не могут быть указаны при вызове любого из них.
• Ни один из них не видим для поиска, зависимого от аргументов .
• Когда любой из них найден обычным поиском без квалификации как имя слева от оператора вызова функции, поиск, зависимый от аргументов , блокируется.

Параметры

Возвращаемое значение

Итератор, равный last .

Сложность

Ровно N − 1 сравнений, если доступен дополнительный буфер памяти, где N = ranges:: distance ( first, last ) . В противном случае, \(\scriptsize \mathcal{O}(N\cdot\log{(N)})\) 𝓞(N•log(N)) сравнений. Дополнительно, в обоих случаях количество проекций вдвое превышает количество сравнений.

Примечания

Эта функция пытается выделить временный буфер. Если выделение завершается неудачей, выбирается менее эффективный алгоритм.

Возможная реализация

Эта реализация показывает только более медленный алгоритм, используемый когда нет доступной дополнительной памяти. Смотрите также реализацию в MSVC STL и libstdc++ .

struct inplace_merge_fn
{
    template<std::bidirectional_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, I middle, S last, Comp comp = {}, Proj proj = {}) const
    {
        I last_it = ranges::next(middle, last);
        inplace_merge_slow(first, middle, last_it,
                           ranges::distance(first, middle),
                           ranges::distance(middle, last_it),
                           std::ref(comp), std::ref(proj));
        return last_it;
    }
    template<ranges::bidirectional_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, ranges::iterator_t<R> middle,
                   Comp comp = {}, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), std::move(middle), ranges::end(r),
                       std::move(comp), std::move(proj));
    }
private:
    template<class I, class Comp, class Proj>
    static constexpr void inplace_merge_slow(I first, I middle, I last,
                                             std::iter_difference_t<I> n1,
                                             std::iter_difference_t<I> n2,
                                             Comp comp, Proj proj)
    {
        if (n1 == 0 || n2 == 0)
            return;
        if (n1 + n2 == 2 && comp(proj(*middle), proj(*first)))
        {
            ranges::iter_swap(first, middle);
            return;
        }
        I cut1 = first, cut2 = middle;
        std::iter_difference_t<I> d1{}, d2{};
        if (n1 > n2)
        {
            d1 = n1 / 2;
            ranges::advance(cut1, d1);
            cut2 = ranges::lower_bound(middle, last, *cut1,
                                       std::ref(comp), std::ref(proj));
            d2 = ranges::distance(middle, cut2);
        }
        else
        {
            d2 = n2 / 2;
            ranges::advance(cut2, d2);
            cut1 = ranges::upper_bound(first, middle, *cut2,
                                       std::ref(comp), std::ref(proj));
            d1 = ranges::distance(first, cut1);
        }
        I new_middle = ranges::rotate(cut1, middle, cut2);
        inplace_merge_slow(first, cut1, new_middle, d1, d2,
                           std::ref(comp), std::ref(proj));
        inplace_merge_slow(new_middle, cut2, last, n1 - d1, n2 - d2,
                           std::ref(comp), std::ref(proj));
    }
};
inline constexpr inplace_merge_fn inplace_merge {};

Пример

#include <algorithm>
#include <complex>
#include <functional>
#include <iostream>
#include <iterator>
#include <vector>
void print(auto const& v, auto const& rem, int middle = -1)
{
    for (int i{}; auto n : v)
        std::cout << (i++ == middle ? "│ " : "") << n << ' ';
    std::cout << rem << '\n';
}
template<std::random_access_iterator I, std::sentinel_for<I> S>
requires std::sortable<I>
void merge_sort(I first, S last)
{
    if (last - first > 1)
    {
        I middle{first + (last - first) / 2};
        merge_sort(first, middle);
        merge_sort(middle, last);
        std::ranges::inplace_merge(first, middle, last);
    }
}
int main()
{
    // демонстрация пользовательской сортировки слиянием
    std::vector v{8, 2, 0, 4, 9, 8, 1, 7, 3};
    print(v, ": before sort");
    merge_sort(v.begin(), v.end());
    print(v, ": after sort\n");
    // слияние с объектом функции сравнения и проекцией
    using CI = std::complex<int>;
    std::vector<CI> r{{0,1}, {0,2}, {0,3}, {1,1}, {1,2}};
    const auto middle{std::ranges::next(r.begin(), 3)};
    auto comp{std::ranges::less{}};
    auto proj{[](CI z) { return z.imag(); }};
    print(r, ": before merge", middle - r.begin());
    std::ranges::inplace_merge(r, middle, comp, proj);
    print(r, ": after merge");
}

8 2 0 4 9 8 1 7 3 : before sort
0 1 2 3 4 7 8 8 9 : after sort
(0,1) (0,2) (0,3) │ (1,1) (1,2) : before merge
(0,1) (1,1) (0,2) (1,2) (0,3) : after merge

Смотрите также