当前位置：文江博客话题详情

deque::insert() 在索引处？

发布于 2024-12-11 09:19:06 字数 122 浏览 0 评论 0原文

如何在线性时间内 insert() 将一堆项目插入到 deque 的中间？

（我插入的项目无法通过 STL 样式迭代器访问。）

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

·深蓝 2024-12-18 09:19:06

有一个 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 样式数组 < code>T array[] 长度为 n 包含您的元素，您可以插入此数组中的所有元素

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

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

编辑

我快速检查了微软的实现，他们通过push_back或push_front序列来实现，无论什么更接近pos< /code> 然后将元素旋转到最终位置，这保证了上述 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 实现中复制了代码，删除了调试代码和异常处理，

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,

回复收藏 0 原文