Std :: string size () è un'operazione O (1)?

Question

std :: string size () è un'operazione O (1)?

L'implementazione di STL che sto usando è quella integrata in VC ++

Answer 1

Se stai chiedendo se l'implementazione di string :: size () di MSVC ha una complessità costante, la risposta è sì. Ma Don Wakefield menzionato la Tabella 65 nel 23.1 dello standard C ++ dove afferma che la complessità di size () dovrebbe seguire quanto detto nella "Nota A". La nota A dice:

  

Le voci contrassegnate con & # 8216; & # 8216; (Nota A) & # 8217; & # 8217;   dovrebbe avere una complessità costante.

Tuttavia, ciò non significa che tali voci debbano avere una complessità costante. Gli standard usano una terminologia molto specifica e "dovremmo" significa che non è obbligatorio.

'Nota A' è stata aggiunta allo standard specificamente per placare coloro che credevano che size () avrebbe dovuto avere una complessità lineare, quindi non sarebbe necessario mantenere le dimensioni quando i contenitori erano modificato.

Quindi non puoi fare affidamento sul fatto che size () abbia una complessità costante, ma sinceramente non sono sicuro che ci siano implementazioni che non hanno una stringa :: size ( ) .

Answer 2

Ecco un modo semplice per rispondere a questa domanda per msvc ++.

Scrivi del codice in un progetto:

string happy;
happy.size();

Riavvia la chiamata .size, fai clic con il pulsante destro del mouse, vai alla definizione.

Nella mia installazione (vs2005sp1) questo mi invia a xstring: 1635, che assomiglia a questo:

size_type __CLR_OR_THIS_CALL size() const
    {   // return length of sequence
    return (_Mysize);
    }

Quindi sembra che la stringa abbia un membro chiamato _Mysize, e lo sta solo restituendo.

In altre parole, questa è un'implementazione O (1).

Answer 3

Sì, std :: string :: size () è O (1).

Answer 4

Vedere la tabella 65 nella sezione 23.1 della norma. & Quot; a.size () " è elencato come "(Nota A)", che dice che "Quelle voci ... dovrebbero avere una complessità costante".

La Sezione 21.3 afferma che le stringhe sono conformi ai requisiti di una sequenza (23.1), ipso facto, size () è tempo costante.

Answer 5

Per una stringa, l'operazione size () deve essere costante per tutte le implementazioni di stringa che non usano ropes ⁽¹⁾ . Non esiste alcun requisito esplicito nello standard che richiede che l'operazione sia O (1) , il più vicino è il requisito generico che size () dovrebbe essere tempo costante, ma ciò lascia spazio a qualsiasi altra misura di complessità.

Quindi perché deve essere O (1)?

Ciò deriva dal fatto che la dimensione non può essere calcolata dal contenuto della stringa stessa. Mentre in C si utilizza un terminatore NUL per determinare la fine della stringa, in C ++ NUL è valido come qualsiasi altro carattere nella stringa. Poiché la dimensione della stringa non può essere calcolata dal contenuto ⁽²⁾ , deve essere gestita esternamente, indipendentemente dalla dimensione effettiva della stringa.

⁽¹⁾ Lo standard C ++ 03 consente a un'implementazione di usare corde come implementazione per le stringhe, ma il fatto è che nessuna delle attuali implementazioni dello standard le biblioteche li usano.

⁽²⁾ Se l'implementazione utilizzava delle corde, l'operazione potrebbe dipendere dalle dimensioni mediante il numero di blocchi da cui è stata costruita la corda se i blocchi fossero collegati attraverso un elenco collegato o simili costruire, o se fosse permesso loro di avere dimensioni diverse. Ma corde non sono usate in nessuna implementazione di libreria standard che io conosca.

Answer 6

L'STL garantisce che le prestazioni siano almeno O (N) per i contenitori, tuttavia molti contenitori tra cui std :: string possono implementarlo come O (1) e lo faranno. Di solito restituisce una semplice variabile o fa qualcosa come _End - _Begin e la restituisce.

Answer 7

size_type __CLR_OR_THIS_CALL size() const

{   // return length of sequence

    return (_Mysize);

}

Quindi alla fine potrebbe essere così, ma non puoi mai esserne sicuro.