std :: string y su cambio de tamaño automático de memoria

Question

Estoy bastante nuevo en C ++, pero sé que no se puede simplemente utilizar la memoria queramos o no, como la clase std :: string parece dejar que hagas. Por ejemplo:

std::string f = "asdf";
f += "fdsa";

¿Cómo funciona el mango clase string aumentando y disminuyendo? Asumo que asigna una cantidad predeterminada de memoria y si necesita más, news un bloque más grande de memoria y copia a sí mismo más a eso. Pero no que sea muy ineficiente tener que copiar toda la serie cada vez que necesitaba para cambiar el tamaño? Realmente no puedo pensar en otra manera se podría hacer (pero obviamente alguien lo hizo).

Y para el caso, ¿cómo todas las clases stdlib como vector, cola, pila, etc mango crecimiento y la contracción de modo transparente?

Answer 1

Por lo general, hay un algoritmo de duplicación. En otras palabras, cuando se llena el búfer en uso, se asigna un nuevo búfer que es el doble de grande, y luego copia los datos actuales sobre. Este resultado en menos asignan / operaciones de copia que la alternativa de crecimiento por un solo bloque de asignación.

Answer 2

Su análisis es correcto - es es ineficiente para copiar la cadena cada vez que se necesita para cambiar el tamaño. Es por eso que desalienta consejos comunes que el uso de patrones. Usar reserve función de la cadena para pedirle que asignar suficiente memoria para lo que intención para almacenar en ella. A continuación, otras operaciones que llenarán la memoria. (Pero si su sugerencia resulta ser demasiado pequeño, la cadena sigue creciendo de forma automática, también.)

Los contenedores también suele tratar de mitigar los efectos de repetir con frecuencia la asignación mediante la asignación de más memoria de la que necesitan. Un algoritmo común es que cuando una cadena hallazgos que está fuera del espacio, dobles su tamaño del búfer en lugar de sólo la asignación del mínimo requerido para mantener el nuevo valor. Si la cadena se está cultivando un carácter a la vez, este algoritmo duplicar reduce la complejidad vez en cuando lineal amortizado (en lugar de tiempo cuadrática). También reduce la susceptibilidad del programa para la fragmentación de memoria.

Answer 3

A pesar de que no sé la aplicación exacta de std :: string, la mayoría de las estructuras de datos que necesita para manejar el crecimiento de memoria dinámica hacerlo haciendo exactamente lo que dice - asignar una cantidad predeterminada de memoria, y si se necesita más a continuación, crear un bloque más grande y copia a sí mismo de nuevo.

La forma de evitar el problema ineficiencia obvia es asignar más memoria de la que necesita. La proporción de memoria utilizada: la memoria total de un vector / secuencia / lista / etc a menudo se llama el factor carga (también se utiliza para las tablas hash en un sentido ligeramente diferente). Por lo general, se trata de una relación de 1: 2 - es decir, se asigna el doble de memoria que necesita. Cuando se queda sin espacio, se asigna una nueva cantidad de memoria dos veces su cantidad actual y el uso de eso. Esto significa que con el tiempo, si continúa a añadir cosas al vector / secuencia / etc, tiene que copiar el elemento cada vez menos (como la creación de memoria es exponencial, y su inserción de nuevos elementos es por supuesto lineal), por lo que el tiempo necesario para que esta forma de manipulación de memoria no es tan grande como se podría pensar. Por los principios de Análisis de amortización , a continuación, puede ver que la inserción de artículos m en un vector / secuencia / lista usando este método sólo es Big-Theta de m, m no ² .