Безопасно ли возвращать элемент из того же вектора?

126
vector<int> v;
v.push_back(1);
v.push_back(v[0]);

Если второй push_back вызывает перераспределение, ссылка на первое целое число в векторе больше не будет действительной. Так это небезопасно?

vector<int> v;
v.push_back(1);
v.reserve(v.size() + 1);
v.push_back(v[0]);

Это делает его безопасным?

Нил Кирк
источник
4
Примечание: в настоящее время на форуме стандартных предложений идет обсуждение. В рамках этого кто-то привел пример реализацииpush_back . Другой автор заметил в нем ошибку , которая не соответствовала описанному вами случаю. Насколько я могу судить, никто другой не утверждал, что это не ошибка. Не говорю, что это неопровержимое доказательство, просто наблюдение.
Бенджамин Линдли
9
Мне очень жаль, но я не знаю, какой ответ принять, поскольку по поводу правильного ответа все еще существуют разногласия.
Нил Кирк
4
Меня попросили прокомментировать этот вопрос в пятом комментарии в разделе: stackoverflow.com/a/18647445/576911 . Я делаю это, поддерживая каждый ответ, который в настоящее время говорит: да, push_back элемент из того же вектора безопасно.
Ховард Хиннант,
2
@BenVoigt: <shrug> Если вы не согласны с тем, что говорится в стандарте, или даже если вы согласны со стандартом, но не думаете, что он говорит об этом достаточно четко, это всегда вариант для вас: cplusplus.github.io/LWG/ lwg-active.html # submit_issue Я сам использовал эту опцию больше раз, чем могу вспомнить. Иногда успешно, иногда нет. Если вы хотите обсудить, что говорится в стандарте или что в нем говорится, SO не является эффективным форумом. Наш разговор не имеет нормативного значения. Но вы можете иметь шанс на нормативное воздействие, перейдя по ссылке выше.
Ховард Хиннант
2
@ Polaris878 Если push_back приводит к тому, что вектор достигает своей емкости, вектор выделяет новый больший буфер, копирует старые данные, а затем удаляет старый буфер. Затем он вставит новый элемент. Проблема в том, что новый элемент - это ссылка на данные в старом буфере, который был только что удален. Если push_back не сделает копию значения перед удалением, это будет плохая ссылка.
Нил Кирк

Ответы:

31

Похоже, http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#526 решает эту проблему (или что-то очень похожее на нее) как потенциальный дефект в стандарте:

1) Параметры, взятые по константной ссылке, могут быть изменены во время выполнения функции

Примеры:

Учитывая std :: vector v:

v.insert (v.begin (), v [2]);

v [2] можно изменить, перемещая элементы вектора

Предлагаемое решение заключалось в том, что это не было дефектом:

vector :: insert (iter, value) требуется для работы, потому что стандарт не дает разрешения, чтобы он не работал.

Нейт Коль
источник
Я нахожу разрешение в 17.6.4.9: «Если аргумент функции имеет недопустимое значение (например, значение вне домена функции или указатель, недопустимый для предполагаемого использования), поведение не определено». Если происходит перераспределение, все итераторы и ссылки на элементы становятся недействительными, что означает, что ссылка на параметр, переданная функции, также недействительна.
Ben Voigt
4
Я думаю, дело в том, что реализация отвечает за перераспределение. Он обязан гарантировать, что поведение определено, если вход определен изначально. Поскольку в спецификациях четко указано, что push_back делает копию, реализации должны, возможно, за счет времени выполнения кэшировать или копировать все значения перед освобождением от распределения. Поскольку в этом конкретном вопросе не осталось внешних ссылок, не имеет значения, являются ли итераторы и ссылки недействительными.
OlivierD
3
@NeilKirk Я думаю, это должен быть авторский ответ, он также упоминается Стефаном Т. Лававей на Reddit, используя, по сути, те же аргументы.
TemplateRex
v.insert(v.begin(), v[2]);не может вызвать перераспределение. Так как же это ответить на вопрос?
ThomasMcLeod 03
@ThomasMcLeod: да, это, очевидно, может вызвать перераспределение. Вы увеличиваете размер вектора, вставляя новый элемент.
Violet Giraffe
21

Да, это безопасно, и реализации стандартных библиотек прыгают через препятствия, чтобы сделать это так.

Я считаю, что разработчики каким-то образом прослеживают это требование до 23.2 / 11, но я не могу понять, как это сделать, и не могу найти чего-то более конкретного. Лучшее, что я могу найти, - это эта статья:

http://www.drdobbs.com/cpp/copying-container-elements-from-the-c-li/240155771

