Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

CKTIS / C++

std::set_union — unija urejenih obsegov

std::set_union zapiše urejeno unijo dveh urejenih obsegov. Ohrani največje število pojavitev enakovrednih elementov iz obeh vhodov, zato rezultat ne vsebuje nujno samo enoličnih vrednosti.

Različica: C++23; repository compiler flag, production runtime not attested

Sintaksa

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

std::set_union iz <algorithm> kopira unijo obsegov [first1, last1) in [first2, last2) v izhodni iterator result. Ne zahteva vsebnikov std::set. Ta opis zajema običajne preobremenitve z iteratorji brez izvedbene politike; vrnejo iterator za zadnjim zapisanim elementom.

Oba vhoda morata biti urejena po istem strogem šibkem urejanju: privzeto po std::less{} ali po podanem comp. Enakovrednost pomeni !comp(a, b) && !comp(b, a), ne pa nujno a == b. Kršitev zahtev glede urejenosti ali neprekrivanja povzroči nedefinirano vedenje.

Če se ekvivalenčni razred v prvem obsegu pojavi m-krat in v drugem n-krat, rezultat vsebuje max(m, n) elementov: vseh m iz prvega obsega, nato pa zadnjih max(n - m, 0) iz drugega, pri čemer se ohrani vrstni red. To je unija večkratnih množic, ne popolna odstranitev dvojnikov.

Izhodni obseg se ne sme prekrivati z nobenim vhodom in mora podpirati vse zapise. std::back_inserter(result) povečuje ločen vektor; sam reserve() ne ustvari elementov, v katere bi bilo mogoče pisati prek begin(). Časovna zahtevnost je O(N1 + N2) za dolžini vhodov N1 in N2. Primer prikazuje ohranjanje dvojnikov.

Primeri

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main() {
    const std::vector<int> a{1, 2, 2, 4};
    const std::vector<int> b{2, 3, 3, 4};
    std::vector<int> result;

    std::set_union(a.begin(), a.end(), b.begin(), b.end(),
                   std::back_inserter(result));

    const char* separator = "";
    for (int value : result) {
        std::cout << separator << value;
        separator = " ";
    }
    std::cout << '\n';
}

Rezultat

1 2 2 3 3 4

Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.

Viri