Пространства имён
Варианты
Действия

set_difference

Материал из cppreference.com
< cpp‎ | algorithm

 
 
Библиотека алгоритмов
Ограниченные алгоритмы и алгоритмы над диапазонами (C++20)
Ограниченные алгоритмы, например ranges::copy, ranges::sort, ...
Политики исполнения (C++17)
Немодифицирующие операции над последовательностями
(C++11)(C++11)(C++11)
(C++17)
Модифицирующие операции над последовательностями
Операции разбиения
Операции сортировки
(C++11)
Операции двоичного поиска
Операции с наборами (в отсортированных диапазонах)
set_difference
Операции с кучей
(C++11)
Операций минимума/максимума
(C++11)
(C++17)

Операции перестановки
Числовые операции
Операции с неинициализированной памятью
(C++17)
(C++17)
(C++17)
Библиотека C
 
Определено в заголовочном файле <algorithm>
template< class InputIt1, class InputIt2, class OutputIt >

OutputIt set_difference( InputIt1 first1, InputIt1 last1,
                         InputIt2 first2, InputIt2 last2,

                         OutputIt d_first );
(1)
template< class InputIt1, class InputIt2,

          class OutputIt, class Compare >
OutputIt set_difference( InputIt1 first1, InputIt1 last1,
                         InputIt2 first2, InputIt2 last2,

                         OutputIt d_first, Compare comp );
(2)
Копирует элементы из отсортированного диапазона [first1, last1), которые не встречаются в отсортированном диапазоне [first2, last2) в диапазоне начиная с d_first.
Оригинал:
Copies the elements from the sorted range [first1, last1) which are not found in the sorted range [first2, last2) to the range beginning at d_first.
Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
В результате диапазон также отсортировать. Первая версия ожидает, что обе входные диапазоны должны быть отсортированы с operator<, вторая версия ожидает, что они должны быть отсортированы с данной comp функцию сравнения. Эквивалентные элементы обрабатываются по отдельности, то есть, если какой-то элемент находится m раз в [first1, last1) и n раз в [first2, last2), он будет скопирован в d_first точно std::max(m-n, 0) раз. В результате диапазон не должен пересекаться с любым из входных диапазонов.
Оригинал:
The resulting range is also sorted. The first version expects both input ranges to be sorted with operator<, the second version expects them to be sorted with the given comparison function comp. Equivalent elements are treated individually, that is, if some element is found m times in [first1, last1) and n times in [first2, last2), it will be copied to d_first exactly std::max(m-n, 0) times. The resulting range cannot overlap with either of the input ranges.
Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.

Содержание

[править] Параметры

first1, last1
диапазон элементов для изучения
Оригинал:
the range of elements to examine
Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
first2, last2
диапазон элементов для поиска
Оригинал:
the range of elements to search for
Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
comp функция сравнения, возвращающая ​true если первый аргумент меньше второго.

Сигнатура функции сравнения должна быть эквивалентна следующей:

 bool cmp(const Type1 &a, const Type2 &b);

Сигнатура на обязана содержать const &, однако, функция не может изменять переданные объекты.
Типы Type1 и Type2 должны быть таковы, что объекты типов InputIt1 и InputIt2 могут быть разыменованы и затем неявно преобразованы в Type1 и Type2 соответственно. ​

Требования к типам
-
InputIt1 должен соответствовать требованиям InputIterator.
-
InputIt2 должен соответствовать требованиям InputIterator.
-
OutputIt должен соответствовать требованиям OutputIterator.

[править] Возвращаемое значение

Iterator в конце прошлого построен диапазон.
Оригинал:
Iterator past the end of the constructed range.
Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.

[править] Сложность

В большинстве сравнений 2·(N1+N2-1), где N1 = std::distance(first1, last1) и N2 = std::distance(first2, last2).
Оригинал:
At most 2·(N1+N2-1) comparisons, where N1 = std::distance(first1, last1) and N2 = std::distance(first2, last2).
Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.

[править] Возможная реализация

Первый вариант
template<class InputIt1, class InputIt2, class OutputIt>
OutputIt set_difference(InputIt1 first1, InputIt1 last1,
                        InputIt2 first2, InputIt2 last2,
                        OutputIt d_first)
{
    while (first1 != last1) {
        if (first2 == last2) return std::copy(first1, last1, d_first);
 
        if (*first1 < *first2) {
            *d_first++ = *first1++;
        } else {
            if (! (*first2 < *first1)) {
                ++first1;
            }
            ++first2;
        }
    }
    return d_first;
}
Второй вариант
template<class InputIt1, class InputIt2,
         class OutputIt, class Compare>
OutputIt set_difference( InputIt1 first1, InputIt1 last1,
                         InputIt2 first2, InputIt2 last2,
                         OutputIt d_first, Compare comp)
{
    while (first1 != last1) {
        if (first2 == last2) return std::copy(first1, last1, d_first);
 
        if (comp(*first1, *first2)) {
            *d_first++ = *first1++;
        } else {
            if (!comp(*first2, *first1)) {
                ++first1;
            }
            ++first2;
        }
    }
    return d_first;
}

[править] Пример

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
 
int main() {
    std::vector<int> v1 {1, 2, 5, 5, 5, 9};
    std::vector<int> v2 {2, 5, 7};
    std::vector<int> diff;
 
    std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(),
                        std::inserter(diff, diff.begin()));
 
    for (auto i : v1) std::cout << i << ' ';
    std::cout << "minus ";
    for (auto i : v2) std::cout << i << ' ';
    std::cout << "is: ";
 
    for (auto i : diff) std::cout << i << ' ';
    std::cout << '\n';
}

Вывод:

1 2 5 5 5 9 minus 2 5 7 is: 1 5 5 9

[править] См. также

возвращает true, если одна последовательность является подпоследовательностью другой
(шаблон функции) [править]
вычисляет симметричную разницу между двумя наборами
(шаблон функции) [править]