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

概述如何在线性时间内将一堆项目插入到一个双端队列的中间？ (我插入的项目无法通过STL样式的迭代器访问.) 有一个deque :: insert(迭代器pos,const T& x)函数,它将位置pos作为deque :: iterator和一个元素.使用此方法,您可以逐个插入所有元素.通过deque.begin()索引可以很容易地获得pos(如果你有一个索引,你想在其之前插入元素). insert方 如何在线性时间内将一堆项目插入到一个双端队列的中间？

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

解决方法 有一个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实现中的代码,删除了调试代码和异常处理,

总结

以上是内存溢出为你收集整理的c – deque :: insert()在索引处？全部内容，希望文章能够帮你解决c – deque :: insert()在索引处？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。