28 Algorithms library [algorithms]

28.7 Sorting and related operations [alg.sorting]

28.7.6 Set operations on sorted structures [alg.set.operations]

1
#

В этом разделе определены все основные операции над сортированными структурами. Они также работают с multisets несколькими копиями эквивалентных элементов. Семантика заданных операций обобщается на multisets стандартным способом, определяя set_­union() максимальное количество вхождений каждого элемента, set_­intersection() минимальное и т. Д.

28.7.6.1 includes [includes]

template<class InputIterator1, class InputIterator2> bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> bool includes(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template<class InputIterator1, class InputIterator2, class Compare> bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Compare> bool includes(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, Compare comp);

1
#

Returns: true если[first2, last2) пусто или если каждый элемент в диапазоне [first2, last2) содержится в диапазоне [first1, last1). Вfalse противном случае возвращается .

2
#

Complexity: Максимум 2 * ((last1 - first1) + (last2 - first2)) - 1 сравнений.

28.7.6.2 set_­union [set.union]

template<class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator> ForwardIterator set_union(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result); template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator, class Compare> ForwardIterator set_union(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result, Compare comp);

1
#

Requires: Результирующий диапазон не должен перекрываться ни с одним из исходных диапазонов.

2
#

Effects: Создает отсортированное объединение элементов из двух диапазонов; то есть набор элементов, которые присутствуют в одном или обоих диапазонах.

3
#

Returns: Конец построенного диапазона.

4
#

Complexity: Максимум 2 * ((last1 - first1) + (last2 - first2)) - 1 сравнений.

5
#

Remarks: Если[first1, last1) содержитm элементы, которые эквивалентны друг другу , и[first2, last2) содержитn элементы, которые эквивалентны их, то всеm элементы из первого диапазона должны быть скопированы в выходном диапазоне, в порядке, а затемmax(n−m,0) элементы из второго диапазона должны быть скопированы в выходном диапазоне , чтобы.

28.7.6.3 set_­intersection [set.intersection]

template<class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator> ForwardIterator set_intersection(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result); template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator, class Compare> ForwardIterator set_intersection(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result, Compare comp);

1
#

Requires: Результирующий диапазон не должен перекрываться ни с одним из исходных диапазонов.

2
#

Effects: Создает отсортированное пересечение элементов из двух диапазонов; то есть набор элементов, которые присутствуют в обоих диапазонах.

3
#

Returns: Конец построенного диапазона.

4
#

Complexity: Максимум 2 * ((last1 - first1) + (last2 - first2)) - 1 сравнений.

5
#

Remarks: Если[first1, last1) содержитm элементы, которые эквивалентны друг другу , и[first2, last2) содержитn элементы, которые эквивалентны них, первыеmin(m,n) элементы должны быть скопированы из первого диапазона выходного диапазона, в порядке.

28.7.6.4 set_­difference [set.difference]

template<class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator> ForwardIterator set_difference(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result); template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator, class Compare> ForwardIterator set_difference(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result, Compare comp);

1
#

Requires: Результирующий диапазон не должен перекрываться ни с одним из исходных диапазонов.

2
#

Effects: Копирует элементы диапазона [first1, last1) , отсутствующие в диапазоне, [first2, last2) в диапазон, начинающийся с result. Элементы в построенном диапазоне сортируются.

3
#

Returns: Конец построенного диапазона.

4
#

Complexity: Максимум 2 * ((last1 - first1) + (last2 - first2)) - 1 сравнений.

5
#

Remarks: Если [first1, last1) содержитm элементы, которые эквивалентны друг другу и [first2, last2) содержитn элементы, которые приравненных к ним, последние max(m−n,0) элементы из [first1, last1) должны быть скопированы в выходной диапазон.

28.7.6.5 set_­symmetric_­difference [set.symmetric.difference]

template<class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator> ForwardIterator set_symmetric_difference(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result); template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator, class Compare> ForwardIterator set_symmetric_difference(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result, Compare comp);

1
#

Requires: Результирующий диапазон не должен перекрываться ни с одним из исходных диапазонов.

2
#

Effects: Копирует элементы диапазона [first1, last1) , отсутствующие в диапазоне [first2, last2), и элементы диапазона [first2, last2) , отсутствующие в диапазоне, [first1, last1) в диапазон, начинающийся с result. Элементы в построенном диапазоне сортируются.

3
#

Returns: Конец построенного диапазона.

4
#

Complexity: Максимум 2 * ((last1 - first1) + (last2 - first2)) - 1 сравнений.

5
#

Remarks: Если[first1, last1) содержитm элементы, которые эквивалентны друг другу и [first2, last2) содержитn элементы, которые приравненных к ним, то |m−n| из этих элементов должны быть скопированы в выходной диапазон: последний m−n из этих элементов от[first1, last1) еслиm>n, и последний n−m из этих элементов ,[first2, last2) еслиm<n.