Определено ли это, чтобы обеспечить инвертированный диапазон для стандартных алгоритмов С++?

Рассмотрим стандартные алгоритмы, например, std::for_each.

template<class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f);

Насколько я могу судить, на относительные состояния двух аргументов InputIterator не существует требования.

Означает ли это, что следующее технически обосновано? Или это undefined? Что я могу реально ожидать от этого?

std::vector<int> v{0,1,2,3,4};
std::for_each(
   v.begin()+3,  // range [3,0)
   v.begin(),
   [](int){}
);

geordi говорит мне:

error: функция требует допустимого диапазона итератора [__first, __last). [+ 13 отброшенных строк]

но я не могу сказать, насколько совместима эта диагностика отладки.

Я придумал этот вопрос, пытаясь педантично определить, насколько явным определяется поведение следующего:

std::vector<int> v; // <-- empty
std::for_each(      // <-- total no-op? stated or just left to implication?
   v.begin(),
   v.end(),
   [](int){}
);

Ответы

Ответ 1

Стандарт явно требует, чтобы итератор last был доступен из итератора first. Это означает, что, увеличивая first, вы должны в конечном итоге нажать last.

24.1 Требования к итератору

...

6 Итератор j называется достижимым из итератора i тогда и только тогда, когда существует конечная последовательность применений выражения ++i, что делает i == j. Если j достижимо от i, они относятся к тому же контейнер.

7. Большинство алгоритмических шаблонов библиотеки, которые работают на структурах данных есть интерфейсы, которые используют диапазоны. Диапазон - это пара итераторов, которые обозначают начало и конец вычисления. Диапазон [i, i) - пустой диапазон; в общем случае диапазон [i, j) относится к элементы в структуре данных, начиная с той, на которую указывает i и до, но не включая тот, на который указывает j. Диапазон [i, j) равен действителен тогда и только тогда, когда j доступен из i. Результат применение функций в библиотеке к недопустимым диапазонам undefined.

Ответ 2

Результат Undefined.

С++ 03 Стандарт: 25.1.1 Для каждого и
С++ 11 Стандарт: 25.2.4 Для каждого состояния:

template<class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f);

1 Эффекты: Применяет f к результату разыменования каждого итератора в диапазоне [первый, последний], начиная от первого и до последнего - 1

В то время как другой раздел определяет допустимый диапазон [first,last) как:

С++ 03 Стандарт: 24.1 Требования к итератору и
С++ 11 Стандарт: 24.2.1 Требования к итератору

Пара 7 для обоих:

Большинство алгоритмических шаблонов библиотеки, которые работают с структурами данных, имеют интерфейсы, которые используют диапазоны. Диапазон - это пара итераторов, которые обозначают начало и конец вычисления. Диапазон [i, i) - пустой диапазон; в общем случае диапазон [i, j) относится к элементам в структуре данных, начиная с того, на который указывает i, и до, но не включая тот, на который указывает j. Диапазон [i, j) действителен тогда и только тогда, когда j доступен из i. Результатом применения функций в библиотеке к недопустимым диапазонам является Undefined.

Вспомнив прочтение этого места, просто просмотрел:

Стандартная библиотека С++ - Учебное пособие и справочник - Николас Йосутильс

Это находит упоминание в:

5.4.1 Диапазоны
Вызывающий должен убедиться, что первый и второй аргументы определяют допустимый диапазон. Это тот случай, когда конец диапазона доступен с самого начала, итерации через элементы. Это означает, что программист должен гарантировать, что оба итератора принадлежат одному и тому же контейнеру и что начало не стоит за концом. Если это не так, поведение undefined и бесконечные циклы или доступ к запрещенной памяти могут привести к.

Ответ 3

Означает ли это, что следующее технически обосновано? Или это undefined? Что я могу реально ожидать от этого?

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

Ответ 4

Это объясняется разделом 24.1 стандарта "Требования к итератору":

Итератор j называется достижимым из итератора i тогда и только тогда, когда существует конечная последовательность приложений выражения ++i, которая делает i == j. Если j доступен из i, они относятся к одному и тому же контейнеру.

...

Диапазон [i, j) действителен тогда и только тогда, когда j доступен из i. Результатом применения функций в библиотеке к недопустимым диапазонам является undefined.

Итак, v.begin() + 3 достижимо от v.begin(), но не наоборот. Таким образом, [v.begin()+3, v.begin()) не является допустимым диапазоном, а ваш вызов for_each равен undefined.

Ответ 5

Стандарт определяет ограничения сложности для функций, принимающих диапазоны. В конкретном случае for_each (25.2.4 в стандарте С++):

Сложность: применяет f ровно last - first раз

Таким образом, это эффективно no-op в вашем примере.