STL C++ - Perché il metodo forward_list no size()?

Question

Utilizzo il C++ 11 forward_list come contenitore per gli inserimenti rapidi, senza troppo carico di memoria, poiché si tratta di un elenco collegato separatamente.

Dopo aver realizzato che il metodo forward_list non ha il metodo , sono un po 'confuso sul ragionamento alla base di ciò. Non potrebbe semplicemente mantenere un campo privato tenendo traccia dei nodi inseriti e rimossi, quindi implementando un'operazione O (1) size()?

Answer 1

N2543 è la proposta e ha una discussione dettagliata su size().

La scelta tra opzione 3 [non fornire size()] e Opzione 2 [fornire un O (1) size()] è più una questione di giudizio. Ho scelto l'opzione 3 per la stessa ragione per cui ho scelto insert-after anziché insert-before: l'opzione 3 è più coerente con l'obiettivo di zero overhead rispetto a un elenco collegato in stile C scritto a mano. Il mantenimento di un conteggio raddoppia le dimensioni di un oggetto forward_list (una parola per la riga di elenco e una per il conteggio) e rallenta ogni operazione che modifica il numero di nodi. Nella maggior parte dei casi non si tratta di una variazione asintotica di (l'unica variazione nella complessità asintotica di è in una delle forme di splice), ma è un carico non diverso . È un costo che tutti gli utenti dovrebbero pagare, sia che abbiano questa funzione o meno, e, per gli utenti che amano il mantenendo un conteggio, è altrettanto facile mantenerlo al di fuori dell'elenco , incrementando il conteggio con ogni inserto e lo decrementa con ad ogni cancellazione, come lo è per mantenere il conteggio all'interno della lista.

Answer 2

I contenitori STL hanno rimosso in modo tradizionale/intelligente le caratteristiche delle strutture di dati che non hanno un buon rendimento in termini di tempo e spazio.

Aggiunta citazione da "libreria standard C++ - un tutorial e riferimento"

Un std::forward_list non fornisce una funzione size() membro. Questa è una conseguenza dell'omissione delle funzioni che creano un sovraccarico di tempo o spazio in relazione a un elenco collegato a mano.

Answer 3

Mi chiedo se il comitato standard abbia considerato un mix-in come parametro di modello che può aggiungere la manutenzione di un membro di dimensione facoltativo alle classi di elenchi? Ciò avrebbe permesso alla classe di avere un conteggio di elementi facoltativo, senza perdita di generalità.

come questo

class HasSize 
{ 
public: 
    HasSize() : size_(0) { } 

    void addSize(size_t add) { size_ += add; } 

    bool has_size() { return true; } 

    size_t size() { return size_; } 

    size_t size_; 
}; 

class NoSize 
{ 
public: 
    void addSize(size_t add) { } 

    bool has_size() { return false; } 

    size_t size() { return 0; } 
}; 

template<type T, type Allocator, type Sz = HasSize> 
class forward_list 
{ 

    void push_back(T &arg) 
    { 
     ... 
     opt_.addSize(1); 
    } 

    size_t size() 
    { 
     if (opt_.has_size()) 
      return opt_.size(); 
     else 
      return std::distance(begin(), end()); 
    } 

    Sz opt_; 
}; 

/a questa domanda è stato contrassegnato come duplicato, in modo da aggiungere qui/