Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C++

std::set_intersection — przecięcie posortowanych zakresów

std::set_intersection kopiuje wspólne elementy dwóch posortowanych zakresów do osobnego miejsca. Zachowuje powtórzenia w liczbie równej mniejszej liczbie ich wystąpień, a nie tylko pojedyncze unikalne wartości.

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

Składnia

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

std::set_intersection z <algorithm> wyznacza przecięcie zakresów [first1, last1) i [first2, last2). Nie wymaga kontenerów std::set. Opis dotyczy klasycznych przeciążeń iteratorowych bez polityki wykonania; zwracają one iterator za ostatnim zapisanym elementem.

Oba zakresy muszą być wcześniej posortowane według tego samego porządku: domyślnie std::less{}, a w wariancie z comp według przekazanego komparatora. Komparator musi określać ścisły słaby porządek. Równoważność oznacza !comp(a, b) && !comp(b, a), niekoniecznie a == b. Nieposortowane dane naruszają warunek wstępny.

Jeżeli równoważna wartość występuje m razy w pierwszym zakresie i n razy w drugim, wynik zawiera pierwsze min(m, n) odpowiadających jej elementów z pierwszego zakresu. Wynik pozostaje posortowany. Liczba porównań jest liniowa względem łącznej długości wejść.

Zakres wynikowy nie może nakładać się na żadne wejście. Zwykły iterator wyjściowy wymaga wystarczającej liczby zapisywalnych elementów; samo reserve() ich nie tworzy. W przykładzie std::back_inserter(common) dopisuje elementy do osobnego wektora. Źródłem jest rozwijany szkic standardu; przykład ograniczono do API dostępnego w C++23.

Przykłady

#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';
}

Wynik

2 2 7

Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.

Źródła