deque::insert() 在索引处？

我如何insert()一堆物品到中间deque在线性时间内？

（我要插入的项目是not可通过 STL 风格的迭代器访问。）

有一个deque::insert(iterator pos, const T&x)函数占据位置pos as deque::iterator和单个元素。使用这种方法，您可以一一插入所有元素。pos可以轻松获得（如果您有一个要在其之前插入元素的索引）deque.begin()+index. The insert方法返回新插入元素的迭代器，只需增加此返回的迭代器即可获取下一个位置：

deque::iterator it = myDeque.begin()+index;
while(n--) {
  it = myDeque.insert(it, currentElement);
  it++;
  currentElement = ... // However you get your next element ...
}

然而这可以O(n*k)时间，因为单个元素的插入是 (iirc) 线性时间操作 iirc。

第二个过载是deque::insert(iterator pos, InputIterator f, InputIterator l)：请记住，简单指针也满足 STL 输入迭代器的要求，因此如果您有一个 C 风格数组T array[]长度n包含您的元素，您可以插入此数组中的所有元素

d.insert(pos, array, array+n);

该操作可以在线性时间内完成，即O(n+k)。我不确定标准是否保证这一点，但我认为大多数实现都会有效地做到这一点。

EDIT

我快速检查了微软的实现，他们通过以下任一序列来实现push_back or push_front，无论哪个更接近pos然后将元素旋转到最终位置，这保证了上述O(n+k)复杂。当然，这也可以“手动”完成，例如：

size_type _Off = pos - d.begin();
size_type _Oldsize = d.size();
if (_Off <= d.size() / 2)
{   // closer to front, push to front then rotate
  while (hasMoreElements())
    push_front(nextElement()); // prepend flipped

  size_type _Num = d.size() - _Oldsize;
  std::reverse(d.begin(), d.begin() + _Num); // flip new stuff in place
  std::rotate(d.begin(), d.begin() + _Num, begin() + _Num + _Off);
}
else
{ // closer to back
  while (hasMoreElements())
    push_front(nextElement()); // prepend flipped

  std::rotate(begin() + _Off, begin() + _Oldsize, end());
}

（我从微软的实现中复制了代码deque::insert，删除调试代码和异常处理，