deque :: insert（）在index？

问题描述

我如何 insert（）在线性时间中的 deque / p>

（我插入的项目是不可通过STL式迭代器访问。）

deque :: insert（iterator pos，const T& x）函数采用位置 pos 为 deque :: iterator 和一个元素。使用此方法，您可以逐个插入所有元素。 deque.begin（）+ index pos （如果你有一个索引要插入元素） c $ c>。 insert 方法为新插入的元素返回一个迭代器，只需将返回的迭代器增加到下一个位置：

  deque :: iterator it = myDeque.begin（）+ index; 
 while（n--）{
 it = myDeque.insert（it，currentElement）; 
 it ++; 
 currentElement = ... //但是你得到你的下一个元素... 
} 
  

$ b b

然而，由于单个元素的插入是（iirc）一个线性时间运算iirc，所以 O（n * k）
$ b

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

  d.insert（pos，array，array + n）; 
  

此操作可以在线性时间执行，即 O k）。我不知道这是否由标准保证，但我想大多数实现将有效地。

EDIT

我快速检查了Microsoft的实现， push 或 push_front 的顺序，无论更接近 pos 然后将元素旋转到它们的最终位置，这保证了上述 O（n + k）复杂性。当然，也可以手动完成，例如：

  size_type _Off = pos  -  d.begin 
 size_type _Oldsize = d.size（）; 
 if（_Off  {//接近前面，推到前面然后旋转
 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 
 {//靠近后面
 while（hasMoreElements（））
 push_front（nextElement（））; // prepend flipped 
 
 std :: rotate（begin（）+ _Off，begin（）+ _Oldsize，end（））; 
} 
  

（我复制的代码来自Microsoft的实现 deque :: insert ，删除调试代码和异常处理，

How do I insert() a bunch of items to the middle of a deque in linear time?

(The items I am inserting are not accessible through an STL-style iterator.)

解决方案

There is a deque::insert(iterator pos, const T&x) function taking the position pos as deque::iterator and a single element. Using this method you could insert all elements one by one. pos can easily be obtained (if you have an index before which you want to insert the element) by deque.begin()+index. The insert method returns an iterator for the newly inserted element, simply increment this returned iterator to get the next position:

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

This however cantake O(n*k) time, since insertion of a single element is (iirc) a linear time operation iirc.

The second overload is deque::insert(iterator pos, InputIterator f, InputIterator l): Remember that simple pointers also fulfill the requirements of an STL input iterator, so if you have a C-Style array T array[] of length n containing your elements, you could insert all elements from this array with

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

This operation can be carried out in linear time, i.e. O(n+k). I'm not sure if this is guaranteed by the standard, but I suppose that most implementation will do it efficiently.

EDIT

I quickly checked with Microsoft's implementation, they do it by a sequence of either push_back or push_front, whatever is closer to pos and then rotating the elements to their final place, which guarantees the above O(n+k) complexity. Of course, that could also be done "by hand" like:

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());
}

(I copied the code from Microsofts implementation of deque::insert, removing debug code and exception handling,

这篇关于deque :: insert（）在index？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！