Как убедиться, что итераторы не перекрывают end()?

Я использовал 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

Ответ 1

advance() last end() приводит к поведению undefined. Вы должны будете протестировать, как вы идете по этому фрагменту:

  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().

Ответ 2

Неэффективно вызывать distance или advance не что иное, как модели RandomAccessIterator: вызовы O (n), где n обозначает расстояние.

Кроме того, list не является действительно моделью Sequence, поскольку ее метод size не гарантированно является постоянным (или даже амортизированным постоянным), действительно, вполне может быть O (n).

Глядя на код (и если вы не можете использовать что-либо еще, кроме list), то есть две возможности:

Не используйте заранее, перемещайте по одному элементу за раз и проверяйте с помощью end на каждом шаге.
Вычислить размер раз и навсегда в начале, тогда вы знаете, сколько вы можете продвинуть, прежде чем вызывать поведение undefined (вы можете держать счетчик сбоку, обернуть итератор и т.д.).

Действуйте на этом:

// 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;

Довольно утомительно держать этот счет, хотя...

EDIT:

Обращаясь к Дэвиду с обоснованными соображениями для обобщения решений:

// 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) с такими.

Ответ 3

Расстояние не может сделать это. Когда ваш контейнер не предлагает произвольный доступ, он пытается достичь цели, продвигая старт, что может привести к хаосу, когда запуск наступил последним.

Вам нужно начинать с действительной начальной точки (т.е. путем продвижения вперед вы можете достичь последнего) и проверять расстояние до каждого хода и только продвигаться на X <= (расстояние (первое, последнее), чтобы не догонять последний.

Ответ 4

Это просто. Чтобы избежать выхода за пределы .end(), просто избегайте выхода за пределы .end(). Ситуация ничем не отличается от того, как избегать использования указателя NULL и т.д. Структурируйте свой код так, чтобы он никогда не происходил. Например. которые используют такие условия, как it != v.end() и т.д. Некоторые популярные стандартные реализации библиотек обнаруживают эти ошибки и сообщают вам, но вы не должны полагаться на них, используйте его только во время тестирования/отладки.

UPDATE

Если вы не можете быть уверены, что можете advance() на сумму больше единицы, то вы просто не должны advance() более чем на один.

Ответ 5

Я думаю, вы пытаетесь решить неправильную проблему здесь.

Не используйте advance таким образом, чтобы в прошлое end. Вы никогда не будете использовать приращение (специальную форму продвижения), когда ваш текущий итератор укажет на конец, так что вы никогда не должны использовать продвижение, если ваш код уже не знает, что в контейнере осталось достаточно оставшихся элементов. Если вы не уверены, вам нужно увеличивать один за раз и проверять на конец каждого элемента. advance не выполняет (и не может) делать какие-либо проверки для вас, так как это будет удар производительности для кода, который не нуждается в этой функции.

Вместо этого просмотрите свой код и выясните, почему вызов advance может привести к его запуску с конца вашего контейнера и исправить эту проблему с вашим кодом.

Немного больше контекста может дать нам больше шансов помочь.

Ответ 6

С одной стороны, вы также можете написать оболочку итератора, которая хранит конечный итератор и проверяет критические операции.

Например, с помощью boost iterator_facade для краткости и не проверяя наличие недочетов.

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