KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

CKTIS / C++

std::set_intersection — doorsnede van gesorteerde bereiken

std::set_intersection kopieert de gemeenschappelijke elementen van twee gesorteerde bereiken naar een afzonderlijke bestemming. Duplicaten blijven behouden volgens het kleinste aantal voorkomens, in plaats van alleen unieke waarden op te leveren.

Versie: C++23; repository compiler flag, production runtime not attested

Syntax

#include <algorithm>
std::set_intersection(first1, last1, first2, last2, result);
std::set_intersection(first1, last1, first2, last2, result, comp);

std::set_intersection, gedeclareerd in <algorithm>, berekent de doorsnede van [first1, last1) en [first2, last2). Er zijn geen std::set-containers voor nodig. Deze uitleg behandelt de klassieke iterator-overloads zonder uitvoeringsbeleid; die retourneren een iterator voorbij het laatst geschreven element.

Beide bereiken moeten vooraf volgens dezelfde ordening zijn gesorteerd: standaard std::less{}, of de meegegeven comparator voor de comp-overload. De comparator moet een strikte zwakke ordening definiëren. Equivalentie betekent !comp(a, b) && !comp(b, a), niet noodzakelijk a == b. Ongesorteerde invoer schendt een voorwaarde vooraf.

Als een equivalente waarde m keer voorkomt in het eerste bereik en n keer in het tweede, bevat het resultaat de eerste min(m, n) overeenkomstige elementen uit het eerste bereik. Het resultaat blijft gesorteerd. Het aantal vergelijkingen is lineair met de totale lengte van de invoer.

Het uitvoerbereik mag geen van beide invoerbereiken overlappen. Een gewone outputiterator vereist voldoende beschrijfbare elementen; reserve() maakt die niet op zichzelf aan. Het voorbeeld gebruikt std::back_inserter(common) om elementen aan een afzonderlijke vector toe te voegen. De bron is een in ontwikkeling zijnde werkversie; het voorbeeld beperkt zich tot API die beschikbaar is in C++23.

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, 7};
    std::vector<int> common;

    std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
                          std::back_inserter(common));

    for (std::size_t i = 0; i < common.size(); ++i) {
        if (i != 0) std::cout << ' ';
        std::cout << common[i];
    }
    std::cout << '\n';
}

Resultaat

2 2 7

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.

Bronnen