std::
set_union
函数模板 <algorithm>| default (1) | template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_union (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result); |
| custom (2) | template <class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator set_union (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp); |
两个排序范围的并集
构造一个排序范围，从result所指向的位置开始， 使用两个排序范围[first1,last1)和[first2,last2)的并集。
两个集合的并集由存在于其中一个集合或两个集合中的元素构成。 第二个范围中的元素如果在第一个范围中有等价的元素，则不会复制到结果范围中。
第一个版本使用operator<比较元素，第二个版本使用comp操作符比较元素。 if (!(a<b) && !(b<a))或if (!comp(a,b) && !comp(b,a)),两个元素a和b被认为是等价的。
范围内的元素应该已经按照相同的标准排序(operator<或comp)。得到的范围也是根据这个排序的。
这个函数模板的行为相当于:
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_union (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result)
{
while (true)
{
if (first1==last1) return std::copy(first2,last2,result);
if (first2==last2) return std::copy(first1,last1,result);
if (*first1<*first2) { *result = *first1; ++first1; }
else if (*first2<*first1) { *result = *first2; ++first2; }
else { *result = *first1; ++first1; ++first2; }
++result;
}
} |
☲ 参数
- first1, last1
- 指向第一个已排序序列初始和最终位置的输入迭代器。使用的范围是[first1,last1)， 它包含first1和last1之间的所有元素，包括first指向的元素，但不包括last指向的元素。
- first2, last2
- 指向第二个排序序列的初始和最终位置的迭代器。使用的范围是[first2,last2)。
- result
- 指向存储结果的范围的初始位置的输出迭代器。指向类型应该支持从其他范围的元素赋值。
- comp
-
二元函数，接受两个由迭代器指向的类型参数，
并返回一个可转换为bool类型的值。
返回的值表示在它定义的特定严格弱排序中，第一个参数是否被认为在第二个参数之前。
函数不能修改它的任何参数。
它可以是函数指针，也可以是函数对象。
☉ 返回值
一个指向所构造范围末尾的迭代器.
☣ 示例
// set_union example
#include <iostream> // std::cout
#include <algorithm> // std::set_union, std::sort
#include <vector> // std::vector
int main () {
int first[] = {5,10,15,20,25};
int second[] = {50,40,30,20,10};
std::vector<int> v(10); // 0 0 0 0 0 0 0 0 0 0
std::vector<int>::iterator it;
std::sort (first,first+5); // 5 10 15 20 25
std::sort (second,second+5); // 10 20 30 40 50
it=std::set_union (first, first+5, second, second+5, v.begin());
// 5 10 15 20 25 30 40 50 0 0
v.resize(it-v.begin()); // 5 10 15 20 25 30 40 50
std::cout << "The union has " << (v.size()) << " elements:\n";
for (it=v.begin(); it!=v.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
} |
输出:
The union has 8 elements:
5 10 15 20 25 30 40 50
The union has 8 elements:
5 10 15 20 25 30 40 50
✥ 复杂度
可达线性2*(count1+count2)-1 ，其中countX是firstX和lastX之间的距离:比较和赋值元素。
⇄ 数据竞争
范围[first1,last1)和[first2,last2)中的对象被访问。 在result和返回值之间的对象被修改。
☂ 异常安全性
如果任何元素比较，元素赋值或迭代器操作抛出，则抛出。
注意，无效的参数会导致未定义的行为。
🍄 另请参阅
| set_intersection | 两个排序范围的交集(函数模板) |
| set_difference | 两个排序范围的差值(函数模板) |
| set_symmetric_difference | 两个排序范围的对称差异(函数模板) |
| merge | 合并已排序的范围(函数模板) |