List :: size () veramente O (n)?

Recentemente, ho notato alcune persone che citano che std::list::size() ha una complessità lineare.
Secondo alcune fonti , questo è in realtà dipendente dall’implementazione in quanto lo standard non dice quale debba essere la complessità.
Il commento in questo post di blog dice:

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

  1. Quindi la mia ipotesi è che per la size() massa di VC ++ size() abbia una complessità costante dato che Dinkumware probabilmente non avrà cambiato questo fatto dal VC6. Sono di destra?
  2. Che aspetto ha attualmente in gcc ? Se è veramente O (n), perché gli sviluppatori hanno scelto di farlo?

    Pre-C ++ 11 risposta

    Avete ragione nel dire che lo standard non stabilisce quale debba essere la complessità di list :: size () – tuttavia, raccomanda che “dovrebbe avere una complessità costante” (Nota A nella Tabella 65).

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

    Penso che i punti principali del documento siano:

    • ci sono alcune situazioni in cui mantenere un conteggio interno in modo che list::size() possa essere O (1) fa sì che l’operazione di giunzione diventi lineare
    • ci sono probabilmente molte altre situazioni in cui qualcuno potrebbe non essere a conoscenza degli effetti negativi che potrebbero verificarsi perché chiamano una dimensione O (N) size() (come il suo esempio in cui list::size() viene chiamato mentre si tiene un blocco).
    • che invece di consentire size() sia O (N), nell’interesse di ‘least surprise’, lo standard dovrebbe richiedere qualsiasi contenitore che implementa size() per implementarlo in modo O (1). Se un contenitore non può farlo, non dovrebbe implementare size() . In questo caso, l’utente del contenitore verrà informato che size() non è disponibile e se desiderano o devono comunque ottenere il numero di elementi nel contenitore possono comunque utilizzare container::distance( begin(), end()) per ottenere quel valore – ma saranno completamente consapevoli che si tratta di un’operazione O (N).

    Penso di essere in accordo con la maggior parte dei suoi ragionamenti. Tuttavia, non mi piace la sua aggiunta proposta ai sovraccarichi di splice() . Dover passare un n che deve essere uguale alla distance( first, last) per ottenere un comportamento corretto sembra una ricetta per diagnosticare i bachi difficili da diagnosticare.

    Non sono sicuro di cosa si debba o si potrebbe fare per andare avanti, poiché ogni cambiamento avrebbe un impatto significativo sul codice esistente. Ma così com’è, penso che il codice esistente sia già influenzato – il comportamento potrebbe essere piuttosto significativamente diverso da un’implementazione all’altra per qualcosa che avrebbe dovuto essere ben definito. Forse il commento di onebyone su come avere la dimensione ‘cache’ e contrassegnato noto / sconosciuto potrebbe funzionare bene – si ottiene un comportamento O (1) ammortizzato – l’unica volta che si ottiene il comportamento O (N) è quando l’elenco viene modificato da alcune operazioni di splice () . La cosa bella di questo è che può essere fatto dagli implementatori oggi senza una modifica allo standard (a meno che manchi qualcosa).

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

    In C ++ 11 è necessario che per qualsiasi contenitore standard l’operazione .size() sia completa in complessità “costante” (O (1)). (Tabella 96 – Requisiti del contenitore). Precedentemente in C ++ 03 .size() dovrebbe avere una complessità costante, ma non è richiesto (si veda Is std :: string size () un’operazione di O (1)? ).

    La modifica dello standard è introdotta da n2923: Specifica della 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é è std :: list più grande su c ++ 11? per i dettagli perché è tenuto in questo modo.

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


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

     _LIBCPP_INLINE_VISIBILITY size_type size() const _NOEXCEPT {return base::__sz();} ... __compressed_pair __size_alloc_; _LIBCPP_INLINE_VISIBILITY const size_type& __sz() const _NOEXCEPT {return __size_alloc_.first();} 

    Ho dovuto esaminare la lista di gcc 3.4 :: size in precedenza, quindi posso dire questo:

    1. usa std :: distance (head, tail)
    2. std :: distance ha due implementazioni: per i tipi che soddisfano RandomAccessIterator, usa “tail-head”, e per i tipi che soddisfano semplicemente InputIterator, utilizza un algoritmo O (n) basato su “iteratore ++”, contando fino a quando non raggiunge il dato coda.
    3. std :: list non satsify RandomAccessIterator, quindi la dimensione è O (n).

    Per quanto riguarda il “perché”, posso solo dire che std :: list è appropriato per problemi che richiedono l’accesso sequenziale. Memorizzare la dimensione come una variabile di class introdurrebbe un sovraccarico su ogni inserto, elimina, ecc. E quello spreco è un grande no-no secondo l’intento del STL. Se hai davvero bisogno di una dimensione costante (), usa std :: deque.

    Personalmente non vedo il problema con splice essere O (N) come l’unico motivo per cui la dimensione è permesso di essere O (N). Non si paga per quello che non si usa è un importante motto in C ++. In questo caso, il mantenimento delle dimensioni dell’elenco richiede un incremento / decremento extra per ogni inserimento / cancellazione, indipendentemente dal fatto che si verifichi o meno la dimensione dell’elenco. Questo è un piccolo overhead fisso, ma è comunque importante da considerare.

    Il controllo della dimensione di un elenco è raramente necessario. Iterare dall’inizio alla fine senza preoccuparsi della dimensione totale è infinitamente più comune.

    Vorrei andare alla fonte . La pagina STL di SGI afferma che è consentito avere una complessità lineare. Credo che la linea guida di progettazione che hanno seguito sia stata quella di permettere che l’implementazione della lista fosse il più generica ansible, e quindi di consentire una maggiore flessibilità nell’utilizzo delle liste.

    Questo bug report: [C ++ 0x] std :: list :: size complessità , cattura in dettaglio straziante il fatto che l’implementazione in GCC 4.x sia lineare e come la transizione al tempo costante per C ++ 11 sia stata lenta in arrivo (disponibile in 5.0) a causa di problemi di compatibilità ABI.

    La pagina di manuale per la serie 4.9 di GCC include ancora il seguente disclaimer:

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


    Lo stesso bug report è riferito qui: dovrebbe std :: list :: size avere una complessità costante in C ++ 11?

    Se stai usando correttamente le liste, probabilmente non noti alcuna differenza.

    Gli elenchi sono validi con strutture di dati di grandi dimensioni che si desidera riordinare senza copiare, per i dati che si desidera mantenere i puntatori validi dopo l’inserimento.

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

    In ogni caso std parla più di correttezza, comportamento standard e “facilità d’uso” rispetto alla velocità non elaborata.