std::set_difference
| Определено в заголовочном файле <algorithm>
|
||
| template< class InputIt1, class InputIt2, class OutputIt > OutputIt set_difference( InputIt1 first1, InputIt1 last1, |
(1) | |
| template< class InputIt1, class InputIt2, class OutputIt, class Compare > |
(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, если первый аргумент "меньше", чем второй. Определение сравнения должно быть эквивалентно: bool cmp(const Type1 &a, const Type2 &b); Использование noexcept (начиная с C++11) желательно но не обязательно. Параметры не обязаны передаваться по const&, но не должны модифицироваться. Они должны быть способны принимать все значения типа (даже const) |
| Требования к типам | ||
-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, если одна последовательность является подпоследовательностью другой (шаблон функции) | |
| вычисляет симметричную разницу между двумя наборами (шаблон функции) |