Проверка реализаций libc ++ и libstdc ++ показывает, что они также безопасны.

Себастьян Редл
источник
9
Некоторая поддержка здесь действительно поможет.
Крис
3
Это интересно, я должен признать, что никогда не рассматривал этот случай, но на самом деле это кажется довольно трудным. Это также относится к vec.insert(vec.end(), vec.begin(), vec.end());?
Matthieu M.
2
@MatthieuM. Нет. В таблице 100 сказано: «pre: i и j не являются итераторами в a».
Себастьян Редл,
2
Я сейчас голосую, так как это тоже мое воспоминание, но нужна ссылка.
bames53
3
Имеет 23,2 / 11 в версии, которую вы используете "Если не указано иное (явно или путем определения функции в терминах других функций), вызов функции-члена контейнера или передача контейнера в качестве аргумента библиотечной функции не должны аннулировать итераторы. для или изменения значений объектов в этом контейнере ". ? Но vector.push_backДОЛЖЕН указать иное. «Вызывает перераспределение, если новый размер больше старого». и (at reserve) «Перераспределение делает недействительными все ссылки, указатели и итераторы, относящиеся к элементам в последовательности».
Ben Voigt
13

Стандарт гарантирует безопасность даже первого примера. Цитирование C ++ 11

[sequence.reqmts]

3 В таблицах 100 и 101 ... Xобозначает класс контейнера последовательности, aобозначает значение, Xсодержащее элементы типа T, ... tобозначает lvalue или const rvalue дляX::value_type

16 Таблица 101 ...

Выражение a.push_back(t) Тип возвращаемого значения void Операционная семантика Добавляет копию Requires t. : T должно быть CopyInsertableв X. Контейнер basic_string , deque, list,vector

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

Энгью больше не гордится SO
источник
7
Я не понимаю, как это гарантирует безопасность.
jrok
4
@Angew: Это абсолютно недействительно t, вопрос только в том, до или после создания копии. Ваше последнее предложение определенно неверно.
Ben Voigt
4
@BenVoigt Поскольку tсоответствует перечисленным условиям, описанное поведение гарантировано. Реализации не разрешается аннулировать предварительное условие, а затем использовать его как предлог для несоблюдения указанного.
bames53
8
@BenVoigt Клиент не обязан поддерживать предварительное условие на протяжении всего вызова; только для того, чтобы гарантировать его выполнение при инициировании вызова.
bames53
6
@BenVoigt Это хороший аргумент, но я считаю, что переданный функтор for_eachне должен аннулировать итераторы. Я не могу найти ссылку для for_each, но я вижу в некоторых алгоритмах текст вроде «op и binary_op не должны аннулировать итераторы или поддиапазоны».
bames53
7

Не очевидно, что первый пример безопасен, потому что простейшей реализацией push_backбыло бы сначала перераспределить вектор, если необходимо, а затем скопировать ссылку.

Но, по крайней мере, это кажется безопасным с Visual Studio 2010. Его реализация push_backвыполняет особую обработку случая, когда вы возвращаете элемент в векторе. Код имеет следующую структуру:

void push_back(const _Ty& _Val)
    {   // insert element at end
    if (_Inside(_STD addressof(_Val)))
        {   // push back an element
                    ...
        }
    else
        {   // push back a non-element
                    ...
        }
    }
Йохан Роде
источник
8
Я хотел бы знать, требует ли спецификация этого, чтобы это было безопасно.
Nawaz
1
Согласно Стандарту это не обязательно. Однако возможно реализовать его безопасным способом.
Ben Voigt
2
@BenVoigt Я бы сказал, что это необходимо для безопасности (см. Мой ответ).
Энгью больше не гордится SO
2
@BenVoigt На момент передачи ссылки она действительна.
Энгью больше не гордится SO
4
@Angew: Этого недостаточно. Вам необходимо передать ссылку, которая остается действительной на время звонка, а эта - нет.
Ben Voigt
3

Это не гарантия стандарта, но, как еще одна точка данных, v.push_back(v[0])безопасна для библиотеки LLVM libc ++ .

Libc ++ Sstd::vector::push_back вызовы , __push_back_slow_pathкогда ему необходимо перераспределить память:

