Perché non c'è un operatore [] per una lista std ::?

Question

Qualcuno può spiegare perché l'operatore [] non è implementato per una lista std ::? Ho cercato un po 'ma non ho trovato una risposta. Non sarebbe troppo difficile da implementare o mi manca qualcosa?

Answer 1

Il recupero di un elemento per indice è un'operazione O (n) per l'elenco collegato, che è ciò che è std::list. Così è stato deciso che fornire operator[] sarebbe ingannevole, dal momento che le persone sarebbero tentati di utilizzare attivamente, e poi si vedrebbe il codice come:

std::list<int> xs; 
for (int i = 0; i < xs.size(); ++i) { 
    int x = xs[i]; 
    ... 
} 

che è O (n^2) - molto brutto. Pertanto, lo standard ISO C++ indica specificamente che tutte le sequenze STL che supportano operator[] dovrebbero farlo in tempo costante ammortizzato (23.1.1 [lib.sequence.reqmts]/12), che è ottenibile per vector e deque, ma non list.

Per i casi in cui è effettivamente necessario questo genere di cose, è possibile utilizzare std::advance algoritmo:

int iter = xs.begin(); 
std::advance(iter, i); 
int x = *iter; 

Answer 2

Non sarebbe troppo difficile (per l'implementatore) ma sarebbe troppo difficile in fase di esecuzione, poiché la prestazione sarà terribile nella maggior parte dei casi. Costringere l'utente a passare attraverso ogni link renderà più ovvio ciò che sta accadendo in là rispetto a "myList [102452]".

Answer 3

Credo di aver trovato la risposta in un altro SO inviare Extending std::list

"l'operatore [] è O (N) time "- questo è esattamente il motivo per cui non è incluso in standard std :: list <>. - Michael Burr 14 dicembre alle 17:29

Tuttavia, è questa l'unica ragione?

EDIT: Sembra che, come si è detto, è più una questione di coerenza in termini di prestazioni, quindi di prestazioni rigorose.

Answer 4

In realtà, non c'è assolutamente alcuna ragione per non fornire all'operatore [] o almeno il metodo a (int), a causa dei due motivi:

• E 'doppia lista collegata, quindi è necessario muoversi a la maggior parte delle dimensioni()/2 posiziona il tuo iteratore per ottenere il tuo indice, e i costi per mantenere internamente pochi altri iteratori fissi sono molto bassi. E alla fine, la libreria Qt fornisce l'operatore [] e l'at, e non vedo costi di performance che lo utilizzano.
• forzare le persone a non usare è un'abitudine di programmazione molto brutta, perché un elenco è molto contenitore utilizzabile, se si ha un "accesso casuale" vicino all'accesso collegato, vi sono vari esempi quando è necessario l'accesso, a seconda di quale punto di esecuzione.