CKTIS / C++
std::set_difference — różnica posortowanych zakresów
std::set_difference kopiuje różnicę dwóch posortowanych zakresów do osobnego miejsca. Uwzględnia liczbę powtórzeń: każde równoważne wystąpienie w drugim zakresie usuwa jedno wystąpienie z wyniku pierwszego.
Wersja: C++23; repository compiler flag, production runtime not attested
Składnia
std::set_difference(first1, last1, first2, last2, result)
std::set_difference(first1, last1, first2, last2, result, comp)std::set_difference z nagłówka <algorithm> oblicza kierunkową różnicę A − B, a nie różnicę symetryczną. Przyjmuje dwa półotwarte zakresy iteratorów i iterator wyjściowy; nie wymaga kontenerów std::set. Opisane wywołania nie używają polityki wykonania.
Oba zakresy muszą być posortowane według tego samego porządku: domyślnie std::less{}, a w drugim wariancie według comp. Komparator musi definiować ścisły słaby porządek. Równoważność oznacza !comp(a, b) && !comp(b, a), niekoniecznie a == b. Niespełnienie warunku posortowania powoduje niezdefiniowane zachowanie.
Algorytm zachowuje powtórzenia: dla m równoważnych elementów w pierwszym zakresie i n w drugim kopiuje ostatnie max(m - n, 0) z pierwszego, w dotychczasowej kolejności. Wynik jest posortowany; wejścia pozostają niezmienione.
Obszar wyniku nie może nakładać się na żaden zakres wejściowy. Jeśli iterator wyjściowy nadpisuje elementy zakresu, zakres ten musi zawierać dostatecznie dużo istniejących elementów, do których można zapisywać. Nie każdy iterator wyjściowy odwołuje się jednak do istniejących elementów: std::back_inserter dodaje elementy na końcu kontenera, a std::ostream_iterator zapisuje do strumienia. Zwracany iterator wskazuje za zapisanym wynikiem. Złożoność jest liniowa względem sumy długości wejść, bez kosztu ich wcześniejszego sortowania.
Przykłady
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <iterator>
#include <vector>
int main() {
const std::vector<int> a{1, 2, 2, 2, 4, 7};
const std::vector<int> b{2, 2, 3, 7};
std::vector<int> difference;
std::set_difference(a.begin(), a.end(), b.begin(), b.end(),
std::back_inserter(difference));
for (std::size_t i = 0; i < difference.size(); ++i) {
if (i != 0) std::cout << ' ';
std::cout << difference[i];
}
std::cout << '\n';
}
Wynik
1 2 4
Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.