如何确保迭代器不会超越end()？

Question

我一直在使用advance一些iterators,但恐怕上述可能的越级end().我想确保我的迭代器保持在界限之间,我想到了distance但似乎它没有返回我期望的东西(迭代器超越时的非正值end()).你怎么能确保没有越级？

#include <iostream>
#include <iterator>
#include <list>
using namespace std;

int main () {
  list<int> mylist;
  for (int i=0; i<10; i++) mylist.push_back (i*10);

  list<int>::const_iterator first = mylist.begin();
  const list<int>::const_iterator last = mylist.end();

  cout << "The distance is: " << distance(first,last) << endl; // 10
  advance(first, 10);
  cout << "The distance is: " << distance(first,last) << endl; // 0
  advance(first, 1);
  cout << "The distance is: " << distance(first,last) << endl; // 10
  advance(first, 10);
  cout << "The distance is: " << distance(first,last) << endl; // 0

  return 0;
}

这是输出:

The distance is: 10
The distance is: 0
The distance is: 10
The distance is: 0

Answer 1

advance()last end()导致未定义的行为.根据这个片段,你将不得不进行测试:

  template <class Iter, class Incr>
  void safe_advance(Iter& curr, const Iter& end, Incr n)
  {
    size_t remaining(std::distance(curr, end));
    if (remaining < n)
    {
      n = remaining;
    }
    std::advance(curr, n);
  }

你需要考虑当你没有移动全部金额时会发生什么(curr返回为end().

Answer 2

调用distance或advance除了以下模型之外的任何东西都是低效的RandomAccessIterator:调用是O(n),其中n表示距离.

而且,list并不是真正的模型,Sequence因为它的size方法不能保证是恒定的(甚至是摊销的常数),实际上它很可能是O(n).

查看代码(如果你不能使用除a之外的任何东西list),因此有两种可能性:

• 不要使用提前,一次移动一个项目并end在每个步骤检查.
• 在开始时一次性计算大小,然后你知道在调用未定义的行为之前你可以提前多少(你可以在旁边保留一个计数器,包装迭代器等等......)

让我们采取行动:

// Advance one at a time
// replace calls to advance by this function

typedef list<int>::const_iterator const_iterator;

const_iterator safe_advance(const_iterator it, const_iterator end, size_t n)
{
  for (size_t i = 0; i != n && it != end; ++i) { ++it; }
  return it;
}


// Precompute size
size_t const size = list.size();

size_t remaining = size;
const_iterator begin = list.begin();

size_t ad = std::min(10, remaining);
advance(begin, ad);
remaining -= ad;

ad = std::min(1, remaining);
advance(begin, ad);
remaining -= ad;

尽管如此,这仍然很繁琐.

编辑:

解决大卫关于推广解决方案的合理关注:

// Advance `it` from n, or up to end
// returns the number of steps that could not be performed
template <typename Iterator>
size_t safe_advance(Iterator& it, Iterator const& end, size_t n)
{
  size_t i = 0;
  for (; i != n && it != end; ++i, ++it);
  return n - i;
}

请注意,对于双向迭代器,advance可以使用负距离,但这也需要引入,begin并且会变得非常繁琐.因此,我更喜欢第二种方法:

template <typename BI>
size_t safe_reverse(BI& it, BI const& begin, size_t n)
{
  for (; n != 0 && it != begin; --n, --it);
  return n;
}

最后,虽然我不会在这里做,但是专门化模板会很好,RandomAccessIterator因为这些操作可以在O(1)中完成.

Answer 3

距离做不到这一点。当您的容器不提供随机访问时，它会尝试通过提前启动到达终点，这将在启动最后超过时造成严重破坏。

你必须从一个有效的起点开始（即通过提前开始你可以到达最后一个）并在每次前进之前检查距离，并且只能前进 X<=(distance(first,last) 以便不超过最后一个。