void __push_back_slow_path(_Up& __x) {
  allocator_type& __a = this->__alloc();
  __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), 
                                                  size(), 
                                                  __a);
  // Note that we construct a copy of __x before deallocating
  // the existing storage or moving existing elements.
  __alloc_traits::construct(__a, 
                            _VSTD::__to_raw_pointer(__v.__end_), 
                            _VSTD::forward<_Up>(__x));
  __v.__end_++;
  // Moving existing elements happens here:
  __swap_out_circular_buffer(__v);
  // When __v goes out of scope, __x will be invalid.
}
Нейт Коль
источник
Копия должна быть сделана не только перед освобождением существующего хранилища, но и перед перемещением из существующих элементов. Я полагаю, что перемещение существующих элементов выполнено __swap_out_circular_buffer, и в этом случае эта реализация действительно безопасна.
Ben Voigt
@BenVoigt: хорошая мысль, и вы действительно правы, что движение происходит внутри __swap_out_circular_buffer. (Я добавил несколько комментариев, чтобы отметить это.)
Nate Kohl
1

Первая версия определенно НЕ безопасна:

Операции с итераторами, полученные путем вызова контейнера стандартной библиотеки или строковой функции-члена, могут обращаться к базовому контейнеру, но не должны его изменять. [Примечание: В частности, операции контейнера, которые делают итераторы недействительными, конфликтуют с операциями над итераторами, связанными с этим контейнером. - конец примечания]

из раздела 17.6.5.9


Обратите внимание, что это раздел о гонках данных, который люди обычно думают в связи с потоковой передачей ... но фактическое определение включает отношения «происходит раньше», и я не вижу какой-либо упорядочивающей взаимосвязи между несколькими побочными эффектами push_backin play здесь, а именно, признание недействительности ссылки, похоже, не определяется как упорядоченное в отношении создания копии нового хвостового элемента.

Бен Фойгт
источник
1
Следует понимать, что это примечание, а не правило, поэтому оно объясняет последствия вышеизложенного правила ... и последствия идентичны для ссылок.
Бен Фойгт,
5
Результат v[0]не является итератором, аналогично push_back()не принимает итератор. Итак, с точки зрения языкового юриста, ваш аргумент недействителен. Сожалею. Я знаю, что большинство итераторов являются указателями, и цель признания итератора недействительной почти такая же, как и для ссылок, но та часть стандарта, которую вы цитируете, не имеет отношения к данной ситуации.
cmaster - восстановить Монику
-1. Это совершенно неуместная цитата, и она все равно на нее не отвечает. Комитет говорит, что x.push_back(x[0])это БЕЗОПАСНО.
Nawaz
0

Это совершенно безопасно.

Во втором примере у вас есть

v.reserve(v.size() + 1);

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

За это отвечает Vector, а не вы.

Zaffy
источник
-1

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

Раздел 23.2.1 Общие требования к контейнерам

16
  • a.push_back (t) Добавляет копию t. Требуется: T должен быть CopyInsertable в X.
  • a.push_back (rv) Добавляет копию rv. Требуется: T должен быть MoveInsertable в X.

Поэтому реализации push_back должны гарантировать, что вставлена копия v[0] . В противоположном примере, если предположить, что реализация будет перераспределяться перед копированием, она не обязательно добавит копию v[0]и, как таковая, нарушит спецификации.

OlivierD
источник
2
push_backоднако также изменит размер вектора, и в наивной реализации это сделает ссылку недействительной до того, как произойдет копирование. Так что, если вы не подтвердите это цитатой из стандарта, я буду считать это неправильным.
Конрад Рудольф
4
Под «этим» вы имеете в виду первый или второй пример? push_backскопирует значение в вектор; но (насколько я понимаю) это может произойти после перераспределения, и в этот момент ссылка, из которой он пытается скопировать, больше не действительна.
Майк Сеймур,
1
push_backполучает свой аргумент по ссылке .
bames53
1
@OlivierD: он должен (1) выделить новое пространство (2) скопировать новый элемент (3) переместить-построить существующие элементы (4) уничтожить перемещенные элементы (5) освободить старое хранилище - В ЭТОМ порядке - чтобы первая версия заработала.
Бен Фойгт,
1
@BenVoigt, зачем еще контейнеру требовать, чтобы тип был CopyInsertable, если он все равно полностью игнорирует это свойство?
OlivierD
-2

Начиная с 23.3.6.5/1: 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.

Поскольку мы вставляем в конце, никакие ссылки не будут признаны недействительными, если размер вектора не будет изменен. Итак, если вектор, capacity() > size()то он гарантированно работает, в противном случае гарантированно будет неопределенное поведение.

Марк Б
источник
Я считаю, что спецификация действительно гарантирует, что это будет работать в любом случае. Хотя жду ссылки.
bames53
В вопросе нет упоминания об итераторах или безопасности итераторов.
OlivierD
3
@OlivierD часть итератора здесь лишняя: меня интересует referencesчасть цитаты.
Mark B
2
На самом деле это безопасно (см. Мой ответ, семантика push_back).
Angew больше не гордится SO