C++

参考

<algorithm>

function template
<algorithm>

std::set_difference

默认 (1)
template <class InputIterator1, class InputIterator2, class OutputIterator>  OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1,                                 InputIterator2 first2, InputIterator2 last2,                                 OutputIterator result);
自定义 (2)
template <class InputIterator1, class InputIterator2,          class OutputIterator, class Compare>  OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1,                                 InputIterator2 first2, InputIterator2 last2,                                 OutputIterator result, Compare comp);
两个已排序范围的差集
将已排序范围 [first1,last1) 与已排序范围 [first2,last2) 的集合差集构造到 result 指向的位置，并形成一个已排序的范围。

两个集合的差集由存在于第一个集合中但不存在于第二个集合中的元素组成。函数复制的元素始终来自第一个范围，顺序保持不变。

对于支持值重复的容器，差集包含第一个范围中给定值的出现次数，减去第二个范围中匹配元素的数量，并保持顺序。

请注意，这是一个单向操作——有关对称等效操作，请参见 set_symmetric_difference。

元素使用第一个版本的 operator< 进行比较，第二个版本使用 comp。两个元素 a 和 b 被视为等效，如果 (!(a<b) && !(b<a)) 或 (!comp(a,b) && !comp(b,a))。

范围中的元素应已根据相同的标准（operator< 或 comp）排序。生成的范围也根据此标准进行排序。

此函数模板的行为等同于
1
2
3
4
5
6
7
8
9
10
11
12
13
 
template <class InputIterator1, class InputIterator2, class OutputIterator>
  OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1,
                                 InputIterator2 first2, InputIterator2 last2,
                                 OutputIterator result)
{
  while (first1!=last1 && first2!=last2)
  {
    if (*first1<*first2) { *result = *first1; ++result; ++first1; }
    else if (*first2<*first1) ++first2;
    else { ++first1; ++first2; }
  }
  return std::copy(first1,last1,result);
}

参数

first1, last1
输入迭代器，指向第一个已排序序列的起始和结束位置。使用的范围是 [first1,last1)，它包含 first1 和 last1 之间的所有元素，包括 first1 指向的元素，但不包括 last1 指向的元素。
first2, last2
输入迭代器，指向第二个已排序序列的起始和结束位置。使用的范围是 [first2,last2)。
result
输出迭代器，指向存储结果序列的范围的起始位置。
被指向的类型应支持被赋值为第一个范围中的元素值。
comp
二进制函数，接受指向输入迭代器的两种类型的参数，并返回可转换为 bool 的值。返回的值指示第一个参数在它定义的特定严格弱序中是否排在第二个参数之前。
该函数不得修改其任何参数。
这可以是指针函数，也可以是函数对象。

这些范围不应重叠。

返回值

指向所构造范围结束位置的迭代器。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
// set_difference example
#include <iostream>     // std::cout
#include <algorithm>    // std::set_difference, std::sort
#include <vector>       // std::vector

int main () {
  int first[] = {5,10,15,20,25};
  int second[] = {50,40,30,20,10};
  std::vector<int> v(10);                      // 0  0  0  0  0  0  0  0  0  0
  std::vector<int>::iterator it;

  std::sort (first,first+5);     //  5 10 15 20 25
  std::sort (second,second+5);   // 10 20 30 40 50

  it=std::set_difference (first, first+5, second, second+5, v.begin());
                                               //  5 15 25  0  0  0  0  0  0  0
  v.resize(it-v.begin());                      //  5 15 25

  std::cout << "The difference has " << (v.size()) << " elements:\n";
  for (it=v.begin(); it!=v.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

输出
The difference has 3 elements:
 5 15 25


复杂度

线性时间，最多为 2*(count1+count2)-1（其中 countX 是 firstX 和 lastX 之间的距离）：比较和赋值元素。

数据竞争

访问范围 [first1,last1) 和 [first2,last2) 中的对象。
修改 result 和返回的迭代器之间的范围内的对象。

异常

如果任何元素比较、元素赋值或迭代器操作抛出异常，则抛出异常。
请注意，无效参数会导致未定义行为。

另见

set_union
两个已排序范围的并集 （函数模板）
set_intersection
两个已排序范围的交集 （函数模板）
set_symmetric_difference
两个已排序范围的对称差集 （函数模板）
merge
合并已排序的范围 （函数模板）