Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C++

std::set_union — suma posortowanych zakresów

std::set_union zapisuje posortowaną sumę dwóch posortowanych zakresów. Zachowuje maksymalną liczbę wystąpień równoważnych elementów z obu wejść, więc wynik nie musi zawierać wyłącznie unikalnych wartości.

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

Składnia

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

std::set_union z nagłówka <algorithm> kopiuje sumę zakresów [first1, last1) i [first2, last2) do iteratora wyjściowego result. Nie wymaga kontenerów std::set. Opis dotyczy zwykłych przeciążeń iteratorowych bez polityki wykonania; zwracają one iterator za ostatnim zapisanym elementem.

Oba wejścia muszą być posortowane według tego samego ścisłego słabego porządku: domyślnie std::less{} albo przekazanego comp. Równoważność oznacza !comp(a, b) && !comp(b, a), niekoniecznie a == b. Naruszenie wymagań dotyczących sortowania lub nakładania się zakresów powoduje niezdefiniowane zachowanie.

Jeżeli klasa równoważności występuje m razy w pierwszym zakresie i n razy w drugim, wynik zawiera max(m, n) elementów: wszystkie m z pierwszego, a następnie ostatnie max(n - m, 0) z drugiego, z zachowaniem kolejności. To suma multizbiorów, a nie całkowite usuwanie duplikatów.

Zakres wyjściowy nie może nakładać się na wejścia i musi umożliwiać wszystkie zapisy. std::back_inserter(result) rozszerza osobny wektor; samo reserve() nie tworzy elementów do zapisu przez begin(). Złożoność wynosi O(N1 + N2) dla długości wejść N1 i N2. Przykład pokazuje zachowanie duplikatów.

Przykłady

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

Wynik

1 2 2 3 3 4

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

Źródła