std::set_intersection

来自cppreference.com
< cpp‎ | algorithm

 
 
算法库
执行策略 (C++17)
不修改的序列操作
(C++11)
(C++11)
(C++11)
(C++17)
修改的序列操作
未初始化存储上的操作
划分操作
排序操作
(C++11)
二分查找操作
集合操作(在已排序范围上)
set_intersection
堆操作
(C++11)
最小/最大操作
(C++11)
(C++17)

重排
数值操作
C 库
 
定义于头文件 <algorithm>
template< class InputIt1, class InputIt2, class OutputIt >

OutputIt set_intersection( InputIt1 first1, InputIt1 last1,
                           InputIt2 first2, InputIt2 last2,

                           OutputIt d_first );
(1)
template< class InputIt1, class InputIt2,

          class OutputIt, class Compare >
OutputIt set_intersection( InputIt1 first1, InputIt1 last1,
                           InputIt2 first2, InputIt2 last2,

                           OutputIt d_first, Compare comp );
(2)
构造一个排序的范围开始,d_first中发现的两个排序范围的元素组成的[first1, last1)[first2, last2)。预计两个输入范围进行排序与​​operator<的第一个版本,第二个版本需要进行排序的比较函数comp。如果一些元素被发现m[first1, last1)n[first2, last2)的时候,第一std::min(m, n)元素将被复制到目的范围从第一个范围。等同元件的顺序被保留。由此获得的范围不能重叠的输入范围.
原文:
Constructs a sorted range beginning at d_first consisting of elements that are found in both sorted ranges [first1, last1) and [first2, last2). The first version expects both input ranges to be sorted with operator<, the second version expects them to be sorted with the given comparison function comp. If some element is found m times in [first1, last1) and n times in [first2, last2), the first std::min(m, n) elements will be copied from the first range to the destination range. The order of equivalent elements is preserved. The resulting range cannot overlap with either of the input ranges.
文本通过谷歌翻译机器翻译。
你可以帮忙校正和验证翻译。点击此处查看指示。

目录

[编辑] 参数

first1, last1 -
检查的元素
原文:
the first range of elements to examine
文本通过谷歌翻译机器翻译。
你可以帮忙校正和验证翻译。点击此处查看指示。
first2, last2 -
第二次检查的元素
原文:
the second range of elements to examine
文本通过谷歌翻译机器翻译。
你可以帮忙校正和验证翻译。点击此处查看指示。
comp - 比较函数对象(即满足比较 (Compare) 要求的对象),若首个参数小于第二个,则返回 ​true

比较函数的签名应等价于如下者:

 bool cmp(const Type1 &a, const Type2 &b);

签名不需要拥有 const & ,但函数对象必须不修改传递给它的对象。
类型 Type1Type2 必须使得 InputIt1InputIt2 类型的对象在解引用后能隐式转换到 Type1Type2 两者。 ​

类型要求
-
InputIt1 必须满足 InputIterator 的要求。
-
InputIt2 必须满足 InputIterator 的要求。
-
OutputIt 必须满足 OutputIterator 的要求。

[编辑] 返回值

过去的结尾的Iterator构建范围.
原文:
Iterator past the end of the constructed range.
文本通过谷歌翻译机器翻译。
你可以帮忙校正和验证翻译。点击此处查看指示。

[编辑] 复杂度

2·(N1+N2-1)比较,其中N1= std::distance(first1, last1)N2= std::distance(first2, last2).
原文:
At most 2·(N1+N2-1) comparisons, where N1 = std::distance(first1, last1) and N2 = std::distance(first2, last2).
文本通过谷歌翻译机器翻译。
你可以帮忙校正和验证翻译。点击此处查看指示。

[编辑] 可能的实现

版本一
template<class InputIt1, class InputIt2, class OutputIt>
OutputIt set_intersection(InputIt1 first1, InputIt1 last1,
                          InputIt2 first2, InputIt2 last2,
                          OutputIt d_first)
{
    while (first1 != last1 && first2 != last2) {
        if (*first1 < *first2) {
            ++first1;
        } else  {
            if (!(*first2 < *first1)) {
                *d_first++ = *first1++;
            }
            ++first2;
        }
    }
    return d_first;
}
版本二
template<class InputIt1, class InputIt2,
         class OutputIt, class Compare>
OutputIt set_intersection(InputIt1 first1, InputIt1 last1,
                          InputIt2 first2, InputIt2 last2,
                          OutputIt d_first, Compare comp)
{
    while (first1 != last1 && first2 != last2) {
        if (comp(*first1, *first2)) {
            ++first1;
        } else {
            if (!comp(*first2, *first1)) {
                *d_first++ = *first1++;
            }
            ++first2;
        }
    }
    return d_first;
}


[编辑] 示例

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
int main()
{
    std::vector<int> v1{1,2,3,4,5,6,7,8};
    std::vector<int> v2{        5,  7,  9,10};
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());
 
    std::vector<int> v_intersection;
 
    std::set_intersection(v1.begin(), v1.end(),
                          v2.begin(), v2.end(),
                          std::back_inserter(v_intersection));
    for(int n : v_intersection)
        std::cout << n << ' ';
}

输出:

5 7

[编辑] 另请参阅

计算两个集合的并集
(函数模板) [编辑]