Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C++

std::merge — stabilno spajanje sortiranih raspona

std::merge iz <algorithm> kopira dva sortirana raspona u zaseban izlazni raspon. Čuva duplikate i stabilnost te vraća iterator iza posljednjeg zapisanog elementa.

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

Sintaksa

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

std::merge spaja [first1, last1) i [first2, last2) te zapisuje sve elemente počevši od result. Oba ulaza već moraju biti sortirana prema istom poretku: uzlazno prema zadanim postavkama ili prema poretku koji određuje comp. Usporednik mora definirati strogi slabi poredak. Nesortirani ulazi krše preduvjete algoritma; funkcija ih ne sortira prije spajanja.

Spajanje je stabilno: čuva redoslijed elemenata unutar svakog ulaza, a elementi s ekvivalentnim ključevima iz prvog raspona dolaze prije onih iz drugog. Ekvivalentnost znači da ni comp(a, b) ni comp(b, a) nije istinito. Duplikati ostaju u izlazu.

Izlazni raspon ne smije se preklapati ni s jednim ulaznim rasponom. Osigurajte prostor za zbroj njihovih duljina ili upotrijebite odgovarajući iterator za umetanje. Sam poziv reserve() nad vektorom ne stvara elemente u koje se može pisati putem begin(). Vraćeni iterator pokazuje na mjesto iza posljednjeg zapisanog elementa.

Za ovdje opisane preopterećene funkcije bez pravila izvođenja, rad je linearan u odnosu na ukupan broj elemenata N, uz najviše N - 1 usporedbi kada je N > 0. Nemojte ovu funkciju zamijeniti s std::inplace_merge, koja spaja dva susjedna sortirana podraspona unutar istog raspona. Primjer upotrebljava sintaksu kompatibilnu s C++23; navedeni radni nacrt ažurira se i može sadržavati i kasnija proširenja.

Primjeri

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

Rezultat

1 2 3 3 5 6

Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.

Izvori