c++ vector - È sicuro premere un elemento di push_back dallo stesso vettore?




example array (9)

Sì, è sicuro, e le implementazioni di libreria standard saltano attraverso i cerchi per renderlo tale.

Credo che gli implementatori riportino questo requisito al 23.2 / 11 in qualche modo, ma non riesco a capire come, e non riesco a trovare qualcosa di più concreto. Il meglio che posso trovare è questo articolo:

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

L'ispezione delle implementazioni di libc ++ e libstdc ++ mostra che sono anche sicuri.

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

Se il secondo push_back causa una riallocazione, il riferimento al primo intero nel vettore non sarà più valido. Quindi questo non è sicuro?

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

Questo lo rende sicuro?


Lo standard garantisce che anche il tuo primo esempio sia sicuro. Citando C ++ 11

[sequence.reqmts]

3 Nelle Tabelle 100 e 101 ... X denota una classe contenitore di sequenza, a denota un valore di X contenente elementi di tipo T , ... t denota un lvalue o un constvalval di X::value_type

16 Tabella 101 ...

Espressione a.push_back(t) Tipo di ritorno void Semantica operativa Appende una copia di t. Richiede: T deve essere CopyInsertable in X Contenitore basic_string , deque , list , vector

Quindi, anche se non è esattamente banale, l'implementazione deve garantire che non invalida il riferimento quando si fa push_back .


Questa non è una garanzia dallo standard, ma come un altro punto di dati, v.push_back(v[0]) è sicuro per libc ++ di LLVM .

std::vector::push_back libc ++ chiama __push_back_slow_path quando ha bisogno di riallocare la memoria:

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

È completamente sicuro

Nel tuo secondo esempio hai

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

che non è necessario perché se il vettore esce dalle sue dimensioni, implicherà la reserve .

Il vettore è responsabile di questa roba, non tu.


Entrambi sono sicuri poiché push_back copierà il valore, non il riferimento. Se stai memorizzando i puntatori, questo è ancora sicuro per quanto riguarda il vettore, ma sappi solo che avrai due elementi del tuo vettore che puntano agli stessi dati.

Sezione 23.2.1 Requisiti generali del contenitore

16
  • a.push_back (t) Aggiunge una copia di t. Richiede: T deve essere CopyInsertable in X.
  • a.push_back (rv) Aggiunge una copia di rv. Richiede: T deve essere MoveInsertable in X.

Le implementazioni di push_back devono quindi garantire che sia inserita una copia di v[0] . Per contro esempio, supponendo un'implementazione che sarebbe riallocata prima di copiare, non accoderebbe sicuramente una copia di v[0] e come tale viola le specifiche.


Sembra che http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#526 risolto questo problema (o qualcosa di molto simile ad esso) come un potenziale difetto dello standard:

1) I parametri presi da riferimento const possono essere modificati durante l'esecuzione della funzione

Esempi:

Dato std :: vector v:

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

v [2] può essere modificato spostando gli elementi del vettore

La risoluzione proposta era che questo non era un difetto:

vector :: insert (iter, value) è richiesto per funzionare perché lo standard non dà il permesso di non funzionare.


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

Dal momento che stiamo inserendo alla fine, nessun riferimento verrà invalidato se il vettore non viene ridimensionato. Quindi se la capacity() > size() del vettore capacity() > size() è garantita, altrimenti è garantito un comportamento indefinito.


Non è ovvio che il primo esempio sia sicuro, perché l'implementazione più semplice di push_back sarebbe quella di riallocare il vettore, se necessario, e quindi copiare il riferimento.

Ma almeno sembra essere sicuro con Visual Studio 2010. La sua implementazione di push_back fa una gestione speciale del caso quando si respinge un elemento nel vettore. Il codice è strutturato come segue:

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

java.util.Stack eredita l'overhead di sincronizzazione di java.util.Vector , che di solito non è giustificato.

Tuttavia eredita molto di più. Il fatto che java.util.Stack extends java.util.Vector è un errore nella progettazione orientata agli oggetti. I puristi noteranno che offre anche molti metodi oltre alle operazioni tradizionalmente associate a uno stack (vale a dire: push, pop, peek, size). È anche possibile eseguire search , elementAt , setElementAt , remove e molte altre operazioni di accesso casuale. È fondamentalmente compito dell'utente astenersi dall'utilizzare le operazioni non stack di Stack .

Per questi motivi di prestazioni e progettazione OOP, JavaDoc per java.util.Stack consiglia ArrayDeque come sostituzione naturale. (Una deque è più di una pila, ma almeno si limita a manipolare le due estremità, piuttosto che offrire accesso casuale a tutto.)





c++ vector reference language-lawyer push-back