CKTIS / C++
std::set_difference — razlika sortiranih raspona
std::set_difference kopira razliku dvaju sortiranih raspona na zasebno odredište. Uvažava duplikate: svaka ekvivalentna pojava u drugom rasponu poništava jednu pojavu iz rezultata prvog raspona.
Verzija: C++23; repository compiler flag, production runtime not attested
Sintaksa
std::set_difference(first1, last1, first2, last2, result)
std::set_difference(first1, last1, first2, last2, result, comp)std::set_difference iz zaglavlja <algorithm> računa usmjerenu razliku A − B, a ne simetričnu razliku. Prihvaća dva poluotvorena raspona iteratora i izlazni iterator; spremnici std::set nisu potrebni. Ovdje opisani pozivi ne upotrebljavaju politiku izvođenja.
Oba raspona moraju biti sortirana prema istom poretku: zadano prema std::less{}, a u drugom obliku prema comp. Usporednik mora definirati strogi slabi poredak. Ekvivalentnost znači !comp(a, b) && !comp(b, a), ne nužno a == b. Kršenje preduvjeta sortiranja uzrokuje nedefinirano ponašanje.
Algoritam čuva duplikate: za m ekvivalentnih elemenata u prvom rasponu i n u drugom kopira posljednjih max(m - n, 0) elemenata iz prvog, njihovim izvornim redoslijedom. Rezultat je sortiran; ulazi ostaju nepromijenjeni.
Odredište se ne smije preklapati ni s jednim ulaznim rasponom. Ako izlazni iterator prepisuje elemente u rasponu, taj raspon mora sadržavati dovoljno postojećih elemenata u koje se može pisati. Izlazni iterator ipak ne mora upućivati na postojeće elemente: std::back_inserter dodaje elemente na kraj spremnika, a std::ostream_iterator piše u tok. Vraćeni iterator pokazuje iza zapisanog rezultata. Složenost je linearna u odnosu na zbroj duljina ulaza, ne računajući prethodno sortiranje.
Primjeri
#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';
}
Rezultat
1 2 4
Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.