List :: size () è davvero O (n)?

StackOverflow https://stackoverflow.com/questions/228908

Domanda

Di recente, ho notato alcune persone che menzionano che std :: list :: size () ha una complessità lineare.
Secondo alcuni fonti , questo dipende dall'implementazione poiché lo standard non dice quale sia la complessità.
Il commento in questo post di blog dice :

  

In realtà, dipende da quale STL tu   stiamo usando. Microsoft Visual Studio V6   implementa size () come {return (_Size);   } considerando gcc (almeno nelle versioni   3.3.2 e 4.1.0) lo fanno come {return std :: distance (begin (), end ()); } Il   il primo ha una velocità costante, il secondo   ha o (N) velocità

  1. Quindi la mia ipotesi è che per la folla VC ++ size () abbia una complessità costante come Dinkumware probabilmente non avrà cambiato questo fatto dal VC6. Sono proprio lì?
  2. Che aspetto ha attualmente in gcc ? Se è davvero O (n), perché ha fatto gli sviluppatori scelgono di farlo?
È stato utile?

Soluzione

Risposta pre-C ++ 11

Hai ragione nel dire che lo standard non indica quale deve essere la complessità di list :: size () - tuttavia, si raccomanda che "abbia una complessità costante" (Nota A nella tabella 65).

Ecco un interessante articolo di Howard Hinnant che spiega perché alcune persone pensano list :: size ( ) dovrebbe avere una complessità O (N) (sostanzialmente perché credono che O (1) list :: size () rende list :: splice () abbia una complessità O (N)) e perché un O (1) list :: size ( ) è una buona idea (secondo l'opinione dell'autore):

Penso che i punti principali nel documento siano:

  • ci sono poche situazioni in cui il mantenimento di un conteggio interno, quindi list :: size () può essere O (1) fa diventare lineare l'operazione di splicing
  • ci sono probabilmente molte più situazioni in cui qualcuno potrebbe non essere consapevole degli effetti negativi che potrebbero verificarsi perché chiamano una O (N) size () (come il suo esempio in cui l'elenco :: size () viene chiamato mentre si tiene premuto un lucchetto).
  • che invece di consentire size () sia O (N), nell'interesse della 'minima sorpresa', lo standard dovrebbe richiedere qualsiasi contenitore che implementa size () per implementarlo in modo O (1). Se un contenitore non può farlo, non dovrebbe implementare affatto size () . In questo caso, l'utente del contenitore verrà informato che size () non è disponibile e se vogliono o devono ancora ottenere il numero di elementi nel contenitore possono comunque usare container :: distance (begin (), end ()) per ottenere quel valore - ma saranno completamente consapevoli che si tratta di un'operazione O (N).

Penso di essere d'accordo con la maggior parte del suo ragionamento. Tuttavia, non mi piace la sua proposta aggiunta ai sovraccarichi splice () . Dover passare un n che deve essere uguale a distance (first, last) per ottenere un comportamento corretto sembra una ricetta per errori difficili da diagnosticare.

Non sono sicuro di cosa dovrebbe o potrebbe essere fatto andando avanti, poiché qualsiasi modifica avrebbe un impatto significativo sul codice esistente. Ma così com'è, penso che il codice esistente sia già influenzato: il comportamento potrebbe essere piuttosto diverso da un'implementazione all'altra per qualcosa che avrebbe dovuto essere ben definito. Forse il commento di uno a uno sull'avere la dimensione 'cache' e contrassegnato noto / sconosciuto potrebbe funzionare bene - ottieni un comportamento O (1) ammortizzato - l'unica volta che ottieni un comportamento O (N) è quando l'elenco viene modificato da alcune operazioni splice () . La cosa bella di questo è che oggi può essere fatto dagli implementatori senza cambiare lo standard (a meno che non mi manchi qualcosa).

Per quanto ne so, C ++ 0x non sta cambiando nulla in quest'area.

Altri suggerimenti

In C ++ 11 è necessario che per qualsiasi contenitore standard l'operazione .size () debba essere completata in " costante " complessità (O (1)). (Tabella 96 & # 8212; Requisiti del contenitore). Precedentemente in C ++ 03 .size () dovrebbe avere una complessità costante, ma non è richiesto (vedere È std :: string size () un'operazione O (1)? ).

