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

CKTIS / C++

std::set_union — обединение на сортирани диапазони

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

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

Синтаксис

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

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

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

Ако даден клас на еквивалентност се среща m пъти в първия диапазон и n пъти във втория, резултатът съдържа max(m, n) елемента: всички m от първия, последвани от последните max(n - m, 0) от втория, като редът се запазва. Това е обединение на мултимножества, а не пълно премахване на дубликатите.

Изходният диапазон не трябва да се припокрива с нито един от входовете и трябва да позволява всички записи. std::back_inserter(result) увеличава отделен вектор; само reserve() не създава елементи, в които може да се записва чрез begin(). Сложността е O(N1 + N2) при дължини на входовете N1 и N2. Примерът показва запазването на дубликатите.

Примери

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main() {
    const std::vector<int> a{1, 2, 2, 4};
    const std::vector<int> b{2, 3, 3, 4};
    std::vector<int> result;

    std::set_union(a.begin(), a.end(), b.begin(), b.end(),
                   std::back_inserter(result));

    const char* separator = "";
    for (int value : result) {
        std::cout << separator << value;
        separator = " ";
    }
    std::cout << '\n';
}

Резултат

1 2 2 3 3 4

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

Източници