有没有办法为符合标准的向量实现插入方法？

Question

首先,假设A是一个类型:

• 可能抛出的复制构造函数/赋值运算符.
• 没有移动构造函数/赋值.

这是C++ 03 RAII类型的常见示例.现在让我引用C++ 14标准(剪掉不相关的部分):

§23.2.1一般容器要求

¹¹除非另有规定(见......和23.3.6.5),本条款中定义的所有容器类型均满足以下附加要求:

• 如果在插入单个元素时由insert()或emplace()函数抛出异常,则该函数不起作用.

§23.3.6.5 vector修饰符

iterator insert(const_iterator position, const T& x);
...

¹ 备注:如果新大小大于旧容量,则会导致重新分配.如果没有重新分配,插入点之前的所有迭代器和引用仍然有效.如果除了复制构造函数之外抛出异常,则移动构造函数,赋值运算符或移动赋值运算符T或通过任何InputIterator运算都没有效果.如果在在端部插入单个元件和抛出异常T是CopyInsertable或is_nothrow_move_constructible<T>::value是true,没有影响.否则,如果非移动构造函数抛出异常,CopyInsertable T则不指定效果.

² 复杂性:插入元素的数量加上到向量末尾的距离是复杂的.

现在考虑一下:

std::vector<A> v(5);
v.reserve(10);
v.insert(begin() + 2, A());

显然我们正在插入单个元素,因此§23.2.1 - 11适用,操作成功或v不变.§23.3.6.5对此没有任何改变.复制构造函数抛出异常.我们最后没有插入.不使用移动构造函数.

但是现在考虑在插入的实现过程中这种可能的情况,假设没有重新分配:

01234_____ initial state
0123_4____ making space by copying
012_34____ continued
012?34____ continued, but copy operation threw

此时所有未来的复制操作都可能抛出,从而无法根据需要恢复状态.哎呀.

没有重新分配可以实现强大的异常安全性,我看不到任何实现.这意味着在插入没有移动构造函数和中间抛出复制构造函数的类型时,任何实现都必须始终重新分配.然而:

1. insert(pos, value) 由于不断的重新分配,变得无法忍受.
2. 不满足复杂性要求(重新分配总是需要n操作).

3. 可以说,"如果新的规模大于旧容量,则会导致重新分配." 意味着如果新大小不大于旧容量,则不允许重新分配.

   为了支持这一点,请考虑如果实现可能随时重新分配,则用户无法知道.这保证了保留迭代器("如果没有重新分配,插入点之前的所有迭代器和引用都保持有效.")无用的信息,并且让你想知道为什么两个句子首先被插入到标准中.

1和2是相当诅咒的观察,但如果3是真的那么它(据我所见)根本不可能符合标准.

那么,有没有办法为符合标准的向量实现插入方法？或者这是标准缺陷？

---

这里可以看到这个问题的演示:http://coliru.stacked-crooked.com/a/afd2e838c34c8fcc

Answer 1

就我对标准的解释而言,这里"除非另有说明",否则一旦insert在特定容器的相应条款中指定了关于异常的任何内容,则§23.2.1中列表的要点不再适用.

如果除了[..] 的复制构造函数 [..] 之外抛出异常T,则没有任何影响.

相反的情况表明:当复制构造函数抛出异常时,T无法保证调用不会产生任何影响.要求

如果在插入单个元素时由insert()或emplace()函数抛出异常,则该函数不起作用

不适用:§23.3.6.5规定"否则".