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,