如何使用 C++03 有效地将一系列项目插入中间 std::deque？

Question

我正在使用 C++03 将整数序列插入 std::deque<int>。我看到将一次插入 deque 的唯一方法是使用采用位置、计数和值的重载，或者使用位置、开始输入迭代器和结束输入迭代器。如果我可以使用后者，我会这样做：

#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));
}

但是，boost::counting_iterator 并非在我使用的所有平台上都可用，而且在某些平台上编译器会遇到错误。因此，我尝试按如下方式通过第一次重载来执行此操作，但想知道是否有更有效的方法来执行此操作：

#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;
    }
  }
}

我相信这种方法在 (end - begin) 范围内是线性的，在距 (_recent.end() - insertionPoint) 的距离上也是线性的。我认为这已经是我在这里所能做到的最好了吗？

Answer 1

您可以制作自己的计数迭代器：

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));
}

如何使用 C++03 有效地将一系列项目插入中间 std::deque？

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

c++

std

time-complexity

deque

c++03