deque::insert() at index?

Question

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.)

Answer 1

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,

Answer 2

Call the insert method that takes a sequence of items to insert, see the 3rd method listed here:

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

And, create your own STL-style iterator to access the items you want to insert. See:

Custom Iterator in C++

Answer 3

Input:

Deque: lengtl = l,

New items (m = number of new items)

Algo:

create a new deque (1)

Copy all items from original deque until where you want to insert the new ones (p)

Add new items (m)

Add items from old deque (m-p)

Maybe you can just use the new deque but at worst:

Copy new deque onto old one (after a complete clear: ):

Cost (l+m)

The worst cost is thus: origsize * 2 + newitems which is linear.

The "clear deck" isn't counted here but it is also linear ( at worst).

Answer 4

Add all the elements after the insertion point to a vector.
Remove all elements after insertion point.
Append new range to deque.
Append vector to deque.

This is O(2n) worst case, instead of O(n^2).