How can I efficiently insert a series of items into the middle std::deque with C++03?

Question

I'm using C++03 to insert a sequence of integers into a std::deque<int>. The only way I see to insert one time into a deque is using either the overloading that takes a position, count, and value or using a position, beginning input iterator, and ending input iterator. If I could use the later, I would do this:

#include <deque>
#include <boost/iterator/counting_iterator.hpp>

void
insertRecent(const int begin,
             const int end, // Assumes end >= begin
             std::deque<int> &_recent,
             std::deque<int>::iterator insertionPoint)
{
  _recent.insert(insertionPoint,
                 boost::counting_iterator<int>(begin),
                 boost::counting_iterator<int>(end));
}

However, the boost::counting_iterator is not available on all the platforms I am using and further on some platforms the compiler runs into a bug with it. Therefore, I'm trying to do this with the first overloading as follows, but wonder if there is a more efficient way to do this:

#include <deque>

void
insertRecent(const int begin,
             const int end, // Assumes end >= begin
             std::deque<int> &_recent,
             std::deque<int>::iterator insertionPoint)
{
  if (begin != end) {
    int offset = begin;
    const size_type count = static_cast<size_type>(end - begin);
    const size_type insertEndDistance = _recent.end() - insertionPoint;

    // Make space for all the items being inserted.
    _recent.insert(insertionPoint, count, begin);

    // Start off at the iterator position of the first item just inserted.
    // In C++11 we can just use the return value from deque::insert().
    std::deque<int>::iterator itr = _recent.end() - (count + insertEndDistance);

    for (; ++offset != end; ) {
      *++itr = offset;
    }
  }
}

I believe this approach is linear on the (end - begin) range and linear on the distance from (_recent.end() - insertionPoint). Am I correct in thinking this is as good as I can do here?

Answer 1

You can make your own counting iterator:

class my_int_iterator {
    int v_;
public:
    my_int_iterator (int v = 0) : v_(v) {}
    int operator * () const { return v_; }
    my_int_iterator & operator ++ () { ++v_; return *this; }
    bool operator != (my_int_iterator mii) const { return v_ != mii.v_; }

    typedef std::input_iterator_tag iterator_category;
    typedef int value_type;
    typedef void difference_type;
    typedef void pointer;
    typedef void reference;
};

void
insertRecent(const int begin,
             const int end, // Assumes end >= begin
             std::deque<int> &_recent,
             std::deque<int>::iterator insertionPoint)
{
  _recent.insert(insertionPoint,
                 my_int_iterator(begin),
                 my_int_iterator(end));
}