Определено ли это для обеспечения инвертированного диапазона в стандартных алгоритмах C ++? - PullRequest
Новая
       37

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

10 голосов
/ 21 сентября 2011

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

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

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

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

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

Джорджи говорит мне:

ошибка: функция требует допустимого диапазона итератора [__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){}
);

Ответы [ 5 ]

21 голосов
/ 21 сентября 2011

Стандарт явно требует, чтобы итератор 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. Результат применение функций в библиотеке к недопустимым диапазонам не определено.

6 голосов
/ 21 сентября 2011

Результат не определен.

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

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

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

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

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

Пункт 7 для обоих:

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

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

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

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

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

2 голосов
/ 21 сентября 2011

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

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

…

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

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

2 голосов
/ 21 сентября 2011

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

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

1 голос
/ 21 сентября 2011

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

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

Так что в вашем примере это, по сути, бездействие.

...