c – deque :: insert()在索引处？

有一个deque :: insert(迭代器pos,const T& x)函数,它将位置pos作为deque :: iterator和一个元素.使用此方法,您可以逐个插入所有元素.通过deque.begin()索引可以很容易地获得pos(如果你有一个索引,你想在其之前插入元素). insert方法为新插入的元素返回一个迭代器,只需递增此返回的迭代器即可获得下一个位置：

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

然而,由于单个元素的插入是(iirc)线性时间操作,因此这可以缩短O(n * k)时间.

第二个重载是deque :: insert(iterator pos,InputIterator f,InputIterator l)：请记住,简单的指针也满足STL输入迭代器的要求,所以如果你有一个长度为n的C-Style数组T array []你的元素,你可以插入这个数组中的所有元素

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

该操作可以在线性时间内进行,即O(n k).我不确定这是否由标准保证,但我想大多数实现都会有效地完成.

编辑

我快速检查了Microsoft的实现,他们通过push_back或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的Microsofts实现中的代码,删除了调试代码和异常处理,