Здравствуйте, Caracrist, Вы писали:
C>is subj. UB?
Почему? operator[] возвращает ссылку, дальше имеем обычную историю с forwarding reference (reference collapsing, это все) в результате получаем emplace_back(T& )
Здравствуйте, andyp, Вы писали:
C>>is subj. UB? A>Почему? operator[] возвращает ссылку, дальше имеем обычную историю с forwarding reference (reference collapsing, это все) в результате получаем emplace_back(T& )
Потому что, если случится переаллокация, то в конструктор объекта может прийти дохлая ссылка, если только в реализации вектора не создается промежуточная копия. Но рассчитывать на это не стоит:
23.3.6.5 vector modifiers
Remarks: Causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid. If an exception is thrown other than by the copy constructor, move constructor, assignment operator, or move assignment operator of T or by any InputIterator operation there are no effects. If an exception is thrown while inserting a single element at the end and T is CopyInsertable or is_nothrow_move_constructible<T>::value is true, there are no effects. Otherwise, if an exception is thrown by the move constructor of a non-CopyInsertable T, the effects are unspecified.
--
Справедливость выше закона. А человечность выше справедливости.
Здравствуйте, rg45, Вы писали:
R>Здравствуйте, andyp, Вы писали:
C>>>is subj. UB? A>>Почему? operator[] возвращает ссылку, дальше имеем обычную историю с forwarding reference (reference collapsing, это все) в результате получаем emplace_back(T& )
R>Потому что, если случится переаллокация, то в конструктор объекта может прийти дохлая ссылка, если только в реализации вектора не создается промежуточная копия. Но рассчитывать на это не стоит: R>
R>23.3.6.5 vector modifiers
R>Remarks: Causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid. If an exception is thrown other than by the copy constructor, move constructor, assignment operator, or move assignment operator of T or by any InputIterator operation there are no effects. If an exception is thrown while inserting a single element at the end and T is CopyInsertable or is_nothrow_move_constructible<T>::value is true, there are no effects. Otherwise, if an exception is thrown by the move constructor of a non-CopyInsertable T, the effects are unspecified.
Здравствуйте, rg45, Вы писали:
R>Потому что, если случится переаллокация, то в конструктор объекта может прийти дохлая ссылка, если только в реализации вектора не создается промежуточная копия. Но рассчитывать на это не стоит:
Здравствуйте, MT-Wizard, Вы писали:
MW>Не UB, можно всё что явно не запрещено...
Согласно стандарту, все как раз наоборот:
1.3.24 undefined behavior
behavior for which this International Standard imposes no requirements
Как должна повести себя программа в случае переаллокации, никаких требований нет. И будет переаллокация или нет, тоже не известно. Так что UB в чистом виде, если не зарезервировать достаточный объем памяти заранее.
Ради интереса, попробуй выполнить этот пример в Visual Studio (в отладочной конфигурации assert вылетает на первой же итерации):
Здравствуйте, MT-Wizard, Вы писали:
MW>Не UB, можно всё что явно не запрещено. STL рассказывал это где-то, но не могу найти именно ту статью; зато есть косвенное подтверждение тут:
вопрос невнятно сформулирован
если речь о доступе к нулевому элементу пустого вектора, то это UB
если речь об алиасинге, то есть вставляемый элемент уже где-то в векторе есть, то это не UB, но у VS есть\были баги в этом месте
ТС, дай внятный кусок кода, лучше в онлайн компиляторе
Despite appearances, iterator invalidation doesn't prohibit this — when you call push_back(), the value is valid, so the implementation has to ensure that if it triggers a reallocation, it doesn't accidentally invalidate the element.
Это звучит резонно.
Я вижу, название принципа "nothing prohibits it" взято в кавычки в сообщении по ссылке. Это наводит на мысль, что где-то в природе существует отдельное описание этого принципа. Интересно было бы увидеть.
--
Справедливость выше закона. А человечность выше справедливости.
Здравствуйте, rg45, Вы писали:
R>Это звучит резонно.
R>Я вижу, название принципа "nothing prohibits it" взято в кавычки в сообщении по ссылке. Это наводит на мысль, что где-то в природе существует отдельное описание этого принципа. Интересно было бы увидеть.
Я так рассуждаю:
для методов вектора (да и всех контейнеров) стандарт определяет несколько важных вещей:
(список с потолка)
это, по сути, декларация контракта.
Так вот для метода emplace_back (и многих других) не описано никаких ограничений. В том числе не написано "вот это не передавайте, иначе UB". Я это понимаю, как при "ненарушении" других правил языка (то есть где-то ранее не допущен UB) и при передаче некоторого валидного значения в emplace_back реализация STL соблюдет контракт и выполнит post-condtion и всю задекларированную логику.
Короче, если не нарушил pre-conditions, то все должно работать, даже если вставляемый элемент указывает внутрь контейнера (т.к. оговорок по этому поводу в стандарте нет).
Здравствуйте, uzhas, Вы писали:
U>Так вот для метода emplace_back (и многих других) не описано никаких ограничений. В том числе не написано "вот это не передавайте, иначе UB". Я это понимаю, как при "ненарушении" других правил языка (то есть где-то ранее не допущен UB) и при передаче некоторого валидного значения в emplace_back реализация STL соблюдет контракт и выполнит post-condtion и всю задекларированную логику. U>Короче, если не нарушил pre-conditions, то все должно работать, даже если вставляемый элемент указывает внутрь контейнера (т.к. оговорок по этому поводу в стандарте нет).
Да согласен. Но, с практической точки зрения, это означает, что разработчики стандартной бибилиотеки должны иметь в виду, что любой из фактических параметров, переданных в emplace_back, может ссылаться (прямо или косвенно) на какой-нибудь из существующих элементов контейнера и всегда поддрерживать время жизни всех элементов до окончания операции. Не будет ли это ударом по оптимизации?
--
Справедливость выше закона. А человечность выше справедливости.
Здравствуйте, uzhas, Вы писали:
R>>Не будет ли это ударом по оптимизации?
U>Будет. Так же как и поддержка гарантий exception-safety. U>Ну а что поделать? (риторически вздохнул)
А как же тогда другой принцип — "не платить за то, что не используешь"?
--
Справедливость выше закона. А человечность выше справедливости.
Здравствуйте, rg45, Вы писали:
R>А как же тогда другой принцип — "не платить за то, что не используешь"?
ну это же лукавство, не правда ли?
возьми small string optimization в std::string — оно всем надо, думаешь? кому-то и эти 16 байт жалко тратить
или тот же exception safety
стараются сделать как можно гибче и тоньше, исходя из принципа, однако идеально не получится
да и не надо это. лучше иметь крепкий фундамент для своего софта, над ним как раз стандартизаторы и работают имхо
лазейка всегда есть : не хочешь платить — не используй std::vector
Здравствуйте, uzhas, Вы писали:
U>Так вот для метода emplace_back (и многих других) не описано никаких ограничений. В том числе не написано "вот это не передавайте, иначе UB". Я это понимаю, как при "ненарушении" других правил языка (то есть где-то ранее не допущен UB) и при передаче некоторого валидного значения в emplace_back реализация STL соблюдет контракт и выполнит post-condtion и всю задекларированную логику.
U>Короче, если не нарушил pre-conditions, то все должно работать, даже если вставляемый элемент указывает внутрь контейнера (т.к. оговорок по этому поводу в стандарте нет).
Это минорный дефект стандарта. Ведь знали же, что у программистов руки шаловливые, а забыли оговорить время жизни ссылки, передаваемой внутрь методов вектора.
Сказано явно лишь то, что во время выполнения этих методов все указатели и ссылки могут быть инвалидированы. Когда именно они инвалидируются, — не сказано.
Почему бы не предположить, что ссылка инвалидируется мгновенно при входе внутрь функции, просто потому, что реализация имеет право так сделать?
Ну и здравый смысл подсказывает, что конструктор с аргументом v.front() выполняется после reserve(size()+1), то есть, после инвалидации ссылок.
Конечно, мы можем написать код, который будет устойчив к таким проблемам
struct Robust {
Robust(int, int, int) { ..... }
Robust(const Robust&) {} // ничего не копирует
. . .
};
vector<Robust> v;
v.emplace_back(1,2,3);
Robust& r = v.front();
v.emplace_back(r);
// r инвалидировано, да и плевать - если мы его не будем использовать
но в общем случае — передача в конструктор копирования инвалидной ссылки приведёт к UB.
Здравствуйте, Кодт, Вы писали:
К>Нужно ли было всё это расписывать?
Хотя...
Есть способ корректной реализации.
1. Размещаем новый массив
2. Конструируем там новый элемент (все ссылки ещё валидны, все элементы ещё нетронуты)
3. Конструируем там move/copy все остальные элементы
4. Разрушаем элементы в старом массиве
5. Удаляем старый массив
Здравствуйте, Кодт, Вы писали:
К>Хотя... К>Есть способ корректной реализации.
К>1. Размещаем новый массив К>2. Конструируем там новый элемент (все ссылки ещё валидны, все элементы ещё нетронуты) К>3. Конструируем там move/copy все остальные элементы К>4. Разрушаем элементы в старом массиве К>5. Удаляем старый массив
Да и особого оверхеда не видно, вроде бы.
--
Справедливость выше закона. А человечность выше справедливости.
Здравствуйте, rg45, Вы писали:
R>Да и особого оверхеда не видно, вроде бы.
кстати, глянул тут потроха студийные: при push_back делается reserve, но при исключении во время покладания ничего не откатывается, в том числе capacity
как следствие, формальное нарушение правила: в случае исключения push_back has no effect
1. Если вектор пуст, то UB, т.к. вызов v[0] в случае пустоты имеет право убица апстену.
2. Если вектор не пуст, то сначала возьмём константную ссылку на v[0] (адрес памяти), потом вызовем emplace_back(), что может привести к переезду памяти с освобождением старого куска, куда показывает взятый указатель на v[0] (ссылка) и тогда при последующем старте конструирования нового emplaced-объекта получим тоже UB по причине чтения из ссылки (указателя) уже ведущей вникуда.
Короче, да, это UB.
Всякие там советы "не делай так" — тупые, ибо не содержат аргументов.
R>Despite appearances, iterator invalidation doesn't prohibit this — when you call push_back(), the value is valid, so the implementation has to ensure that if it triggers a reallocation, it doesn't accidentally invalidate the element.
R>Это звучит резонно.
R>Я вижу, название принципа "nothing prohibits it" взято в кавычки в сообщении по ссылке. Это наводит на мысль, что где-то в природе существует отдельное описание этого принципа. Интересно было бы увидеть.
Это просто следствие непонимания некоторыми стандартизаторами принципов составления строгих формальных описаний. Неспособность родить ясное и непротиворечивое формальное описание приводит к тому, что под фактическим набором правил языка стандартизаторами подразумется не собственно то, что сказано в стандарте прямым текстом, а некая интерпретация (порой довольно неочевидная) стандарта этими самыми стандартизаторами.
Формально поведение можно считать определённым тогда и только тогда, когда существует набор правил, описывающий какое именно поведение дожно иметь место. Единственное допустимое применение принципа "nothing prohibits it" — это установление факта, что в рассматриваемом случае поведение действительно определено неким существующим набором правил, поскольку данный случай соответствует общим условиям этих правил и не соответвует каким-либо специальным условиям (исключительным случаям), которые могли бы сделать данный набор правил неприменимым к данному случаю.
Что касается v.emplace_back(v[0]), то стандарт не определяет порядок noexcept инициализации нового объекта и инвалидации v[0] в случае реаллокации. А это значит, что теоретически допустима conforming реализация, которая бы делала v[0] невалидным до конструирования вставляемого объекта, и тогда "nothing prohibits it" звучит довольно смешно, т.к. наличие undefined behavior следует собственно из описания (довольно кривого, кстати) семантики операции вставки.
Если инициализация вставляемого объекта потенциально может бросать исключение, то у реализации не остаётся выбора, кроме как сначала пытаться его конструировать, а потом уже заниматься удалением исходной последовательности, потому что в случае выброса исключения стандарт требует сохранения прежнего состояния вектора. Если реализация использует один и тот же код для потенциально бросающей и небросающей инициализации, то, скорее всего, v.emplace_back(v[0]) будет работать "корректно".
Подытожим:
1. Для непустого вектора v при v.size() == v.capacity() вычисление v.emplace_back(v[0]) формально может привести к undefined behavior за счёт инвалидации v[0].
2. Стандатизаторы одновременно не признают такую возможность и не признают наличие дефекта в стандарте, потому что они упоротые. Когда правила вменяемо сформулированы, споров вокруг их правильной трактовки не должно возникать в принципе. Если бы в сообществе математиков теоремы формулировались и доказывались с таким же отношением к формальной логике, мы бы сейчас не имели ничего сложнее доказательства теоремы Пифагора (да и там бы, наверное, не обошлось без ошибок и дефект-репортов).
3. Существует реализация std::vector (MSVC), для которой проблема "некорректного" вычисления v.emplace_back(v[0]) действительно имеет место.
Здравствуйте, N. I., Вы писали:
NI>Это просто следствие непонимания некоторыми стандартизаторами принципов составления строгих формальных описаний.
Со строгостью и понятностью в стандарте плоховато. Могли бы в каждой новой версии вводить хотя бы "очевидные" для стандартизаторов (но неочевидные остальным) пояснения\уточнения. То же разыменование нулевого указателя (вспомним недавнее длинное обсуждение) вызывает массу вопросов когда это UB, а когда — нет.
NI>Что касается v.emplace_back(v[0]), то стандарт не определяет порядок noexcept инициализации нового объекта и инвалидации v[0] в случае реаллокации. А это значит, что теоретически допустима conforming реализация, которая бы делала v[0] невалидным до конструирования вставляемого объекта
Порядок не обязательно определять. Есть требование к std::vector (и emplace_back и реаллокация под его контролем) выполнить контракт (в каком порядке и что он будет делать — его забота). Не вижу тут возможности для conforming реализации допустить UB.
uzhas:
U>Есть требование к std::vector (и emplace_back и реаллокация под его контролем) выполнить контракт (в каком порядке и что он будет делать — его забота).
Что именно emplace_back должна выполнить? Operational semantics у emplace_back следующая:
Appends an object of type T constructed with std::forward<Args>(args)...
Вот, есть у нас, например, такой код:
#include <vector>
int main()
{
std::vector<int> v;
int i;
v.emplace_back(i);
}
Попытка создать an object of type int constructed with std::forward<int &>(i) не cможет обойтись без вычисления lvalue-to-rvalue conversion над std::forward<int &>(i), а в соответствии с правилами С++17 [conv.lval]/3 и [dcl.init]/12 такое вычисление имеет своим результатом indeterminate value и ведёт к undefined behavior. Таким образом, в данном случае прямое выполнение operational semantics метода emplace_back подразумевает возникновение undefined behavior. Нарушили мы при этом какие-то коряво сформулированные куцые "предусловия" emplace_back или нет, тут особой роли не играет, — появление undefined behavior неминуемо по-любому.
Перекуём баги на фичи!
