如果我使用 vector::begin() 而不是 std::back_inserter(vector) 作为 set_intersection 的输出会发生什么? [英] What happens if I use vector::begin() instead of std::back_inserter(vector) for output of set_intersection?

问题描述

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

矢量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.开始())；

set_intersection 在该参数处需要一个 OutputIterator.我认为的标准只要求 c.begin() 返回一个 forward iterator，我认为它可能是也可能不是 OutputIterator.

反正c.begin()的代码是在clang下编译的.

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

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

解决方案

输出迭代器的重要要求是它在范围内有效且可写
[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.开始())；

一旦 set_intersection 将某些内容写入其输出迭代器，即当 a 和 b 的集合交集不是时，

调用未定义的行为空.

<块引用>

在这种情况下，符合标准的实现是否可以默默地扩展向量，以便 begin() 实际上是一个附加的 OutputIterator，就像 back_inserter 一样?

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

I have been using the highly concise and intuitive C++ syntax for finding the intersection of two sorted vectors and putting the result in a third vector:

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

This should set c to intersection(a,b), assuming a and b are sorted.

But what if I just use c.begin() (I thought I saw an example somewhere of this, which is why I did):

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

set_intersection expects an OutputIterator at that parameter. The standard I believe requires only that c.begin() return a forward iterator, which I suppose might or might not be an OutputIterator.

Anyway, the code with c.begin() compiled under clang.

What is guaranteed to happen under the standard? If this compiles, what is likely to happen - that is, when the iterator returned by c.begin() is eventually incremented past the end of the vector, and an attempt is made to access the element pointed to, what must/may happen? Can a conforming implementation silently extend the vector in this case, so that begin() is in fact an appending OutputIterator like back_inserter is?

I'm asking this mainly to understand how the standard works with iterators: what's really going on, so I can move beyond copy-and-paste in using the STL.

解决方案

The important requirement for an output iterator is that it be valid and write-able for the range
[out, out+size of output).

Passing c.begin() will lead to the values being overwritten which only works if the container c holds enough elements to overwrite. Imagine that c.begin() returns a pointer to an array of size 0 - then you'll see the problem when writing *out++ = 7;.

back_inserter adds every assigned value to a vector (via push_back) and provides a concise way of making the STL-algorithms extend a range - it overloads the operators that are used for iterators appropriately.

Thus

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

invokes undefined behavior once set_intersection writes something to its output iterator, that is, when the set intersection of a and b isn't empty.

Can a conforming implementation silently extend the vector in this case, so that begin() is in fact an appending OutputIterator like back_inserter is?

Of course. It's undefined behavior. (This is a humorous approach of telling you that you shouldn't even consider using this, no matter the effects on any implementation.)

这篇关于如果我使用 vector::begin() 而不是 std::back_inserter(vector) 作为 set_intersection 的输出会发生什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！