set_symmetric_difference


类别: 算法	组件类型: 函数

原型

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 InputIterator1, class InputIterator2, class OutputIterator,
          class StrictWeakOrdering>
OutputIterator set_symmetric_difference(InputIterator1 first1,
                                        InputIterator1 last1,
                                        InputIterator2 first2,
                                        InputIterator2 last2,
                                        OutputIterator result, 
                                        StrictWeakOrdering comp);

描述

Set_symmetric_difference构造已排序的范围，该范围是已排序的范围[first1, last1)和[first2, last2)的对称差集。返回值是输出范围的末尾。

在最简单的情况中，set_symmetric_difference执行集合理论计算：构建两个集合的并集A - B和B - A，其中A和B是两个输入范围。也就是说，输出范围包含每个包含在[first1, last1)但不在[first2, last2)中的元素的副本，以及每个包含在[first2, last2)但不在[first1, last1)中的元素的副本。通常情况下比较复杂，因为输入范围可能包含重复的元素。推论是，如果一个值m次出现在[first1, last1)和n次出现在[first2, last2)中（其中m或n可能为零），那么它|m-n|次出现在输出范围中。 [1]Set_symmetric_difference是稳定的，这意味着每个输入范围中元素的相对顺序是保留的。

两个版本set_symmetric_difference的不同之处在于他们如何定义某个元素是否小于另一个元素。第一个版本使用operator<比较对象，第二个版本使用函数对象comp.

比较对象

定义

在标准头文件 algorithm 和非标准向后兼容性头文件 algo.h 中定义。

对类型的要求

对于第一个版本InputIterator1
是 Input 迭代器的模型。InputIterator1
InputIterator2OutputIterator
对于第一个版本和是 Input 迭代器的模型。是 Output 迭代器的模型。
具有相同的值类型。InputIterator
的值类型是 LessThan Comparable 的模型。对于第一个版本对
具有相同的值类型。的值类型的排序是一个严格的弱排序，如 LessThan Comparable 要求中定义的那样。InputIterator2的值类型可转换为

的值类型集合中的一个类型。

对于第一个版本InputIterator1
是 Input 迭代器的模型。InputIterator1
InputIterator2OutputIterator
对于第二个版本StrictWeakOrdering
对于第一个版本和是 Input 迭代器的模型。是 Output 迭代器的模型。
对于第一个版本是 Strict Weak Ordering 的模型。对于第二个版本的值类型可转换为
具有相同的值类型。的值类型的排序是一个严格的弱排序，如 LessThan Comparable 要求中定义的那样。InputIterator2的值类型可转换为

的实参类型。

对类型的要求

[first1, last1)前提条件
[first2, last2)前提条件
[first1, last1)是一个有效范围。operator<按照升序排列。也就是说，对于和中的每个迭代器对i[first1, last1)j升序排列。也就是说，对于，其中中的每个迭代器对, 在前*j < *i是.
[first2, last2)是一个有效范围。operator<按照升序排列。也就是说，对于和中的每个迭代器对i[first2, last2)j升序排列。也就是说，对于，其中中的每个迭代器对, 在前*j < *i是.
错误的[result, result + n)是一个有效的范围，其中n是两个输入范围对称差中的元素数。
[first1, last1)和[result, result + n)不受重叠。
[first2, last2)和[result, result + n)不受重叠。

的值类型集合中的一个类型。

[first1, last1)前提条件
[first2, last2)前提条件
[first1, last1)是一个有效范围。comp按照升序排列。也就是说，对于和中的每个迭代器对i[first1, last1)j升序排列。也就是说，对于，其中中的每个迭代器对, comp(*j, *i)*j < *i是.
[first2, last2)是一个有效范围。comp按照升序排列。也就是说，对于和中的每个迭代器对i[first2, last2)j升序排列。也就是说，对于，其中中的每个迭代器对, comp(*j, *i)*j < *i是.
错误的[result, result + n)是一个有效的范围，其中n是两个输入范围对称差中的元素数。
[first1, last1)和[result, result + n)不受重叠。
[first2, last2)和[result, result + n)不受重叠。

复杂度

线性。如果任一[first1, last1)或[first2, last2)为空，则为零比较，否则最多为2 * ((last1 - first1) + (last2 - first2)) - 1比较。

示例

inline bool lt_nocase(char c1, char c2) { return tolower(c1) < tolower(c2); }

int main()
{
  int A1[] = {1, 3, 5, 7, 9, 11};
  int A2[] = {1, 1, 2, 3, 5, 8, 13};  
  char A3[] = {'a', 'b', 'b', 'B', 'B', 'f', 'g', 'h', 'H'};
  char A4[] = {'A', 'B', 'B', 'C', 'D', 'F', 'F', 'H' };

  const int N1 = sizeof(A1) / sizeof(int);
  const int N2 = sizeof(A2) / sizeof(int); 
  const int N3 = sizeof(A3);
  const int N4 = sizeof(A4);

  cout << "Symmetric difference of A1 and A2: ";
  set_symmetric_difference(A1, A1 + N1, A2, A2 + N2,
                           ostream_iterator<int>(cout, " "));
  cout << endl 
       << "Symmetric difference of A3 and A4: ";
  set_symmetric_difference(A3, A3 + N3, A4, A4 + N4, 
                           ostream_iterator<char>(cout, " "),
                           lt_nocase);
  cout << endl;
}

输出为

Symmetric difference of A1 and A2: 1 2 7 8 9 11 13 
Symmetric difference of A3 and A4: B B C D F g H

备注

[1] 即使这不是一个完全准确的描述，因为为了对输入范围进行排序，允许采用非总序的严格弱序：可能有值x和y是等效的（即，既没有x < y也没有y < x），但并不相等。请参见可比较的算术运算要求，以获取更完整的讨论。输出范围包括这些元素[first1, last1)其中不存在与[first2, last2)中的等效元素，以及来自[first2, last2)其中不存在与[first1, last1)的这些元素。具体来说，假设范围[first1, last1)包含m相互等效的元素，范围[first2, last2)包含n从同等效类中获得的元素（其中m或n可能会为零）。如果m > n那么输出范围包含来自m - n的这些元素中的最后一个[first1, last1)，如果m < n那么输出范围包含最后一个n - m的这些元素中的最后一个[first2, last2).

另请参见

includes, set_union, set_intersection, set_difference, sort