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恶 ，即可以将其导致UB /不符合要求的，如果行为insert如上所述得到优化？
也许我 do_evil不作恶不够..对铛++ 3.2没有问题（使用的libstdc ++）：
编辑2：新增调用reserve 。 现在，我在做坏事:)
试图做坏事; 帽：6，尺寸：2，成功>：]
试图做坏事; 帽：6，尺寸：3，成功>：]
试图做坏事; 帽：6，大小：4，成功>：]
试图做坏事; 帽：6，尺寸：9，失败>：[
1，3，4，5，6，0，0，135097，2，
编辑：为什么我认为优化可以打破这个：
- 考虑
dst.size() == dst.capacity() == 2开头。 - 要将呼叫
insert需要6一种新的能力。 - 优化放大能力准确6，然后开始通过从复制到插入元件
src迭代器（beg，end）。 - 这种复制是在没有能力检查发生在一个循环中完成的。 （这是最优化。）
- 在复制过程中，另外的元素被添加到载体（W / O型的迭代无效），在
do_evil。 容量现在是不是足够任何更多的持有其余元素被复制。
也许你不得不使用reserve的例子明确强制更新观察到的capacity使用前do_evil 。 目前， insert可能会保留一些能力，但改变什么capacity回报（即观察到的容量）的复制完成之后。
我的标准已经找到迄今为止似乎允许的优化insert ：
[sequence.reqmts] / 3
a.insert(p,i,j)[...]要求：T应EmplaceConstructible为X *从我。
对于载体，如果迭代器不符合前向迭代器要求（24.2.5），T也应MoveInsertable到X和MoveAssignable。 在范围[I，J）的每个迭代应正好一次解引用。
前：i和j不是迭代器成。 第106页在[I，J）元件的插入物拷贝
[vector.modifiers]上insert
1备注：导致重新分配，如果新的尺寸比旧款更大的容量。 如果没有重新分配情况，所有的迭代器和插入点之前引用保持有效。 如果抛出一个异常不是由拷贝构造函数等，将构造函数，赋值运算符，或移动的T赋值运算符或任何InputIterator的操作没有任何影响。 如果一个异常是由非CopyInsertable T的移动构造函数抛出，效果是不确定的。
2复杂性：复杂性是在插入元件的数量加至该载体的端部的距离是线性的。
