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
Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.