9

我一直在使用高度简洁和直观的 C​​++ 语法来查找两个 sortedvector的交集并将结果放在第三个中vector：

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

这应该设置c为 intersection( a, b)，假设a和b已排序。

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

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

set_intersection期望OutputIterator在那个参数。我相信的标准只需要c.begin()返回 a forward iterator，我认为它可能是也可能不是OutputIterator。

无论如何，c.begin()在clang下编译的代码。

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

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

4

3 回答 3

10

back_inserter通过调用将元素插入范围中push_back（这就是为什么不能back_inserter与不提供push_back操作的范围一起使用的原因）。

因此，您不会关心超出范围的末尾，因为push_back会自动扩展容器。但是，使用 insert 的情况并非如此begin()。

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

于 2014-11-30T17:03:19.060 回答
6

它编译得很好，因为你从begin函数中得到了一个有效的迭代器，但是如果向量是空的，那么你将得到end迭代器，然后从那里继续。

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

添加元素正是back_inserter迭代器所做的，它返回一个基本上push_back在向量上执行的迭代器。

于 2014-11-30T17:03:40.080 回答
5

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

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

back_inserter 将每个分配的值添加到 a vector(via push_back) 并提供一种使 STL 算法扩展范围的简洁方法 - 它适当地重载了用于迭代器的运算符。

因此

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

set_intersection一旦将某些内容写入其输出迭代器，即当 和 的集合交集a不b为空时，就会调用未定义的行为。

在这种情况下，符合要求的实现是否可以默默地扩展向量，以便 begin() 实际上是一个附加OutputIterator项back_inserter？

当然。这是未定义的行为。（这是一种幽默的方法，告诉你你甚至不应该考虑使用它，不管对任何实现的影响。）

于 2014-11-30T17:07:07.820 回答