Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C++

std::merge — stabilne scalanie posortowanych zakresów

std::merge z nagłówka <algorithm> kopiuje dwa posortowane zakresy do osobnego zakresu wynikowego. Zachowuje duplikaty oraz stabilność i zwraca iterator za ostatnim zapisanym elementem.

Wersja: C++23; repository compiler flag, production runtime not attested

Składnia

#include <algorithm>
std::merge(first1, last1, first2, last2, result);
std::merge(first1, last1, first2, last2, result, comp);

std::merge scala zakresy [first1, last1) i [first2, last2), zapisując wszystkie elementy od result. Oba wejścia muszą być już posortowane według tego samego porządku: domyślnie rosnącego albo określonego przez comp. Komparator musi definiować ścisły słaby porządek. Niespełnienie warunku posortowania narusza wymagania algorytmu; funkcja nie sortuje najpierw wejść.

Scalanie jest stabilne: zachowuje kolejność elementów w każdym wejściu, a przy równoważnych kluczach elementy pierwszego zakresu trafiają przed elementy drugiego. Równoważność oznacza, że ani comp(a, b), ani comp(b, a) nie jest prawdziwe. Duplikaty pozostają w wyniku.

Zakres wynikowy nie może nakładać się na żaden zakres wejściowy. Zapewnij miejsce na sumę ich długości albo użyj odpowiedniego iteratora wstawiającego. Samo reserve() wektora nie tworzy elementów, do których można zapisywać przez begin(). Zwracany iterator wskazuje pozycję za ostatnim zapisanym elementem.

Dla omawianych przeciążeń bez polityki wykonania praca jest liniowa względem łącznej liczby elementów N, z najwyżej N - 1 porównaniami, gdy N > 0. Nie myl tej funkcji z std::inplace_merge, które scala dwa sąsiednie posortowane podzakresy w tym samym zakresie. Przykład używa składni zgodnej z C++23; cytowany roboczy standard jest aktualizowany i może obejmować także późniejsze rozszerzenia.

Przykłady

#include <algorithm>
#include <array>
#include <iostream>

int main() {
    const std::array<int, 3> a{1, 3, 5};
    const std::array<int, 3> b{2, 3, 6};
    std::array<int, 6> result{};

    const auto end = std::merge(a.begin(), a.end(),
                                b.begin(), b.end(), result.begin());

    for (auto it = result.begin(); it != end; ++it) {
        if (it != result.begin()) {
            std::cout << ' ';
        }
        std::cout << *it;
    }
    std::cout << '\n';
}

Wynik

1 2 3 3 5 6

Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.

Źródła