База знанияИзпитен център
BGБългарски
Избери език13

CKTIS / C++

std::set_intersection — сечение на сортирани диапазони

std::set_intersection копира общите елементи на два сортирани диапазона в отделно местоназначение. Запазва дубликатите според по-малкия брой срещания, вместо да връща само уникални стойности.

Версия: C++23; repository compiler flag, production runtime not attested

Синтаксис

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

std::set_intersection от <algorithm> изчислява сечението на [first1, last1) и [first2, last2). Не изисква контейнери std::set. Този текст разглежда класическите претоварвания с итератори без политика за изпълнение; те връщат итератор след последния записан елемент.

И двата диапазона трябва предварително да са сортирани по един и същ ред: по подразбиране според std::less{}, или според подадения компаратор за претоварването comp. Компараторът трябва да задава строго слабо подреждане. Еквивалентност означава !comp(a, b) && !comp(b, a), а не непременно a == b. Несортираните входни данни нарушават предварително условие.

Ако еквивалентна стойност се среща m пъти в първия диапазон и n пъти във втория, резултатът съдържа първите min(m, n) съответстващи елемента от първия диапазон. Резултатът остава сортиран. Броят на сравненията е линеен спрямо общата дължина на входните данни.

Изходният диапазон не трябва да се припокрива с нито един от входните диапазони. Обикновеният изходен итератор изисква достатъчно елементи, в които може да се записва; само reserve() не ги създава. Примерът използва std::back_inserter(common), за да добавя елементи към отделен вектор. Източникът е развиващ се работен проект; примерът е ограничен до API, наличен в C++23.

Примери

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

Резултат

2 2 7

Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.

Източници