vector::insert(dst_iterator, src_begin, src_end)（插入范围）可以针对随机访问迭代器进行优化，以src_end - src_begin首先保留所需的容量，然后执行复制。
我的主要问题是：标准是否还允许vector::insert避免对每个复制元素进行容量检查？（即不在push_back要插入的每个元素上使用或类似）
我将避免这种容量检查称为“优化insert”。
可能出了什么问题：我可以想象一个迭代器在取消引用时会产生副作用：
注意：标准保证传递给的迭代器insert将被取消引用一次（见问题结尾）。
#include <vector>
#include <iterator>
#include <iostream>
template < typename T >
struct evil_iterator : std::iterator < std::random_access_iterator_tag, T >
{
using base = std::iterator < std::random_access_iterator_tag, T >;
std::vector<T>* evil_feedback;
typename std::vector<T>::iterator innocent_iterator;
evil_iterator( std::vector<T>* c,
typename std::vector<T>::iterator i )
: evil_feedback{c}
, innocent_iterator{i}
{}
void do_evil()
{
std::cout << "trying to do evil; ";
std::cout << "cap: " << evil_feedback->capacity() << ", ";
std::cout << "size: " << evil_feedback->size() << ", ";
// better not invalidate the iterators of `*evil_feedback`
// passed to the `insert` call (see example below)
if( evil_feedback->capacity() > evil_feedback->size() )
{
evil_feedback->push_back( T{} );
// capacity() might be == size() now
std::cout << "successful >:]" << std::endl;
}else
{
std::cout << "failed >:[" << std::endl;
}
}
T& operator*()
{
do_evil(); // <----------------------------------------
return *innocent_iterator;
}
// non-evil iterator member functions-----------------------
evil_iterator& operator++()
{
++innocent_iterator;
return *this;
}
evil_iterator& operator++(int)
{
evil_iterator temp(*this);
++(*this);
return temp;
}
evil_iterator& operator+=(typename base::difference_type p)
{
innocent_iterator += p;
return *this;
}
evil_iterator& operator-=(typename base::difference_type p)
{
innocent_iterator -= p;
return *this;
}
evil_iterator& operator=(evil_iterator const& other)
{
evil_feedback = other.evil_feedback;
innocent_iterator = other.innocent_iterator;
return *this;
}
evil_iterator operator+(typename base::difference_type p)
{
evil_iterator temp(*this);
temp += p;
return temp;
}
evil_iterator operator-(typename base::difference_type p)
{
evil_iterator temp(*this);
temp -= p;
return temp;
}
typename base::difference_type operator-(evil_iterator const& p)
{
return this->innocent_iterator - p.innocent_iterator;
}
bool operator!=(evil_iterator const& other) const
{ return innocent_iterator != other.innocent_iterator; }
};
例子：
int main()
{
std::vector<int> src = {3, 4, 5, 6};
std::vector<int> dst = {1, 2};
evil_iterator<int> beg = {&dst, src.begin()};
evil_iterator<int> end = {&dst, src.end()};
// explicit call to reserve, see below
dst.reserve( dst.size() + src.size() );
// using dst.end()-1, which stays valid during `push_back`,
// thanks to Ben Voigt pointing this out
dst.insert(dst.end()-1, beg, end); // <--------------- doing evil?
std::copy(dst.begin(), dst.end(),
std::ostream_iterator<int>{std::cout, ", "});
}
问题：
- 可以
vector::insert优化以避免对每个插入元素进行容量检查吗？ - 仍然是
evil_iterator有效的迭代器吗？ - 如果是这样，是
evil_iterator邪恶insert的，即如果如上所述进行优化，它会导致 UB / 不合规行为吗？
也许我do_evil的不够邪恶..在clang++ 3.2上没有问题（使用libstdc++）：
编辑 2：添加了对reserve. 现在，我在做坏事:)
试图作恶；cap: 6, size: 2, 成功 >:]
试图作恶；cap: 6, size: 3, 成功 >:]
试图作恶；cap: 6, size: 4, 成功 >:]
试图作恶；上限：6，大小：9，失败 >:[
1, 3, 4, 5, 6, 0, 0, 135097, 2,
编辑：为什么我认为优化可以打破这一点：
- 一开始就考虑
dst.size() == dst.capacity() == 2。 - 调用
insert需要新容量 6。 - 优化将容量精确地扩大到 6，然后通过从
src迭代器 (beg,end) 复制来开始插入元素。 - 此复制在不进行容量检查的循环内完成。（这就是优化。）
- 在复制过程中，更多元素被添加到向量中（不使迭代器无效），在
do_evil. 现在的容量不再足以容纳要复制的其余元素。
也许您必须reserve在示例中明确使用以强制capacity在使用之前更新可观察对象do_evil。目前，insert可以保留一些容量，但capacity只有在复制完成后才能更改返回的内容（即可观察容量）。
到目前为止，我在标准中发现的似乎允许优化insert：
[sequence.reqmts]/3
a.insert(p,i,j)[...]要求：T 应该是 EmplaceConstructible 从 *i 到 X 的。
对于向量，如果迭代器不满足前向迭代器要求（24.2.5），T 也应该是 MoveInsertable 到 X 和 MoveAssignable。[i,j) 范围内的每个迭代器都应该被取消引用一次。
pre: i 和 j 不是 a 的迭代器。在 p 之前插入 [i, j) 中元素的副本
[vector.modifiers] 开启insert
1 备注：如果新大小大于旧容量，则导致重新分配。如果没有发生重新分配，则插入点之前的所有迭代器和引用仍然有效。如果异常被 T 的复制构造函数、移动构造函数、赋值运算符或移动赋值运算符或任何 InputIterator 操作引发，则没有任何影响。如果非 CopyInsertable T 的移动构造函数抛出异常，则未指定效果。
2 复杂度：复杂度与插入的元素数量加上到向量末端的距离成线性关系。