¿Es std :: string size () una operación O (1)?

Question

¿Es std :: string size () una operación O (1)?

La implementación de STL que estoy usando es la integrada en VC ++

Answer 1

Si pregunta si la implementación de string :: size () de MSVC tiene una complejidad constante, entonces la respuesta es sí. Pero Don Wakefield mencionó la Tabla 65 en 23.1 de la Norma C ++ donde dice que la complejidad de size () debe seguir lo que se dice en la 'Nota A'. La nota A dice:

  

Esas entradas marcadas ‘‘ (Nota A) ’’   debe tener una complejidad constante.

Sin embargo, eso no significa que esas entradas deberán tener una complejidad constante. Los estándares utilizan una terminología muy específica, y " debería " significa que no es obligatorio.

'Nota A' se agregó a la norma específicamente para apaciguar a aquellos que creían que se debería permitir que size () tenga una complejidad lineal, por lo que no sería necesario mantener el tamaño cuando los contenedores estaban modificado.

Por lo tanto, no puede confiar en que size () tenga una complejidad constante, pero honestamente no estoy seguro de que haya implementaciones que no tengan una cadena de constante :: tamaño ( ) .

Answer 2

Aquí hay una manera fácil de responder esa pregunta para msvc ++.

Escribir un código en un proyecto:

string happy;
happy.size();

Encienda la llamada .size, haga clic con el botón derecho, vaya a definición.

En mi instalación (vs2005sp1) esto me envía a xstring: 1635, que se ve así:

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

Así que parece que la cadena tiene un miembro llamado _Mysize, y simplemente está devolviendo eso.

En otras palabras, esta es una implementación O (1).

Answer 3

Sí, std :: string :: size () es O (1).

Answer 4

Consulte la Tabla 65 en la Sección 23.1 de la Norma. " a.size () " aparece en la lista como "(Nota A)", que dice que "esas entradas ... deben tener una complejidad constante".

La Sección 21.3 dice que las cadenas se ajustan a los requisitos de una secuencia (23.1), ipso facto, size () es tiempo constante.

Answer 5

Para una cadena, la operación size () debe ser constante para todas las implementaciones de cadenas que no usan ropes ⁽¹⁾ . No hay un requisito explícito en el estándar que requiera que la operación sea O (1) , el más cercano es el requisito genérico de que size () debería sea tiempo constante, pero eso deja espacio para cualquier otra medida de complejidad.

Entonces, ¿por qué debe ser O (1)?

Esto proviene del hecho de que el tamaño no puede calcularse a partir del contenido de la cadena en sí. Mientras que en C usas un terminador NUL para determinar el final de la cadena, en C ++ NUL es tan válido como cualquier otro carácter en la cadena. Dado que el tamaño de la cadena no puede calcularse a partir del contenido ⁽²⁾ , debe manejarse externamente, independientemente del tamaño real de la cadena.

⁽¹⁾ C ++ 03 estándar permite que una implementación use cuerdas como implementación para cadenas, pero el hecho es que ninguna de las implementaciones actuales del estándar las bibliotecas los usan.

⁽²⁾ Si la implementación usara cuerdas, la operación podría depender del tamaño por medio del número de bloques a partir de los cuales se construyó la cuerda si los bloques se vinculan a través de una lista vinculada Construir, o si se les permitiera tener diferentes tamaños. Pero las cuerdas no se usan en ninguna implementación de biblioteca estándar que yo sepa.

Answer 6

El STL garantiza que el rendimiento sea al menos O (N) para los contenedores, sin embargo, muchos contenedores que incluyen std :: string pueden implementar esto como O (1) y lo harán. Por lo general, devolverá una variable simple o hará algo como _End - _Begin y devolverá eso.

Answer 7

size_type __CLR_OR_THIS_CALL size() const

{   // return length of sequence

    return (_Mysize);

}

Entonces eventualmente podría ser así, pero nunca puedes estar seguro.