2009-07-07 17 views
18

Mi chiedevo se restituire un elenco, invece di restituire un puntatore a uno, fosse costoso in termini di prestazioni perché, se ricordo, una lista non ha molti attributi (non è qualcosa come 3 puntatori? per la posizione attuale, una per l'inizio e una per la fine?).Restituisce un elenco std :: costoso?

risposta

33

Se si restituisce un valore std::list in modo non copierà solo la testata dell'elenco, verrà copiato un nodo elenco per elemento nell'elenco. Quindi sì, per una lunga lista è costoso.

Se l'elenco è incorporato nella funzione che lo sta restituendo, è possibile trarre vantaggio dall'ottimizzazione del valore di ritorno con nome, per evitare una copia non necessaria. Questo è specifico per il tuo compilatore, però. Non si applica mai se, ad esempio, la lista esistesse già prima che la funzione venisse chiamata (ad esempio se si tratta di una variabile membro di un oggetto).

Un linguaggio comune in C++, per evitare di restituire contenitori in base al valore, consiste nel prendere un iteratore di output come parametro. Così, invece di:

std::list<int> getListOfInts() { 
    std::list<int> l; 
    for (int i = 0; i < 10; ++i) { 
     l.push_back(i); 
    } 
    return l; 
} 

Fate:

template<typename OutputIterator> 
void getInts(OutputIterator out) { 
    for (int i = 0; i < 10; ++i) { 
     *(out++) = i; 
    } 
} 

Poi il chiamante fa:

std::list<int> l; 
getInts(std::back_inserter(l)); 

Spesso una volta che il compilatore ha terminato la messa in linea e l'ottimizzazione, il codice è più o meno identico .

Il vantaggio di ciò è che il chiamante non è legato a una particolare raccolta, ad esempio può avere gli elementi aggiunti a un vettore anziché una lista se ciò è più utile per le circostanze particolari. Se ha solo bisogno di vedere ogni oggetto una volta, invece di tutti insieme, allora può salvare la memoria elaborandoli in modalità streaming usando un iteratore di output del suo stesso progetto.

Gli svantaggi sono gli stessi di qualsiasi codice modello: l'implementazione deve essere disponibile al chiamante in fase di compilazione e si può finire con un sacco di codice oggetto "duplicato" per più istanze del modello. Ovviamente è possibile utilizzare lo stesso modello senza utilizzare i modelli, prendendo come parametro un puntatore a funzione (più un puntatore dati utente se desiderato) e chiamandolo una volta con ciascun elemento o definendo una classe astratta IntVisitor, con un membro virtuale puro funzione, e avere il chiamante fornire un'istanza di esso.

[Modifica: T.E.D indica in un commento che un altro modo per evitare la copia senza utilizzare i modelli è che il chiamante passi in un elenco per riferimento. Certamente funziona, offre al chiamante meno flessibilità rispetto al modello e quindi non è l'idioma utilizzato da STL. È una buona opzione se non vuoi il "vantaggio di questo" che descrivo sopra. Una delle intenzioni originali dietro l'STL, però, è separare gli "algoritmi" (in questo caso quelli che determinano i valori) da "contenitori" (in questo caso, il fatto che i valori capita di essere memorizzati in una lista, al contrario a un vettore o un array o un set di auto-ordinamento, o semplicemente stampato senza memorizzarli affatto.]

+0

Grazie, ho pensato che fosse solo copiando la testa! –

+3

Interessante. Perché non basta passare la lista per riferimento? –

+0

Impaurito non - una copia di qualsiasi raccolta STL è una copia completa (incluse copie degli articoli stessi). Questo è così che quando si modifica la copia (oi suoi elementi) non si modifica anche l'originale. Anche se si tratta di una raccolta di puntatori, i puntatori devono ancora essere copiati, anche se, naturalmente, gli oggetti puntati non vengono copiati e sono ancora "condivisi" tra le raccolte. –

0

Credo che il costruttore di copie sia chiamato.

+0

In effetti lo è, ma mi chiedevo cosa stesse facendo il costruttore di copie. Grazie ancora! –

+0

il mio consiglio: compra Pensare in C++ di Bruce Eckel, la maggior parte di queste domande andrà via dopo il primo passaggio ;-) – MadH

+0

Acquista C++ accelerato di Andrew Koenig e Barbara Moo. –

0

Può essere costoso, in quanto copierà ogni elemento nell'elenco. Ancora più importante, ha un comportamento diverso: vuoi una copia della lista o vuoi un puntatore alla lista originale?

2

Se si restituisce il valore, verrà chiamato il costruttore di copie e gli elementi verranno copiati uno per uno. A volte verrai salvato dall'ottimizzazione del valore con nome come indicato da onebyone.

I suoi principali opzioni per assicurare la copia non avrà luogo sono:

  • Passo in un elenco con riferimento a essere compilato dalla funzione. In questo modo indichi la funzione in cui inserire i dati e non sarà necessario effettuare alcuna copia perché l'hai inserita nella posizione finale.
  • Assegnare un elenco all'heap e restituirlo. Dovresti restituirlo in un puntatore intelligente come std :: auto_ptr o boost :: shared_ptr per assicurarti che venga cancellato e che sia eccezionalmente sicuro.
5

Esso (come sempre) dipende. Il costruttore di copie può o non può essere invocato mediante ritorno nel seguente codice.

std::list<int> foo() { 
    std::list<int> bar; 
    // ... 
    return bar; 
}; 

Esso non può essere invocata se il compilatore applica return value optimization. Se viene chiamato il costruttore di copie, è probabilmente più costoso rispetto a un puntatore per elenchi più grandi e, se non viene chiamato, è più rapido restituire l'elenco diretto (perché evita un'allocazione dinamica)

Personalmente, non mi preoccupo e restituisco la lista. Quindi, solo quando il mio profiler dice che questo è un problema, considero le ottimizzazioni.

+1

leggi anche [this] (http://cpp-next.com/archive/2009/08/want-speed-pass-by-value/) – andreabedini

Problemi correlati