Как сравнить (порядок) двух двунаправленных итераторов?

Question

Мне было интересно, есть ли встроенный в C++ способ сравнения порядка двух двунаправленных итераторов. Например, у меня есть функция Sum для вычисления суммы между двумя итераторами в одном и том же списке:

double Sum(std::list::const_iterator Start, std::list::const_iterator End){
      double sum=0;
      for (Start;Start!=End;Start++)
           sum+=*Start;
      return sum;
}

Затем:Sum(my_list.begin(),my_list.end()); хорошо, но Sum(my_list.end(),my_list.begin()); вызовет ошибку во время выполнения.

Я думал положитьif (Start>End) return 0; чтобы предотвратить ошибку. Но, похоже, я не могу сравнить итераторы, как это.

Answer 1

Вы должны прочитать Введение в STL, которое объясняет различные уточнения концепции Итератора.

Только RandomAccessIterators поддерживают сравнение с < потому что это не эффективная операция для не-RandomAccessIterators.

Единственный способ узнать, является ли BidirectionalIterator i меньше, чем другой, j, увеличивая i один шаг за раз и посмотреть, если вы когда-нибудь достигнете j, но этого никогда не произойдет, если j недоступен из iи является ошибкой, если i не может быть увеличен, например, потому что это последний итератор для диапазона.

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

Таким образом, в общем, нет никакого способа узнать, приходит ли один не-RandomAccessIterator до или после другого, потому что вы даже не можете знать, начинать ли итерацию вперед или назад, чтобы достичь другого, и вы не будете знать, когда это безопасно продолжать или когда вы достигнете конца допустимого диапазона.

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

Затем: Sum(my_list.begin(),my_list.end()); хорошо, но Sum(my_list.end(),my_list.begin()); вызовет ошибку во время выполнения.

Тогда не делай этого!

Ответственность за правильный вызов функции лежит на вызывающей стороне, и почему вызывающая сторона не знает, какой итератор является началом, а какой - концом?

Answer 2

Когда вы вызываете Sum (my_list.begin (), my_list.end ()), my_list.begin () будет указывать на первый элемент в списке

double Sum(std::list::const_iterator& Start, std::list::const_iterator& End)
{
      double sum=0;
      if (Start;Start!=End;Start++)
           sum+=*Start;
      return sum;
}

SameWay, когда вы вызываете Sum (my_list.end (), my_list.begin ()), my_list.end () будет указывать на последний элемент в списке.

Сделайте ниже изменения, это будет работать,

    double Sum(std::list<int>::const_iterator Start, std::list<int>::const_iterator End)
{
      double sum=0;
      for (Start;Start!=End;Start)
           sum+=*(--Start);
      return sum;
}