set_intersection

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

原型

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

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

描述

在最简单的情况下，set_intersection执行集合论中的“交集”运算：输出范围包含两个[first1, last1)和[first2, last2)都包含的每个元素的副本。一般情况更为复杂，因为输入范围可能包含重复元素。推广的结论是，如果一个值出现在m次于[first1, last1)和n次于[first2, last2)(其中m或n可能为零)，那么它会出现在min(m,n)次于输出范围。[1]Set_intersection为稳定，意味着这两个元素从第一个范围复制，而不是第二个范围，并且输出范围中元素的相对顺序与第一个输入范围的顺序相同。

两个版本set_intersection的元素小于另一元素的定义方式不同。第一个版本使用operator<比较对象，而第二个版本使用 函数对象comp.

比较对象

在标准头 algorithm 中定义，在非标准的后向兼容性头 algo.h 中定义。

• 对于第一个版本InputIterator1
• 为 输入迭代器 的模型。InputIterator1
• InputIterator2OutputIterator
• 对于第一个版本和为 输入迭代器 的模型。为 输出迭代器 的模型。
• 具有相同的值类型。InputIterator
• '的值类型为 小于可比较类型 的模型。对于第一个版本对
• 具有相同的值类型。'的值类型的排序为严格弱排序，如 小于可比较类型 要求中所定义。InputIterator2'的值类型可转换为

• 对于第一个版本InputIterator1
• 为 输入迭代器 的模型。InputIterator1
• InputIterator2OutputIterator
• 对于第二个版本StrictWeakOrdering
• 对于第一个版本和为 输入迭代器 的模型。为 输出迭代器 的模型。
• 对于第一个版本为 严格弱排序 的模型。对于第二个版本'的值类型可转换为
• 具有相同的值类型。'的值类型的排序为严格弱排序，如 小于可比较类型 要求中所定义。InputIterator2'的值类型可转换为

'的实参类型。

• [first1, last1)前提条件
• [first2, last2)前提条件
• [first1, last1)为有效范围。operator<根据按升序排序。也就是说，对于和p中[first1, last1)中的每一对迭代器按升序排序。也就是说，对于ip, j，使得先于.
• [first2, last2)为有效范围。operator<根据按升序排序。也就是说，对于和p中[first2, last2)中的每一对迭代器按升序排序。也就是说，对于ip, j，使得先于.
• *j < *i为falsen是两个输入范围交集中的元素个数。
• [first1, last1)和为无重叠。
• [first2, last2)和为无重叠。

• [first1, last1)前提条件
• [first2, last2)前提条件
• [first1, last1)为有效范围。comp根据按升序排序。也就是说，对于和p中[first1, last1)中的每一对迭代器按升序排序。也就是说，对于ip, comp(*j, *i)，使得先于.
• [first2, last2)为有效范围。comp根据按升序排序。也就是说，对于和p中[first2, last2)中的每一对迭代器按升序排序。也就是说，对于ip, comp(*j, *i)，使得先于.
• *j < *i为falsen是两个输入范围交集中的元素个数。
• [first1, last1)和为无重叠。
• [first2, last2)和为无重叠。

复杂度

示例

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

输出为

Intersection of A1 and A2: 1 3 5 
Intersection of A3 and A4: a b b f h 

注解

[1] 即使如此，这也不是一个完全精确的说明，因为输入范围按其排序的顺序允许为严格弱排序，而不是总排序：可能存在值x和y这些值是等价的（即x < y也不成立y < x），但不是相等的。请参阅 Less Than Comparable 需求，了解更详尽的讨论。输出范围包含[first1, last1)中存在的元素，这些元素在[first2, last2)中有等价元素。具体来说，如果范围[first1, last1)包含n相互等价的元素，并且范围[first1, last1)包含m属于该等价类（其中m或n可以为零）的元素，则输出范围包含第一个min(m, n)来自[first1, last1)的元素。请注意，仅当元素可以等价但不想同时，此精度才显得重要。如果你正在使用总排序（例如正在使用strcmp或者正在对整数使用普通算术比较），那么你可以忽略这个技术区别：对于总排序，等同和等价是相同的。

另请参阅