std :: vector :: inserire riserva per definizione?

Question

Quando si chiama la funzione membro insert su un std::vector, sarà reserve prima di "respingere" i nuovi elementi? Voglio dire, lo standard lo garantisce o no?

In altre parole, devo fare in questo modo:

std::vector<int> a{1,2,3,4,5}; 
std::vector<int> b{6,7,8,9,10}; 
a.insert(a.end(),b.begin(),b.end()); 

o come questo:

std::vector<int> a{1,2,3,4,5}; 
std::vector<int> b{6,7,8,9,10}; 
a.reserve(a.size()+b.size()); 
a.insert(a.end(),b.begin(),b.end()); 

o un altro approccio migliore?

Answer 1

quanto riguarda la complessità della funzione [link]:

lineare del numero di elementi inseriti (copia costruzione/spostare) più il numero di elementi dopo la posizione (in movimento).

Inoltre, se InputIterator nell'inserto gamma (3) non è almeno uno stile iteratore in avanti (cioè solo un iteratore ingresso) il nuovo capacità non può essere determinato in anticipo e l'inserimento incorre in ulteriori complessità logaritmica in taglia (riallocazioni).

Quindi, ci sono due casi:

• La nuova capacità può essere determinato, quindi non sarà necessario chiamare prenotare
• La nuova capacità non può essere determinato, quindi una chiamata a reserve dovrebbe essere utile.

Answer 2

Dal documentation, sembra che:

cause riallocazione se il nuovo formato() è maggiore rispetto al vecchio capacità().

Si noti inoltre che in tal caso tutti gli iteratori e i riferimenti sono invalidati.

Va da sé quindi che riassegnazioni sono responsabile della insert e, se si guarda a tali operazioni una alla volta, è come un coerente di riserva-size-plus one- operazione è effettuata ad ogni passo.
Si può sostenere che una chiamata reserve nella parte superiore dell'inserzione acceleri tutto in quei casi in cui si verifica più di una riallocazione ... Bene, potrebbe essere d'aiuto, ma dipende in gran parte dal tuo problema reale.

Answer 3

std::vector::insert riserva per definizione?

Sì, no; dipende dalla capacità attuale.

Dal progetto N4567, §23.3.6.5/1 ([vector.modifiers]):

Cause riallocazione se il nuovo formato è superiore alla vecchia capienza.

Se la capacità di memoria allocata nel vector è sufficientemente grande per contenere i nuovi elementi, non sono necessari ulteriori accantonamenti per il vector. Quindi no, quindi non riserverà memoria.

Se la capacità dello vector non è sufficientemente grande, viene assegnato un nuovo blocco, i contenuti correnti vengono spostati/copiati e i nuovi elementi vengono inseriti. L'algoritmo di allocazione esatto non è specificato, ma in genere dovrebbe essere quello utilizzato nel metodo reserve().

... o un altro approccio migliore?

Se siete preoccupati per troppi allocazioni, mentre l'inserimento di elementi nella vector, quindi chiamando il metodo reserve con la dimensione del numero di elementi che ci si attende da aggiungere non ridurre gli stanziamenti.

Il vector chiama reserve prima degli/eventuali inserimenti? Cioè assegna abbastanza capacità in un'unica allocazione?

Nessuna garanzia. Come saprebbe la distanza tra gli iteratori di input? Dato che il metodo insert può prendere un InputIterator (cioè un iteratore a passaggio singolo), non ha alcun motivo per calcolare la dimensione prevista. Il metodo può calcolare la dimensione se gli iteratori contengono qualcos'altro (ad es. Puntatori o RandomAccessIterator)? Sì, potrebbe. Lo sarebbe? Dipende dall'implementazione e dalle ottimizzazioni che vengono fatte.