deque :: insert()在索引？

Question

我如何insert()将一堆物品deque放在线性时间的中间？

(我插入的项目无法通过STL样式的迭代器访问.)

Answer 1

有一个deque::insert(iterator pos, const T&x)函数将位置pos作为deque::iterator单个元素.使用此方法,您可以逐个插入所有元素.pos可以很容易地获得(如果你有一个索引,你想在之前插入元素)deque.begin()+index.该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)线性时间操作的时间.

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

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

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

编辑

我快速检查了微软的实现,他们通过一系列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());
}

(我复制了Microsofts实现的deque::insert代码,删除了调试代码和异常处理,