Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C++

std::set_union — unija sortiranih raspona

std::set_union zapisuje sortiranu uniju dvaju sortiranih raspona. Čuva najveći broj pojavljivanja ekvivalentnih elemenata iz oba ulaza pa rezultat ne mora sadržavati samo jedinstvene vrijednosti.

Verzija: 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 uniju raspona [first1, last1) i [first2, last2) u izlazni iterator result. Ne zahtijeva spremnike std::set. Ovaj opis obuhvaća uobičajena preopterećenja s iteratorima bez pravila izvođenja; vraćaju iterator iza posljednjeg zapisanog elementa.

Oba ulaza moraju biti sortirana prema istom strogom slabom poretku: zadano prema std::less{} ili prema zadanom comp. Ekvivalentnost znači !comp(a, b) && !comp(b, a), a ne nužno a == b. Kršenje zahtjeva za sortiranje ili nepreklapanje uzrokuje nedefinirano ponašanje.

Ako se klasa ekvivalencije pojavljuje m puta u prvom rasponu i n puta u drugom, rezultat sadrži max(m, n) elemenata: svih m iz prvog, a zatim posljednjih max(n - m, 0) iz drugog, uz očuvanje redoslijeda. To je unija multiskupova, a ne potpuno uklanjanje duplikata.

Izlazni raspon ne smije se preklapati ni s jednim ulazom i mora podržavati sva zapisivanja. std::back_inserter(result) proširuje zaseban vektor; sam reserve() ne stvara elemente u koje se može zapisivati putem begin(). Složenost je O(N1 + N2) za duljine ulaza N1 i N2. Primjer pokazuje očuvanje duplikata.

Primjeri

#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

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

Izvori