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

CKTIS / C++

std::set_difference — разлика на сортирани диапазони

std::set_difference копира разликата на два сортирани диапазона в отделна целева област. Отчита дубликатите: всяко еквивалентно срещане във втория диапазон премахва едно срещане от резултата на първия диапазон.

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

Синтаксис

std::set_difference(first1, last1, first2, last2, result)
std::set_difference(first1, last1, first2, last2, result, comp)

std::set_difference от заглавния файл <algorithm> изчислява насочената разлика A − B, а не симетричната разлика. Приема два полуотворени диапазона от итератори и изходен итератор; контейнери std::set не са необходими. Описаните тук извиквания не използват политика за изпълнение.

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

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

Целевата област не трябва да се припокрива с нито един входен диапазон. Ако изходният итератор презаписва елементи в даден диапазон, този диапазон трябва да съдържа достатъчно вече съществуващи елементи, в които може да се записва. Изходният итератор обаче не е длъжен да сочи към съществуващи елементи: std::back_inserter добавя елементи в края на контейнер, а std::ostream_iterator записва в поток. Върнатият итератор сочи след записания резултат. Сложността е линейна спрямо общата дължина на входовете, без да се включва евентуалното предварително сортиране.

Примери

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

Резултат

1 2 4

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

Източници