CKTIS / C++
std::set_difference — rozdiel usporiadaných rozsahov
std::set_difference skopíruje rozdiel dvoch usporiadaných rozsahov do samostatného cieľa. Zohľadňuje duplicity: každý ekvivalentný prvok v druhom rozsahu zruší jeden výskyt z výsledku prvého rozsahu.
Verzia: C++23; repository compiler flag, production runtime not attested
Syntax
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číta smerový rozdiel A − B, nie symetrický rozdiel. Prijíma dva polootvorené rozsahy iterátorov a výstupný iterátor; kontajnery std::set nie sú potrebné. Tu opísané volania nepoužívajú politiku vykonávania.
Oba rozsahy musia byť usporiadané podľa rovnakého poradia: predvolene podľa std::less{}, v druhej forme podľa comp. Komparátor musí definovať striktné slabé usporiadanie. Ekvivalencia znamená !comp(a, b) && !comp(b, a), nie nevyhnutne a == b. Porušenie predpokladu usporiadania vedie k nedefinovanému správaniu.
Algoritmus zachováva duplicity: pri m ekvivalentných prvkoch v prvom rozsahu a n v druhom skopíruje posledných max(m - n, 0) prvkov z prvého rozsahu v ich pôvodnom poradí. Výsledok je usporiadaný; vstupy zostanú nezmenené.
Cieľ sa nesmie prekrývať so žiadnym vstupným rozsahom. Ak výstupný iterátor prepisuje prvky rozsahu, tento rozsah musí obsahovať dostatok už existujúcich prvkov, do ktorých sa dá zapisovať. Výstupný iterátor však nemusí odkazovať na existujúce prvky: std::back_inserter pridáva prvky na koniec kontajnera a std::ostream_iterator zapisuje do prúdu. Vrátený iterátor ukazuje za zapísaný výsledok. Zložitosť je lineárna vzhľadom na súčet dĺžok vstupov, bez započítania prípadného predchádzajúceho usporiadania.
Prí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ýsledok
1 2 4
Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.