14

我一直在使用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
4

6 回答 6

15

Advance() 过去 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().

于 2010-10-04T15:26:22.640 回答
8

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) 中完成。

于 2010-10-04T19:13:03.830 回答
5

距离无法做到这一点。当您的容器不提供随机访问时，它会尝试通过推进 start 到达 end，这将在 start 超过最后一个时造成严重破坏。

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

于 2010-10-04T15:09:28.660 回答
3

很简单。避免超越.end()只是避免超越.end()。这种情况与避免使用NULL指针等没有什么不同。构造你的代码，使其永远不会发生。例如，使用循环it != v.end()等条件。一些流行的标准库实现会检测到这些错误并让你知道，但你不应该依赖它，只在测试/调试期间使用它。

更新

如果你不能确定你advance()的数量可以大于一，那么你绝对不能advance()超过一。

于 2010-10-04T15:08:58.363 回答
3

一方面，您还可以编写一个迭代器包装器来存储结束迭代器并检查关键操作。

例如iterator_facade，为了简洁起见，使用 boost's 而不是检查下溢。

#include <boost/iterator/iterator_facade.hpp>
#include <iterator>
#include <stdexcept>

template <class Iter>
class checked_iterator:
    public boost::iterator_facade<
        checked_iterator<Iter>,
        typename std::iterator_traits<Iter>::value_type,
        typename std::iterator_traits<Iter>::iterator_category
    >
{
    Iter it, end;
public:
    checked_iterator(Iter it, Iter end): it(it), end(end) {} 
    void increment() 
    { 
        if (it == end) { throw std::range_error("checked_iterator: increment beyond end"); }
        ++it;
    }
    void decrement()
    {
        //TODO: this is not checked
        --it;
    }
    bool equal(const checked_iterator& other) const
    {
        return it == other.it;
    }
    typename std::iterator_traits<Iter>::reference dereference() const 
    {
        if (it == end) { throw std::range_error("checked_iterator: dereference end"); }
        return *it;
    }
    void advance(typename std::iterator_traits<Iter>::difference_type n)
    {
        //TODO: not checked for underflow
        if (std::distance(it, end) < n) { throw std::range_error("checked_iterator: advance beyond end"); }
        it += n;
    }
    typename std::iterator_traits<Iter>::difference_type distance_to(const checked_iterator& other) const
    {
        return other.it - it;
    }
    Iter base() const { return it; }
};

//create checked_iterators from containers, could be overloaded for arrays
template <class Container>
checked_iterator<typename Container::iterator> checked_begin(Container& c)
{
    return checked_iterator<typename Container::iterator>(c.begin(), c.end());
}

template <class Container>
checked_iterator<typename Container::const_iterator> checked_begin(const Container& c)
{
    return checked_iterator<typename Container::const_iterator>(c.begin(), c.end());
}

template <class Container>
checked_iterator<typename Container::iterator> checked_end(Container& c)
{
    return checked_iterator<typename Container::iterator>(c.end(), c.end());
}

template <class Container>
checked_iterator<typename Container::const_iterator> checked_end(const Container& c)
{
    return checked_iterator<typename Container::const_iterator>(c.end(), c.end());
}

示例测试代码：

#include <vector>
#include <list>
#include <iostream>
int main()
{
    typedef std::list<int> Container;
    try {
        Container v(10);
        checked_iterator<Container::iterator> it = checked_begin(v);
        std::advance(it, 6);
        std::cout << *it << '\n';
        std::advance(it, 4);
        std::cout << *it << '\n';
        const Container& r = v;
        checked_iterator<Container::const_iterator> cit = checked_begin(r);
        std::advance(cit, 11);
    }
    catch (const std::exception& e) {
        std::cout << e.what() << '\n';
    }
}

至于实现一个safe_advance函数，这也可以区分随机访问迭代器和其他迭代器，例如std::advance出于效率原因：

#include <iterator>
#include <stdexcept>

namespace detail
{
    template <class Iter>
    void safe_advance_aux(
        Iter& it, Iter end, 
        typename std::iterator_traits<Iter>::difference_type n, 
        std::random_access_iterator_tag
        )
    {
        if (end - it < n) throw std::range_error("advance beyond end (ra)");
        it += n;
    }

    template <class Iter, class Tag>
    void safe_advance_aux(
        Iter& it, Iter end, 
        typename std::iterator_traits<Iter>::difference_type n, 
        Tag
        )
    {
        for (typename std::iterator_traits<Iter>::difference_type i = 0; i != n; ++i) {
            if (it == end) throw std::range_error("advance beyond end");
            ++it;
        }
    }
}

template <class Iter>
void safe_advance(Iter& it, Iter end, typename std::iterator_traits<Iter>::difference_type n)
{
    detail::safe_advance_aux(it, end, n, typename std::iterator_traits<Iter>::iterator_category());
}
于 2010-10-05T10:22:15.070 回答
2

我认为你在这里试图解决错误的问题。

不要advance以可能导致过去的方式使用end。当你当前的迭代器指向结束时，你永远不会使用增量（一种特殊形式的提前），所以同样你不应该使用提前，除非你的代码已经知道容器中有足够的剩余元素。如果您不确定，您需要一次增加一个并检查每个项目的结束。advance不会（也不能）为您做任何检查，因为这会对不需要该功能的代码造成性能影响。

相反，检查您的代码并找出为什么调用advance会导致它从容器的末尾运行，并用您的代码解决该问题。

更多的上下文可能会给我们提供更好的帮助机会。

于 2010-10-04T15:25:13.657 回答