在std::vector中插入一个元素到同一向量中是否允许?

18

请考虑以下std::vector<T>insertemplace成员函数:

template <class... Args> iterator emplace(const_iterator position, Args&&... args);
iterator insert(const_iterator position, const T& x);
iterator insert(const_iterator position, T&& x);
iterator insert(const_iterator position, size_type n, const T& x);

如果其中一个使用向量本身的元素作为参数调用,会发生什么?通常,它们中的每一个都会使从position开始的所有元素的引用无效,这可能包括参数,或者如果发生重新分配,则会使对全部元素的引用,其中肯定包括它,但这是否意味着这样的调用无效,或者插入(似乎)先发生?

查看一些常见实现会得到奇怪的结果:

  • libstdc++在const T&重载的insert中移动任何元素之前复制参数。 它包含以下注释:

    三个操作的顺序由C++0x case指定,其中move操作可能会修改现有向量中属于新元素的对象。 这只适用于通过const lvalue ref获取元素的调用者(请参阅23.1/13)。

    但是,C++11 §23.1只是容器库的简要摘要,即使我们假设这是指§23.2.1(在C++03中曾经是§23.1),§23.2.1/13也仅提供了allocator-aware容器的定义,似乎与此无关。 我已经查看了第23章,但是我没有在任何地方找到任何相关内容。

  • libc++在emplace中移动任何元素之前创建一个临时对象,而在insert中,它首先移动元素,但是将参数引用转换为指针,并调整它以确保它指向原始元素-但是,它仅在const T&重载中执行所有这些操作。

  • Visual C++在所有情况下在移动任何元素之前复制/创建一个临时对象。

我错过了标准定义这种行为的地方吗? 为什么我查看的三个C ++库彼此不同意? 为什么libstdc ++注释说这只是insert(const_iterator,const T&)的问题? 如果标准不要求这起作用,那么为什么库要费力使其起作用? (肯定会造成一些可以避免的复制和/或移动。)最后,如果我正在实现应该类似于std :: vector 的容器,我应该让这个工作吗?


我认为你正在看到C++历史上的一些奇怪现象。如果vector在今天重新设计(在C++11之后),我认为你会发现insert方法将通过值传递其参数,依赖于可移动性意识的可用性以提高性能。 - Richard Hodges
请参见DR2164。我认为这个情感是,这应该是明确定义的。标准中指定的前置条件已经满足,因此实现的负担在于按照正确的顺序执行操作以满足后置条件。 - Igor Tandetnik
@RichardHodges 我部分同意你的看法,但请注意,移动操作并不总是便宜的。例如,请考虑std::array - Chortos-2
@IgorTandetnik 而且(同样地),这仍然留下了“insert(const_iterator,const T &)”的问题未解决。由于它只调用允许抛出异常并使容器处于修改状态的复制构造函数,它能否避免临时变量并在移动/重新分配后进行构造? - Chortos-2
1
@Chortos-2的移动可能不总是便宜的,但复制绝对不会更便宜。 - Richard Hodges
显示剩余3条评论
1个回答

8
首先回答第二个问题:标准明确规定标准库可以假设通过右值引用传递时,该右值引用是该对象的唯一引用。这意味着它不能合法地是向量的元素。C++11 17.6.4.9/1中的相关部分如下:
  • 如果函数参数绑定到右值引用参数,则实现可能假设该参数是对此参数的唯一引用。…… [注意:如果程序将左值强制转换为xvalue,同时将该左值作为库函数的参数传递(例如,通过调用带有参数move(x)的函数),则程序实际上要求该函数将该左值视为临时值。如果参数是左值,则实现可以自由地优化别名检查。—结束注释]
这只留下我们处理const T &情况。即使libstdc ++和libc ++在此情况下不同,它们的最终结果是相同的-它们将正确地从传递的对象复制。标准仅规定行为而不是实现。只要它们实现正确的行为,就可以。

啊,这是一个很好的观点!好的,现在 rvalue 引用重载的情况已经很清楚了。另一个评论指出 emplace 首先需要构造元素以符合强异常保证,因为它可能调用任意构造函数。但是 const-lval-ref 的 insert 呢?标准似乎没有明确定义。它说函数“插入参数的副本”,但这是否实际意味着在引用失效之前就已经制作了副本呢? - Chortos-2
@Chortos-2 除非我误解了你的问题,你已经表明所有三种实现都确保从有效的源代码进行复制。那么问题是什么? - Angew is no longer proud of SO
@Chortos-2:还要注意的是,这些通常在标准文档中有记录。不同的“插入”重载对别名引用有不同的要求。例如,那些接受元素范围(两个迭代器)的重载需要确保迭代器不引用容器本身。 - David Rodríguez - dribeas
@Angew 他们确实这样做,但是他们必须这样做吗?为什么? - Chortos-2
2
@Chortos-2:它们必须这样做,因为标准中定义了在正确位置插入原始对象的行为。对于对象是否可能与向量内的元素别名没有任何限制,因此实现需要确保即使出现别名情况也要遵循所需的行为。与具有此前提条件的insert(p,i,j)进行比较:i和j不是a的迭代器--这是另一个原因,为什么您不应该尝试重新实现标准容器,因为实现可能不会那么好。 - David Rodríguez - dribeas
相关信息:这个规则的部分原理是为了避免移动操作必须执行自我移动检查。 - M.M

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接