C++: ¿Cómo funciona el tiempo de acceso aleatorio de los vectores de cadena?

Question

Sé que un vector int simple tiene O (1) tiempo de acceso aleatorio, ya que es fácil calcular la posición del elemento xth, dado que todos los elementos tienen el mismo tamaño.

Ahora, ¿qué pasa con un vector de cadena?

Dado que las longitudes de cadena varían, no puede tener O (1) tiempo de acceso aleatorio, ¿o sí? Si puede, ¿cuál es la lógica detrás de esto?

Gracias.

Actualización:

Las respuestas son muy clara y concisa, gracias a todos por la ayuda. Acepté la respuesta de Joey porque es simple y fácil de entender.

Answer 1

El vector tiene O (1) tiempo de acceso.

Los objetos de cadena son todos del mismo tamaño (en una implementación dada), independientemente del tamaño de la cadena que representan. Normalmente, el objeto de cadena contiene un puntero a la memoria asignada que contiene los datos de cadena.

lo tanto, si s es una std::string, entonces sizeof s es constante e igual a sizeof(std::string), pero s.size() depende del valor de la cadena. El vector solo se preocupa por sizeof(std::string).

Answer 2

Porque el objeto de cadena tiene un tamaño fijo al igual que cualquier otro tipo. La diferencia es que el objeto cadena almacena su propia cadena en el montón, y mantiene un puntero a la cadena que se fija en el tamaño.

Answer 3

La cadena real en una std :: cadena es generalmente solo un puntero. El tamaño de una cadena es siempre el mismo, incluso si la longitud de la cadena que contiene varía.

Answer 4

Has obtenido varias respuestas (por ejemplo, Steve Jessop y AraK) que ya son en su mayoría correctas. Agregaré solo un pequeño detalle: muchas implementaciones actuales de std::string usan lo que se llama optimización de cadenas cortas (SSO), lo que significa que asignan una pequeña cantidad de espacio fijo en el objeto de cadena que se puede usar para almacenar cadenas cortas. , y solo cuando/si la longitud excede lo asignado en el objeto de cadena en sí mismo, en realidad asigna espacio separado en el montón para almacenar los datos.

En lo que respecta al vector de cadenas, esto no supone una diferencia real: cada objeto de cadena tiene un tamaño fijo independientemente de la longitud de la cadena. La diferencia es que con SSO ese tamaño fijo es mayor, y en muchos casos el objeto de cadena no tiene un bloque asignado en el montón para contener los datos reales.

Answer 5

Las referencias de cadena se almacenan en una ubicación. Las cadenas se pueden almacenar en cualquier lugar de la memoria. Entonces, todavía obtienes O (1) tiempo de acceso aleatorio.

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


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