set_difference

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

原型

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
                              InputIterator2 first2, InputIterator2 last2,
                              OutputIterator result);

template <class InputIterator1, class InputIterator2, class OutputIterator, 
          class StrictWeakOrdering>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
                              InputIterator2 first2, InputIterator2 last2, 
                              OutputIterator result, 
                              StrictWeakOrdering comp);

描述

在最简单的情况下，set_difference执行集合论中的“差集”运算：输出范围包含每个元素的副本，这些元素包含在[first1, last1)中但不包含在[first2, last2)中。一般情况比较复杂，因为输入范围可能包含重复元素。概括地说，如果一个值出现在m次中[first1, last1)和n次中[first2, last2)次（其中m或n可能为零），则它在输出范围中出现max(m-n, 0)次。 [1]Set_difference是稳定的，这意味着元素是从第一个范围而不是第二个范围复制的，并且输出范围中元素的相对顺序与第一个输入范围中的相同。

的两个版本set_difference在如何定义一个元素小于另一个元素方面有所不同。第一个版本使用operator<比较对象，第二个版本使用 函数对象comp.

定义

类型要求

• InputIterator1是 输入迭代器 的模型。
• InputIterator2是 输入迭代器 的模型。
• OutputIterator是 输出迭代器 的模型。
• InputIterator1和InputIterator2具有相同的 value type。
• InputIterator的 value type 是 小于可比较 的模型。
• 对InputIterator1的 value type 对象的排序是严格弱排序，如 小于可比较 要求中所定义。
• InputIterator的 value type 可转换为OutputIterator的一组 value type 中的类型。

• InputIterator1是 输入迭代器 的模型。
• InputIterator2是 输入迭代器 的模型。
• OutputIterator是 输出迭代器 的模型。
• StrictWeakOrdering是 严格弱排序 的模型。
• InputIterator1和InputIterator2具有相同的 value type。
• InputIterator1的 value type 可转换为StrictWeakOrdering的参数类型。
• InputIterator的 value type 可转换为OutputIterator的一组 value type 中的类型。

先决条件

• [first1, last1)是一个有效的范围。
• [first2, last2)是一个有效的范围。
• [first1, last1)按升序排序，根据operator<。也就是说，对于迭代器i和j中的每一对[first1, last1)使得i在j, *j < *i中false.
• [first2, last2)按升序排序，根据operator<。也就是说，对于迭代器i和j中的每一对[first2, last2)使得i在j, *j < *i中false.
• 有足够的空间容纳所有正在复制的元素。更正式地说，要求是[result, result + n)是一个有效的范围，其中n是两个输入范围的差集中的元素数量。
• [first1, last1)和[result, result + n)不重叠。
• [first2, last2)和[result, result + n)不重叠。

• [first1, last1)是一个有效的范围。
• [first2, last2)是一个有效的范围。
• [first1, last1)按升序排序，根据comp。也就是说，对于迭代器i和j中的每一对[first1, last1)使得i在j, comp(*j, *i)中false.
• [first2, last2)按升序排序，根据comp。也就是说，对于迭代器i和j中的每一对[first2, last2)使得i在j, comp(*j, *i)中false.
• 有足够的空间容纳所有正在复制的元素。更正式地说，要求是[result, result + n)是一个有效的范围，其中n是两个输入范围的差集中的元素数量。
• [first1, last1)和[result, result + n)不重叠。
• [first2, last2)和[result, result + n)不重叠。

复杂度

示例

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 << "Difference of A1 and A2: ";
  set_difference(A1, A1 + N1, A2, A2 + N2,
                 ostream_iterator<int>(cout, " "));
  cout << endl 
       << "Difference of A3 and A4: ";
  set_difference(A3, A3 + N3, A4, A4 + N4, 
                   ostream_iterator<char>(cout, " "),
                   lt_nocase);
  cout << endl;
}

输出为

Difference of A1 and A2: 7 9 11 
Difference of A3 and A4: B B g H 

注释

[1] 即使这样也不是一个完全精确的描述，因为允许排序输入范围的排序为严格弱排序而不是全排序：可能存在值x和y它们是等价的（也就是说，既不是x < y也不是y < x），但不等。请参阅 小于可比较 要求以获得更完整的讨论。输出范围由来自[first1, last1)的那些元素组成，对于这些元素，在[first2, last2)中不存在等价元素。具体来说，如果范围[first1, last1)包含m个彼此等价的元素，而范围[first2, last2)包含n包含来自该等价类的m或n个元素（其中任一max(m - n, 0)的这些元素的最后一个[first1, last1)。请注意，此精度仅在元素可以等价但不相等时才重要。如果您使用的是全排序（如果您使用的是strcmp，例如，或者如果您在整数上使用普通的算术比较），那么您可以忽略此技术区别：对于全排序，相等性和等价性是相同的。

另请参阅