CKTIS / C++
std::set_difference — verschil van gesorteerde bereiken
std::set_difference kopieert het verschil van twee gesorteerde bereiken naar een afzonderlijke bestemming. De functie houdt rekening met duplicaten: elke equivalente waarde in het tweede bereik laat één waarde uit het resultaat van het eerste bereik vervallen.
Versie: 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, gedeclareerd in <algorithm>, berekent het gerichte verschil A − B, niet het symmetrische verschil. De functie accepteert twee halfopen iteratorbereiken en een uitvoeriterator; std::set-containers zijn niet vereist. De hier beschreven aanroepen gebruiken geen uitvoeringsbeleid.
Beide bereiken moeten volgens dezelfde volgorde zijn gesorteerd: standaard met std::less{}, of met comp in de tweede vorm. De comparator moet een strikte zwakke ordening definiëren. Equivalentie betekent !comp(a, b) && !comp(b, a), niet noodzakelijk a == b. Als niet aan de sorteervoorwaarde wordt voldaan, is het gedrag ongedefinieerd.
Het algoritme behoudt duplicaten: bij m equivalente elementen in het eerste bereik en n in het tweede kopieert het de laatste max(m - n, 0) elementen uit het eerste bereik, in hun oorspronkelijke volgorde. Het resultaat is gesorteerd; de invoer blijft ongewijzigd.
De bestemming mag geen van beide invoerbereiken overlappen. Als de uitvoeriterator elementen in een bereik overschrijft, moet dat bereik voldoende bestaande, beschrijfbare elementen bevatten. Een uitvoeriterator hoeft echter niet naar bestaande elementen te verwijzen: std::back_inserter voegt elementen achteraan een container toe en std::ostream_iterator schrijft naar een stream. De geretourneerde iterator wijst direct na het geschreven resultaat. De complexiteit is lineair in de gecombineerde lengte van de invoer, exclusief eventueel vooraf sorteren.
Voorbeelden
#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';
}
Resultaat
1 2 4
De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.