Difference between revisions of "cpp/algorithm/set difference"

Revision as of 09:57, 21 March 2016

Defined in header `<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 ExecutionPolicy, class InputIt1, class InputIt2, class OutputIt > OutputIt set_difference( ExecutionPolicy&& policy, InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );	(2)	(since C++17)
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 );	(3)
template< class ExecutionPolicy, class InputIt1, class InputIt2, class OutputIt, class Compare > OutputIt set_difference( ExecutionPolicy&& policy, InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp );	(4)	(since C++17)

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.

The resulting range is also sorted. 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.

1) Elements are compared using operator< and the ranges must be sorted with respect to the same.

3) Elements are compared using the given binary comparison function comp and the ranges must be sorted with respect to the same.

2,4) Same as (1,3), but executed according to policy. These overloads do not participate in overload resolution unless std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> is true

first1, last1	-	the range of elements to examine
first2, last2	-	the range of elements to search for
policy	-	the execution policy to use. See execution policy for details.
comp	-	comparison function object (i.e. an object that satisfies the requirements of Compare) which returns true if the first argument is less than (i.e. is ordered before) the second. The signature of the comparison function should be equivalent to the following: bool cmp(const Type1& a, const Type2& b); While the signature does not need to have const&, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) `Type1` and `Type2` regardless of value category (thus, `Type1&` is not allowed, nor is `Type1` unless for `Type1` a move is equivalent to a copy(since C++11)). The types Type1 and Type2 must be such that objects of types InputIt1 and InputIt2 can be dereferenced and then implicitly converted to both Type1 and Type2.
Type requirements Template:par req concept Template:par req concept Template:par req concept

Return value

Iterator past the end of the constructed range.

Complexity

At most $2\cdot(N 1 +N 2 -1)$ comparisons, where $N 1$ = std::distance(first1, last1) and $N 2$ = std::distance(first2, last2).

Exceptions

The overloads with a template parameter named ExecutionPolicy report errors as follows:

If execution of a function invoked as part of the algorithm throws an exception and ExecutionPolicy is one of the standard policies, std::terminate is called. For any other ExecutionPolicy, the behavior is implementation-defined.
If the algorithm fails to allocate memory, std::bad_alloc is thrown.

Possible implementation

First version

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;
}

Second version

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;
}

Example

Run this code

#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';
}

Output:

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

@@ Line 3: / Line 3: @@
 {{dcl begin}}
 {{dcl header | algorithm}}
-{{dcl | num=1 |
+{{dcl | since= | num= 1 |1=
 template< class InputIt1, class InputIt2, class OutputIt >
 OutputIt set_difference( InputIt1 first1, InputIt1 last1,
@@ Line 9: / Line 9: @@
                           OutputIt d_first );
 }}
-{{dcl | num=2 |
+{{dcl | since=c++17 | num= 2 |1=
+template< class ExecutionPolicy, class InputIt1, class InputIt2, class OutputIt >
+OutputIt set_difference( ExecutionPolicy&& policy, InputIt1 first1, InputIt1 last1,
+                         InputIt2 first2, InputIt2 last2,
+                         OutputIt d_first );}}
+{{dcl | since= | num= 3 |1=
 template< class InputIt1, class InputIt2,
            class OutputIt, class Compare >
@@ Line 16: / Line 21: @@
                           OutputIt d_first, Compare comp );
 }}
+{{dcl | since=c++17 | num= 4 |1=
+template< class ExecutionPolicy, class InputIt1, class InputIt2,
+          class OutputIt, class Compare >
+OutputIt set_difference( ExecutionPolicy&& policy, InputIt1 first1, InputIt1 last1,
+                         InputIt2 first2, InputIt2 last2,
+                         OutputIt d_first, Compare comp );}}
 {{dcl end}}
 Copies the elements from the sorted range {{tt|[first1, last1)}} which are not found in the sorted range {{tt|[first2, last2)}} to the range beginning at {{tt|d_first}}.
-The resulting range is also sorted. The first version expects both input ranges to be sorted with {{c|operator<}}, the second version expects them to be sorted with the given comparison function {{tt|comp}}. Equivalent elements are treated individually, that is, if some element is found {{tt|m}} times in {{tt|[first1, last1)}} and {{tt|n}} times in {{tt|[first2, last2)}}, it will be copied to {{tt|d_first}} exactly {{c|std::max(m-n, 0)}} times. The resulting range cannot overlap with either of the input ranges.
+The resulting range is also sorted. Equivalent elements are treated individually, that is, if some element is found {{tt|m}} times in {{tt|[first1, last1)}} and {{tt|n}} times in {{tt|[first2, last2)}}, it will be copied to {{tt|d_first}} exactly {{c|std::max(m-n, 0)}} times. The resulting range cannot overlap with either of the input ranges.
+@1@ Elements are compared using {{tt|operator<}} and the ranges must be sorted with respect to the same.
+@3@ Elements are compared using the given binary comparison function {{tt|comp}} and the ranges must be sorted with respect to the same.
+@2,4@ Same as {{v|1,3}}, but executed according to {{tt|policy}}. These overloads do not participate in overload resolution unless {{c|std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>}} is true
 ===Parameters===
@@ Line 26: / Line 41: @@
 {{par | first1, last1 | the range of elements to examine}}
 {{par | first2, last2 | the range of elements to search for}}
+{{par exec pol}}
 {{par cmp ord | comp | p1=InputIt1 | p2=InputIt2}}
 {{par hreq}}
@@ Line 38: / Line 54: @@
 ===Complexity===
 At most {{math|2&middot;(N<sub>1</sub>+N<sub>2</sub>-1)}} comparisons, where {{math|N<sub>1</sub>}} {{c|{{=}} std::distance(first1, last1)}} and {{math|N<sub>2</sub>}} {{c|{{=}} std::distance(first2, last2)}}.
+===Exceptions===
+{{cpp/algorithm/parallel_exceptions_reporting_behavior|singular=no}}
 ===Possible implementation===

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Metaprogramming library (C++11)
Diagnostics library
General utilities library
Strings library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Numerics library
Localizations library
Input/output library
Filesystem library (C++17)
Regular expressions library (C++11)
Concurrency support library (C++11)
Execution support library (C++26)
Technical specifications
Symbols index
External libraries

includes	returns true if one sequence is a subsequence of another (function template) [edit]
set_symmetric_difference	computes the symmetric difference between two sets (function template) [edit]
std::experimental::parallel::set_difference (parallelism TS)	parallelized version of `std::set_difference` (function template) [edit]

cppreference.com

Namespaces

Variants

Views

Actions

Difference between revisions of "cpp/algorithm/set difference"

Revision as of 09:57, 21 March 2016

Contents

Parameters

Return value

Complexity

Exceptions

Possible implementation

Example

See also

Navigation

Toolbox