Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

CKTIS / C++

std::merge — stabilní slučování seřazených rozsahů

std::merge z hlavičky <algorithm> kopíruje dva seřazené rozsahy do samostatného výstupního rozsahu. Zachovává duplicity i stabilitu a vrací iterátor za posledním zapsaným prvkem.

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

Syntaxe

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

std::merge slučuje [first1, last1) a [first2, last2) a zapisuje všechny prvky od result. Oba vstupy už musí být seřazené podle stejného uspořádání: ve výchozím stavu vzestupně, nebo podle uspořádání určeného pomocí comp. Komparátor musí definovat striktní slabé uspořádání. Neseřazené vstupy porušují předpoklady algoritmu; funkce vstupy nejprve netřídí.

Slučování je stabilní: zachovává pořadí prvků v každém vstupu a prvky s ekvivalentními klíči z prvního rozsahu řadí před prvky z druhého. Ekvivalence znamená, že ani comp(a, b), ani comp(b, a) není pravdivé. Duplicity ve výstupu zůstávají.

Výstupní rozsah se nesmí překrývat s žádným vstupním rozsahem. Zajistěte místo o velikosti součtu jejich délek, nebo použijte vhodný vkládací iterátor. Pouhé zavolání reserve() na vektoru nevytvoří prvky, do kterých lze zapisovat přes begin(). Vrácený iterátor ukazuje na pozici za posledním zapsaným prvkem.

U zde probíraných přetížení bez zásady provádění je práce lineární vzhledem k celkovému počtu prvků N; pro N > 0 se provede nejvýše N - 1 porovnání. Nezaměňujte tuto funkci za std::inplace_merge, která slučuje dva sousední seřazené podrozsahy uvnitř téhož rozsahu. Příklad používá syntaxi kompatibilní s C++23; citovaný pracovní návrh se aktualizuje a může zahrnovat i pozdější rozšíření.

Příklady

#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';
}

Výsledek

1 2 3 3 5 6

Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.

Zdroje