CKTIS / C++
std::set_difference — rozdíl seřazených rozsahů
std::set_difference zkopíruje rozdíl dvou seřazených rozsahů do samostatného cíle. Zohledňuje duplicity: každý ekvivalentní prvek ve druhém rozsahu zruší jeden výskyt z výsledku prvního rozsahu.
Verze: C++23; repository compiler flag, production runtime not attested
Syntaxe
std::set_difference(first1, last1, first2, last2, result)
std::set_difference(first1, last1, first2, last2, result, comp)std::set_difference z hlavičky <algorithm> počítá směrový rozdíl A − B, nikoli symetrický rozdíl. Přijímá dva polouzavřené rozsahy iterátorů a výstupní iterátor; kontejnery std::set nejsou potřeba. Zde popsaná volání nepoužívají zásadu provádění.
Oba rozsahy musí být seřazeny podle stejného uspořádání: ve výchozím stavu podle std::less{}, ve druhé variantě podle comp. Komparátor musí definovat striktní slabé uspořádání. Ekvivalence znamená !comp(a, b) && !comp(b, a), nikoli nutně a == b. Porušení předpokladu seřazení vede k nedefinovanému chování.
Algoritmus zachovává duplicity: je-li v prvním rozsahu m ekvivalentních prvků a ve druhém n, zkopíruje posledních max(m - n, 0) prvků z prvního rozsahu v jejich původním pořadí. Výsledek je seřazený; vstupy zůstanou beze změny.
Cíl se nesmí překrývat s žádným vstupním rozsahem. Pokud výstupní iterátor přepisuje prvky rozsahu, musí tento rozsah obsahovat dostatek již existujících prvků, do nichž lze zapisovat. Výstupní iterátor ale nemusí odkazovat na existující prvky: std::back_inserter přidává prvky na konec kontejneru a std::ostream_iterator zapisuje do proudu. Vrácený iterátor ukazuje za zapsaný výsledek. Složitost je lineární vzhledem k součtu délek vstupů, bez započtení případného předchozího řazení.
Příklady
#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';
}
Výsledek
1 2 4
Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.