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

Ответ 1

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

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

Примеры:

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

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

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

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

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

Ответ 2

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

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

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

Проверка версий libС++ и libstdС++ показывает, что они также безопасны.

Ответ 3

Стандарт гарантирует, что даже ваш первый пример будет безопасным. Цитирование С++ 11

[sequence.reqmts]

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

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

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

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

Ответ 4

Не очевидно, что первый пример безопасен, потому что простейшей реализацией 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
                    ...
        }
    }

Ответ 5

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

libС++ std::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.
}

Ответ 6

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

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

из раздела 17.6.5.9

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

Ответ 7

Это абсолютно безопасно.

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

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

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

Вектор несет ответственность за этот материал, а не за вас.

Ответ 8

Оба безопасны, поскольку 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] и, как таковая, нарушит спецификации.

Ответ 9

Из 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(), то он гарантированно работает, в противном случае гарантируется поведение undefined.