c++ - set_union() 返回的迭代器

Question

我有以下使用算法 STL 中的 set_union() 的 C++ 代码:

 9     int first[] = {5, 10, 15, 20, 25};
10     int second[] = {50, 40, 30, 20, 10};
11     vector<int> v(10);
12     vector<int>::iterator it;
13
14     sort(first, first+5);
15     sort(second, second+5);
16
17     it = set_union(first, first + 5, second, second + 5, v.begin());
18
19     cout << int(it - v.begin()) << endl;

我通读了http://www.cplusplus.com/reference/algorithm/set_union/中set_union的文档.我有两个问题:

• 第 17 行。我知道 set_union() 正在返回一个 OutputIterator。我认为迭代器就像从容器对象返回的对象(例如实例化 vector 类，并调用 blah.begin()返回迭代器对象)。我试图了解什么set_union 返回的“it”指向哪个对象？
• 第 19 行。“it - v.begin()”等同于什么。我从“8”的输出值猜测 union 的大小，但如何？

如果有人能阐明一些问题，我们将不胜感激。

谢谢，艾哈迈德。

Answer 1

set_union 的文档指出返回的迭代器指向构造范围的末尾，在您的情况下指向 v 中最后一个元素的一个。由 set_union 写入.

这就是原因it - v.begin()也会导致集合并集的长度。请注意，您可以简单地将两者相减，因为 vector<T>::iterator必须满足 RandomAccessIterator 概念。理想情况下，您应该使用 std::distance计算出两个迭代器之间的间隔。

您的代码片段可以更地道地编写如下:

int first[] = {5, 10, 15, 20, 25};
int second[] = {50, 40, 30, 20, 10};

std::vector<int> v;
v.reserve(10);  // reserve instead of setting an initial size

sort(std::begin(first), std::end(first));       
sort(std::begin(second), std::begin(second));
// use std::begin/end instead of hard coding length

auto it = set_union(std::begin(first), std::end(first), 
                    std::begin(second), std::end(second), 
                    std::back_inserter(v));
// using back_inserter ensures the code works even if the vector is not 
// initially set to the right size

std::cout << std::distance(v.begin(), it) << std::endl;
std::cout << v.size() << std::endl;
// these lines will output the same result unlike your example

---

回应您在下方的评论

What is the use of creating a vector of size 10 or reserving size 10

在您的原始示例中，创建一个 vector初始大小至少为 8 是防止未定义行为所必需的，因为 set_union将向输出范围写入 8 个元素。保留 10 个元素的目的是进行优化，以防止多次重新分配 vector 的可能性。 .这通常不需要或不可行，因为您不会提前知道结果的大小。

I tried with size 1, works fine

1 的大小绝对不能很好地处理您的代码，这是未定义的行为。 set_union将写到 vector 的末尾.出于同样的原因，您会遇到大小为 0 的段错误。推测为什么在第一种情况下没有发生同样的事情是没有意义的，这只是未定义行为的本质。

Does set_union trim the size of the vector, from 10 to 8. Why or is that how set_union() works

您只是将迭代器传递给 set_union ，它对底层容器一无所知。所以它不可能修剪多余的元素，或者在需要时为更多元素腾出空间。它只是不断写入输出迭代器，并在每次写入后递增迭代器。这就是为什么我建议使用 back_inserter ，这是一个将调用 vector::push_back() 的迭代器适配器每当迭代器被写入时。这保证了 set_union永远不会超出 vector 的范围.