La modifica dello standard è stata introdotta da n2923 : Specifica la complessità di size () (Revisione 1) .

Tuttavia, l'implementazione di .size () in libstdc ++ utilizza ancora un algoritmo O (N) in gcc fino a 4.8: 

  /**  Returns the number of elements in the %list.  */
  size_type
  size() const _GLIBCXX_NOEXCEPT
  { return std::distance(begin(), end()); }

Vedi anche Perché lo std :: list è più grande su c ++ 11? per i dettagli, perché viene mantenuto in questo modo.

Update : std :: list :: size () è correttamente O (1) quando si utilizza gcc 5.0 in modalità C ++ 11 (o sopra).

A proposito, .size () in libc ++ è correttamente O (1): 

_LIBCPP_INLINE_VISIBILITY
size_type size() const _NOEXCEPT     {return base::__sz();}

...

__compressed_pair<size_type, __node_allocator> __size_alloc_;

_LIBCPP_INLINE_VISIBILITY
const size_type& __sz() const _NOEXCEPT
    {return __size_alloc_.first();}

Ho dovuto esaminare l'elenco di gcc 3.4 :: size prima, quindi posso dire questo:

  1. usa std :: distance (testa, coda)
  2. std :: distance ha due implementazioni: per i tipi che soddisfano RandomAccessIterator, utilizza "tail-head", e per i tipi che soddisfano semplicemente InputIterator, utilizza un algoritmo O (n) che si basa su " iterator ++ " ; contando fino a quando non colpisce la coda data.
  3. std :: list non identifica RandomAccessIterator, quindi la dimensione è O (n).

Per quanto riguarda il "perché", posso solo dire che std :: list è appropriato per i problemi che richiedono un accesso sequenziale. Memorizzare la dimensione come variabile di classe introdurrebbe un sovraccarico su ogni inserimento, eliminazione, ecc. E tale spreco è un grande no-no per l'intento dell'STL. Se hai davvero bisogno di una dimensione a tempo costante (), usa std :: deque.

Personalmente non vedo il problema con la giunzione che è O (N) come l'unico motivo per cui la dimensione può essere O (N). Non paghi per ciò che non usi è un motto C ++ importante. In questo caso, il mantenimento delle dimensioni dell'elenco richiede un ulteriore incremento / decremento ad ogni inserimento / cancellazione indipendentemente dal fatto che si controlli o meno le dimensioni dell'elenco. Questo è un piccolo overhead fisso, ma è ancora importante da considerare.

Raramente è necessario verificare la dimensione di un elenco. Iterare dall'inizio alla fine senza preoccuparsi della dimensione totale è infinitamente più comune.

Vorrei andare alla fonte ( archivio ). La pagina STL di SGI afferma che è permesso avere una complessità lineare. Credo che la linea guida di progettazione seguita fosse quella di consentire l'implementazione degli elenchi nel modo più generale possibile e quindi di consentire una maggiore flessibilità nell'uso degli elenchi.

Questo bug report: [C ++ 0x] std :: list: : complessità dimensionale , cattura in modo estremamente dettagliato il fatto che l'implementazione in GCC 4.x è un tempo lineare e come il passaggio al tempo costante per C ++ 11 è stato lento (disponibile in 5.0) a causa della compatibilità ABI preoccupazioni.

La manpage della serie GCC 4.9 include ancora il seguente disclaimer:

  

Il supporto per C ++ 11 è ancora   sperimentale e potrebbe cambiare in modo incompatibile nelle versioni future.

Qui si fa riferimento allo stesso bug report: dovrebbe essere std :: list :: size una complessità costante in C ++ 11?

Se stai usando correttamente gli elenchi probabilmente non stai notando alcuna differenza.

Gli elenchi vanno bene con le strutture di big data che si desidera riorganizzare senza copiare, per i dati che si desidera mantenere puntatori validi dopo l'inserimento.

Nel primo caso non fa differenza, nel secondo preferirei la vecchia (più piccola) dimensione ().

Comunque std riguarda più la correttezza, il comportamento standard e la "facilità d'uso" che la velocità pura.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top