std::set_difference
| Определено в заголовочном файле <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.
В результате диапазон также отсортировать. Первая версия ожидает, что обе входные диапазоны должны быть отсортированы с operator<, вторая версия ожидает, что они должны быть отсортированы с данной comp функцией сравнения. Эквивалентные элементы обрабатываются по отдельности, то есть, если какой-то элемент находится m раз в [first1, last1) и n раз в [first2, last2), он будет скопирован в d_first точно std::max(m-n, 0) раз. В результате диапазон не должен пересекаться с любым из входных диапазонов.
Параметры
| first1, last1 | — | диапазон элементов для изучения |
| first2, last2 | — | диапазон элементов для поиска |
| comp | — | объект функции сравнения (т.е. объект, удовлетворяющий требованиям Compare), который возвращает true, если первый аргумент "меньше", чем второй.Определение сравнения должно быть эквивалентно:
Использование |
| Требования к типам | ||
-InputIt1 должен соответствовать требованиям InputIterator.
| ||
-InputIt2 должен соответствовать требованиям InputIterator.
| ||
-OutputIt должен соответствовать требованиям OutputIterator.
| ||
Возвращаемое значение
Iterator за конец построенного диапазона.
Сложность
В большинстве сравнений 2·(N1+N2-1), где N1 = std::distance(first1, last1) и N2 = std::distance(first2, last2).
Возможная реализация
| Первый вариант |
|---|
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, если одна последовательность является подпоследовательностью другой (шаблон функции) | |
| вычисляет симметричную разницу между двумя наборами (шаблон функции) |