3

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

（我插入的项目不能通过STL 风格的迭代器访问。）

4

4 回答 4

7

有一个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 样式数组T array[]，n你可以插入这个数组中的所有元素

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

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

编辑

我很快检查了微软的实现，他们通过一个push_backor的序列来完成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，删除了调试代码和异常处理，

于 2011-10-22T20:36:29.423 回答
1

调用 insert 方法，该方法需要插入一系列项目，请参见此处列出的第 3 个方法：

http://msdn.microsoft.com/en-us/library/zcww84w5(v=vs.71).aspx

并且，创建您自己的 STL 风格的迭代器来访问您想要插入的项目。看：

C++ 中的自定义迭代器

于 2011-10-22T20:35:34.110 回答
0

输入：

双端队列：lentl = l，

新项目（m = 新项目数）

算法：

创建一个新的双端队列 (1)

复制原始双端队列中的所有项目，直到您要插入新项目的位置 (p)

添加新项目（米）

从旧双端队列 (mp) 添加项目

也许您可以只使用新的双端队列，但最糟糕的是：

将新双端队列复制到旧双端队列上（完全清除后：）：

成本 (l+m)

因此，最坏的成本是：origsize * 2 + newitems 这是线性的。

这里没有计算“透明甲板”，但它也是线性的（在最坏的情况下）。

于 2011-10-22T20:31:59.433 回答
0

将插入点之后的所有元素添加到向量中。
删除插入点之后的所有元素。
将新范围附加到双端队列。
将向量附加到双端队列。

这是 O(2n) 最坏的情况，而不是 O(n^2)。

于 2011-10-22T22:25:49.373 回答