C++: come funziona il tempo di accesso casuale dei vettori di stringa?

Question

So che un vettore int semplice ha O (1) tempo di accesso casuale, poiché è facile calcolare la posizione dell'elemento xth, dato che tutti gli elementi hanno la stessa dimensione.

Ora che succede con un vettore di stringa?

Poiché le lunghezze delle stringhe variano, non può avere O (1) tempo di accesso casuale, vero? Se può, qual è la logica dietro?

Grazie.

Aggiornamento:

Le risposte sono molto chiaro e conciso, grazie a tutti per l'aiuto. Ho accettato la risposta di Joey perché è semplice e facile da capire.

Answer 1

Il vettore ha O (1) tempo di accesso.

Gli oggetti stringa hanno tutte le stesse dimensioni (in una determinata implementazione), indipendentemente dalla dimensione della stringa che rappresentano. In genere l'oggetto stringa contiene un puntatore alla memoria allocata che contiene i dati della stringa.

Quindi, se s è un std::string, quindi sizeof s è costante e pari a sizeof(std::string), ma s.size() dipende dal valore di stringa. Il vettore si occupa solo di sizeof(std::string).

Answer 2

Poiché l'oggetto stringa ha una dimensione fissa proprio come qualsiasi altro tipo. La differenza è che l'oggetto stringa memorizza la propria stringa sull'heap e mantiene un puntatore alla stringa a dimensione fissa.

Answer 3

La stringa effettiva in una stringa: std :: di solito è solo un puntatore. La dimensione di una stringa è sempre la stessa, anche se la lunghezza della stringa che contiene varia.

Answer 4

Hai ottenuto un numero di risposte (ad es., Steve Jessop e AraK) che sono per lo più corrette già. Aggiungerò solo un piccolo dettaglio: molte implementazioni correnti di std::string usano quello che viene chiamato ottimizzazione della stringa corta (SSO), il che significa che allocano una piccola quantità di spazio fisso nell'oggetto stringa stesso che può essere utilizzato per memorizzare stringhe corte e solo quando/se la lunghezza supera ciò che è allocato nell'oggetto stringa stesso, alloca effettivamente lo spazio separato sull'heap per archiviare i dati.

Per quanto riguarda un vettore di stringhe, questo non fa alcuna differenza: ogni oggetto stringa ha una dimensione fissa indipendentemente dalla lunghezza della stringa stessa. La differenza è che con SSO la dimensione fissa è maggiore e in molti casi l'oggetto stringa non ha blocco sull'archivio per contenere i dati effettivi.

Answer 5

I riferimenti di stringa sono memorizzati in un'unica posizione. Le stringhe possono essere memorizzate ovunque nella memoria. Quindi, hai ancora O (1) tempo di accesso casuale.

--------------------------- 
| 4000 | 4200 | 5000 | 6300 | <- data 
--------------------------- 
[1000] [1004] [1008] [1012] <- address 


[4000] [4200] [5000]  [6300]  <- starting address 
"string1" "string2" "string3" "string4" <- string