c++ - 有没有办法为符合标准的 vector 实现插入方法？

Question

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

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

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

§23.2.1 General container requirements

¹¹ Unless otherwise specified (see ... and 23.3.6.5) all container types defined in this Clause meet the following additional requirements:

• if an exception is thrown by an insert() or emplace() function while inserting a single element, that function has no effects.

§23.3.6.5 vector modifiers

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

¹ Remarks: Causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid. If an exception is thrown other than by the copy constructor, move constructor, assignment operator, or move assignment operator of T or by any InputIterator operation there are no effects. If an exception is thrown while inserting a single element at the end and T is CopyInsertable or is_nothrow_move_constructible<T>::value is true, there are no effects. Otherwise, if an exception is thrown by the move constructor of a non-CopyInsertable T, the effects are unspecified.

² Complexity: The complexity is linear in the number of elements inserted plus the distance to the end of the vector.

现在考虑一下:

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

此时所有 future 的复制操作都可能抛出，从而无法根据需要恢复状态。哎呀。

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

1. insert(pos, value)由于不断的重新分配，速度变得难以忍受。
2. 不满足复杂性要求(重新分配始终需要 n 操作)。

3. 可以说“如果新容量大于旧容量，则导致重新分配。” 意味着如果新容量不大于旧容量，则不允许重新分配.

   为了支持这一点，请考虑一个实现是否可以随时重新分配，用户无法知道。这使得关于保留迭代器的保证(“如果没有发生重新分配，则插入点之前的所有迭代器和引用仍然有效。”)无用的信息，并且让你想知道为什么这两个句子都被插入到标准中首先。

1 和 2 是非常糟糕的观察结果，但如果 3 为真，那么(据我所知)完全不可能符合标准。

那么，有没有办法为符合标准的 vector 实现插入方法？还是这是标准缺陷？

---

可以在此处查看此问题的演示:http://coliru.stacked-crooked.com/a/afd2e838c34c8fcc

Answer 1

就我对标准的解释而言，这里的“除非另有说明”意味着一旦在特定容器的相应子句中为 insert 指定了有关异常的任何内容， §23.2.1 中的列表不再适用。

If an exception is thrown other than by the copy constructor [..] of T [..] there are no effects.

相反:当 T 的复制构造函数抛出异常时，不能保证调用不会产生任何影响。要求

if an exception is thrown by an insert() or emplace() function while inserting a single element, that function has no effects

不适用:§23.3.6.5 规定“否则”。