如果我使用vector :: begin()而不是std :: back_inserter(vector)来输出set_intersection会发生什么？

Question

我一直在使用高度简洁和直观的C++语法来查找两个已排序的vectors并将结果放在第三个中vector:

vector<bar> a,b,c;
//...
std::set_intersection(a.begin(),a.end(),b.begin(),b.end(),
                      std::back_inserter(c));

这应该设置c为交集(a,b),假设a和b排序.

但是,如果我只是使用c.begin()(我以为我在某个地方看到了一个例子,这就是我做的原因):

 std::set_intersection(a.begin(),a.end(),b.begin(),b.end(),
                       c.begin());

set_intersection期望OutputIteratorat参数.我认为标准只需要c.begin()返回a forward iterator,我想这可能是也可能不是OutputIterator.

无论如何,代码与c.begin()编译下铿锵.

保证在标准下发生什么？如果这编译,可能发生的事情 - 也就是说,当返回的迭代器c.begin()最终递增超过向量的末尾,并且尝试访问指向的元素时,必须/可能发生什么？在这种情况下,符合标准的实现是否可以无声地扩展向量,因此begin()实际上是一个OutputIterator类似的附加back_inserter？

我问这个主要是为了理解标准如何与迭代器一起工作:真正发生了什么,所以我可以使用STL超越复制和粘贴.

Answer 1

back_inserter通过调用将元素插入范围push_back(这就是为什么你不能使用back_inserter不提供push_back操作的范围).

因此,您不必关心超出范围的末尾,因为会push_back自动扩展容器.但是,插入使用不是这种情况begin().

如果您正在使用begin(),那么您必须确保目标范围足够大以容纳所有元素.如果不这样做会立即将您的代码传输到未定义行为的领域.

Answer 2

因为你得到一个有效的迭代器从后面它编译罚款begin的功能,但如果向量是空的,那么你会回来的end迭代器,然后从那里继续.

仅当目标向量已包含至少与您尝试添加的元素一样多时,它才会起作用,然后它实际上会覆盖这些元素而不是添加新元素.

添加元素就是back_inserter迭代器所做的,它返回一个基本上push_back在向量上做的迭代器.

Answer 3

输出迭代器的重要要求是它对
[out, out+输出的范围大小有效且可写).

传递c.begin()将导致覆盖的值,只有当容器c包含足够的元素才能覆盖时才会起作用.想象一下,c.begin()返回一个指向大小为0的数组的指针 - 然后你会在写作时看到问题*out++ = 7;.

back_inserter 增加每分配值给一个vector(通过push_back),并提供使STL-算法扩展的范围内的一个简洁的方式-它重载被适当地用于迭代器的运算符.

从而

 std::set_intersection(a.begin(),a.end(),b.begin(),b.end(),
                       c.begin());

调用未定义行为一旦set_intersection写东西,它的输出迭代器,也就是当的交集a而b不是空的.

在这种情况下,一致的实现是否可以静默扩展向量,因此begin()实际上是一个追加的OutputIterator类似back_inserter的？

当然.这是未定义的行为.(这是一种幽默的方式告诉你,你不应该考虑使用它,不管对任何实现的影响.)