c++ - 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) 线性时间操作 iirc。

第二个重载是 deque::insert(iterator pos, InputIterator f, InputIterator l):记住简单指针也满足 STL 输入迭代器的要求，所以如果你有一个 C-包含您的元素的长度 n 的样式数组 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());
}

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