Работает ли std::copy_n с перекрывающимися диапазонами?

Я искал в стандарте С++ N3485 25.3.1 [alg.copy], который определяет 4 алгоритма:

  • copy
  • copy_backward
  • copy_if
  • copy_n

В описании copy есть примечание 25.3.1 [alg.copy]/3:

Требуется: результат не должен быть в диапазоне [first,last)

То есть copy не всегда корректно работает при перекрытии диапазонов (аналогично memcpy).

copy_backward и copy_if имеют похожий язык, запрещающий перекрывающиеся диапазоны (25.3.1 [alg.copy]/14 и 25.3.1 [alg.copy]/8 соответственно).

Однако для copy_n такого запрета нет, как и для copy_n_backward. Означает ли это, что copy_n поступает правильно, когда диапазоны перекрываются?

(Реализация copy_n в MSVC++, по-видимому, делегирует std::memmove, поэтому я знаю, что здесь, в MSVC++ 2013, это безопасно. Но я не хочу полагаться на это, если стандарт подразумевает иное)


c++ algorithm stl stl-algorithm
person Billy ONeal    schedule 23.12.2013    source источник
comment
Реализация copy_n в MSVC++, по-видимому, делегирует std::memmove. Обратите внимание, что мы делаем это только в том случае, если такое преобразование правильно; то есть, где итераторы являются указателями на легко копируемые объекты.   -  person James McNellis    schedule 23.12.2013
comment
@Джеймс: Конечно. :) В таком случае бывает, что это безопасная трансформация.   -  person Billy ONeal    schedule 23.12.2013
comment
@James: А, я понимаю твою точку зрения. Если входы были, например. std::list, это было бы небезопасно для реализации MSVC++. Звучит как ответ мне...   -  person Billy ONeal    schedule 23.12.2013
comment
Ничего себе, это странный пограничный случай, я хочу сказать, что это, вероятно, ошибка (они хотели, чтобы это был UB), но кажется, что это почти намеренно упущено...   -  person user541686    schedule 23.12.2013
comment
В исходной реализации SGI действительно было такое требование для copy_n. Не понимаю, почему этого нет в стандарте. Вы можете отправить вопрос. Кстати, copy запрещает перекрытие только в том случае, если вывод начинается во входном диапазоне, но работает нормально, когда выходной диапазон заканчивается во входном диапазоне (т. е. копирование влево).   -  person TemplateRex    schedule 04.01.2014

Ответы (2)


arrow_upward
3
arrow_downward

Это безопасно*. Почему? Потому что стандарт не говорит, что это небезопасно. Они копируют функции из 25.3.1 и имеют Требования: для вещей, которые им требуются (именно здесь указывается перекрывающийся запрет в других формах копирования).

Однако copy_n не говорит, что требует, чтобы диапазоны не перекрывались, что означает, что это нормально, так как это не запрещено явно. Если бы это требовалось, оно бы заявило об этом.

*Редактировать: Когда я имел в виду «безопасный», я имел в виду, что это не неопределенное поведение или неправильно сформированная программа. Однако не гарантируется, что результаты будут такими, как вы, вероятно, предполагали, если диапазоны памяти перекрываются. Единственное, что мы гарантируем, это:

  1. Для каждого неотрицательного целого числа i < n, *(result + i) = *(first + i) выполняется
  2. Вызов функции с перекрывающимися диапазонами не запрещен и не приводит к неопределенному поведению.

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

Итак, если под «безопасным» вы подразумеваете, что пункт назначения всегда имеет точную копию источника (например, memmove), то нет, это не «безопасно». Но это безопасно в том смысле, что само по себе не вызовет неопределенного/недопустимого поведения.

Напомним, что мы гарантируем, что *(result + i) = *(first + i) будет выполнено для каждого элемента во всем диапазоне. Мы гарантируем, что если диапазоны перекрываются, программа все равно не является неопределенной. Нам не гарантируется порядок, в котором копируются элементы. Мы не гарантируем, что если диапазоны перекрываются, какими будут точные значения, хранящиеся в результате (но мы знаем, что все они получены из источника).

person Cornstalks    schedule 23.12.2013
comment
Как copy_n выполняет проверку безопасности, когда итераторы не поддерживают произвольный доступ? (Для этого требуется только итератор ввода и итератор вывода....) - person Billy ONeal; 23.12.2013
comment
@Billy cplusplus.com говорит If the ranges overlap, some of the elements in the range pointed by result may have undefined but valid values. Но я не знаю, насколько это надежно. - person ; 23.12.2013
comment
@remyabel: cplusplus.com == чертовски ненадежен. :) - person Billy ONeal; 23.12.2013
comment
@BillyONeal: Обновлено. Извините, я изначально имел в виду безопасный не так, как вы, вероятно, его использовали. - person Cornstalks; 23.12.2013
comment
Таким образом, передача перекрывающихся диапазонов разрешена, но на самом деле это приводит к непредсказуемым результатам и, следовательно, бесполезна во всех мыслимых случаях? Какая странная спец. Почему бы не относиться к этому так же, как и к другим функциям copy? Что они могли подумать? (Я согласен, что это то, о чем говорит спецификация, так что +1. Но как странно.) - person Nemo; 23.12.2013
comment
@Nemo: я согласен, что это странно. Я бы хотел, чтобы они либо запретили это, либо, по крайней мере, прямо сказали, что вы можете это сделать, но вы можете получить мусор обратно. - person Cornstalks; 23.12.2013

arrow_upward
1
arrow_downward

Я согласен с ответом Cornstalks и +1 к нему. Но теория должна быть подкреплена практикой.

Беглый взгляд на реализации GCC (libstdc++-v3) и Clang (libc++) показывает, что их copy_n совпадает с (или делегирует) copy, без поддержки перекрытия при перемещении объектов по более высоким адресам.

Таким образом, MSVC выигрывает этот раунд, по крайней мере, в случае POD, который делегирует memmove.

person Potatoswatter    schedule 23.12.2013