Czy można bezpiecznie odepchnąć element z tego samego wektora?

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

Jeśli drugie push_back spowoduje realokację, odwołanie do pierwszej liczby całkowitej w wektorze nie będzie już ważne. Więc to nie jest bezpieczne?

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

Czy to jest bezpieczne?

Wygląda na to, że http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#526 zajęło się tym problemem (lub czymś bardzo podobnym) jako potencjalną wadą w standardzie:

1) Parametry pobierane przez stałą referencję mogą być zmieniane podczas wykonywania funkcji

Przykłady:

Biorąc pod uwagę std :: wektor v:

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

v [2] można zmienić przesuwając elementy wektora

Proponowana rezolucja była taka, że ​​nie jest to wada:

vector :: insert (iter, value) jest wymagany do działania, ponieważ standard nie zezwala na to, aby nie działał.

Tak, jest to bezpieczne, a standardowe implementacje bibliotek przeskakują przez obręcze, aby tak było.

Wierzę, że realizatorzy w jakiś sposób śledzą to wymaganie z powrotem do 23,2 / 11, ale nie mogę dowiedzieć się, jak, i nie mogę znaleźć czegoś bardziej konkretnego. Najlepsze, co mogę znaleźć, to ten artykuł:

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

Inspekcja implementacji libc ++ i libstdc ++ pokazuje, że są one również bezpieczne.

Norma gwarantuje, że nawet Twój pierwszy przykład będzie bezpieczny. Cytowanie C ++ 11

[sequence.reqmts]

3 W tabelach 100 i 101 ... Xoznacza klasę kontenera sekwencji, aoznacza wartość Xzawierającą elementy typu T, ... toznacza lwartość lub stałą rwartośćX::value_type

16 Tabela 101 ...

Wyrażenie a.push_back(t) Typ zwrotu void Semantyka operacyjna Dołącza kopię t. wymagań: T należy CopyInsertabledo X. Pojemnik basic_string , deque, list,vector

Więc nawet jeśli nie jest to całkiem trywialne, implementacja musi gwarantować, że nie unieważni odwołania podczas wykonywania push_back.

Nie jest oczywiste, że pierwszy przykład jest bezpieczny, ponieważ najprostsza implementacja push_backpolegałaby na ponownym przydzieleniu wektora, jeśli to konieczne, a następnie skopiowaniu odwołania.

Ale przynajmniej wydaje się, że jest to bezpieczne w Visual Studio 2010. Jego implementacja push_backwykonuje specjalną obsługę przypadku, gdy przesuwasz z powrotem element w wektorze. Kod ma następującą strukturę:

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
                    ...
        }
    }

To nie jest gwarancja ze standardu, ale jako kolejny punkt danych v.push_back(v[0])jest bezpieczny dla libc ++ LLVM .

std::vector::push_backWywołania libc ++,__push_back_slow_path gdy musi ponownie przydzielić pamięć:

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.
}

Pierwsza wersja zdecydowanie NIE jest bezpieczna:

Operacje na iteratorach uzyskane przez wywołanie standardowego kontenera biblioteki lub funkcji składowej ciągu mogą uzyskać dostęp do podstawowego kontenera, ale nie mogą go modyfikować. [Uwaga: W szczególności operacje kontenera, które unieważniają iteratory, powodują konflikt z operacjami na iteratorach skojarzonych z tym kontenerem. - notatka końcowa]

od sekcji 17.6.5.9

Zwróć uwagę, że jest to sekcja dotycząca wyścigów danych, o których ludzie zwykle myślą w połączeniu z wątkami ... ale rzeczywista definicja obejmuje relacje „dzieje się przed” i nie widzę żadnego związku porządkującego między wieloma efektami ubocznymi push_backw grać tutaj, a mianowicie, że unieważnienie odniesienia nie wydaje się być zdefiniowane jako uporządkowane w odniesieniu do kopiowania konstruowania nowego elementu ogona.

To jest całkowicie bezpieczne.

W swoim drugim przykładzie masz

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

co nie jest potrzebne, ponieważ jeśli wektor przekroczy swój rozmiar, będzie to oznaczać reserve.

To Vector jest odpowiedzialny za to, a nie Ty.

Oba są bezpieczne, ponieważ push_back skopiuje wartość, a nie odwołanie. Jeśli przechowujesz wskaźniki, jest to nadal bezpieczne, jeśli chodzi o wektor, ale po prostu wiedz, że będziesz mieć dwa elementy wektora wskazujące na te same dane.

Sekcja 23.2.1 Ogólne wymagania dotyczące kontenerów

16

• a.push_back (t) Dołącza kopię t. Wymaga: T powinno być CopyInsertable do X.
• a.push_back (rv) Dołącza kopię rv. Wymaga: T musi być MoveInsertable do X.

Implementacje push_back muszą zatem zapewniać wstawienie kopii v[0] . Dla kontrprzykładu, zakładając implementację, która zmieniłaby alokację przed skopiowaniem, z pewnością nie dołączyłaby kopii v[0]i jako taka naruszyłaby specyfikacje.

Od 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.

Ponieważ wstawiamy na końcu, żadne odwołania nie zostaną unieważnione, jeśli wektor nie zostanie zmieniony. Więc jeśli wektor capacity() > size()to na pewno zadziała, w przeciwnym razie gwarantowane będzie niezdefiniowane zachowanie.