std::set_union

来自cppreference.com
< cpp‎ | algorithm

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

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

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

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

          class OutputIt, class Compare >
OutputIt set_union( 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)的时候,所有m元素将被复制从[first1, last1)d_first,维持秩序,并,然后完全std::max(n-m, 0)元素将被复制从[first2, last2)d_first,也维护秩序。由此获得的范围不能重叠的输入范围.
原文:
Constructs a sorted range beginning at d_first consisting of all elements present in one or 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), then all m elements will be copied from [first1, last1) to d_first, preserving order, and then exactly std::max(n-m, 0) elements will be copied from [first2, last2) to d_first, also preserving order. The resulting range cannot overlap with either of the input ranges.
文本通过谷歌翻译机器翻译。
你可以帮忙校正和验证翻译。点击此处查看指示。

目录

[编辑] 参数

first1, last1 -
第一输入端的排序条件范围
原文:
the first input sorted range
文本通过谷歌翻译机器翻译。
你可以帮忙校正和验证翻译。点击此处查看指示。
first2, last2 -
第二个输入排序的范围
原文:
the second input sorted range
文本通过谷歌翻译机器翻译。
你可以帮忙校正和验证翻译。点击此处查看指示。
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_union(InputIt1 first1, InputIt1 last1,
                   InputIt2 first2, InputIt2 last2,
                   OutputIt d_first)
{
    for (; first1 != last1; ++d_first) {
        if (first2 == last2)
            return std::copy(first1, last1, d_first);
        if (*first2 < *first1) {
            *d_first = *first2++;
        } else {
            *d_first = *first1;
            if (!(*first1 < *first2))
                ++first2;
            ++first1;
        }
    }
    return std::copy(first2, last2, d_first);
}
版本二
template<class InputIt1, class InputIt2,
         class OutputIt, class Compare>
OutputIt set_union(InputIt1 first1, InputIt1 last1,
                   InputIt2 first2, InputIt2 last2,
                   OutputIt d_first, Compare comp)
{
    for (; first1 != last1; ++d_first) {
        if (first2 == last2)
            return std::copy(first1, last1, d_first);
        if (comp(*first2, *first1)) {
            *d_first = *first2++;
        } else {
            *d_first = *first1;
            if (!comp(*first1, *first2))
                ++first2;
            ++first1;
        }
    }
    return std::copy(first2, last2, d_first);
}

[编辑] 示例

[编辑] 另请参阅

如果一个集合是另外一个集合的子集则返回true
(函数模板) [编辑]
计算两个集合的差集
(函数模板) [编辑]
计算两个集合的交集
(函数模板) [编辑]
计算两个集合的对称差
(函数模板) [编辑]