Diccionario de acceso aleatorio
El conjunto y el mapa son elementos de almacenamiento desordenados y solo se puede acceder a los elementos internos a través de las interfaces que proporcionan.
Conjunto: Conjunto,
Se utiliza para determinar si un elemento está en un grupo, rara vez se usa.
Mapeo: El mapeo es equivalente a un diccionario, asignando un valor a otro valor. Puedes usarlo si quieres crear un diccionario.
La capa inferior adopta una estructura de árbol, la mayoría de las cuales se implementan mediante árboles binarios equilibrados. El tiempo para encontrar un determinado valor es constante y el efecto transversal es bueno.
Solo cada vez que se inserta un valor, se reconstruirá el árbol binario equilibrado inferior, lo que tiene un cierto impacto en la eficiencia.
Cadenas, vectores, listas, colas y conjuntos son contenedores ordenados.
1.string
La cadena es _ cadena básica
"abcd", entonces el espacio utilizado por S puede ser 255.
Cuando la cadena vuelve a agregar contenido a S, la memoria no se volverá a asignar hasta el contenido>; la memoria se aplicará nuevamente a las 255 horas, mejorando así su rendimiento.
Cuando el contenido>; en 255, la cadena primero asignará una nueva memoria, luego copiará el contenido y luego copiará el contenido anterior.
Para operaciones de cadena, si agrega al final, generalmente no hay necesidad de asignar memoria, por lo que el rendimiento es el más rápido
Si opera en la parte intermedia o inicial; , como agregar o eliminar elementos, o reemplazar elementos, requieren copiar memoria y el rendimiento se reducirá.
Si eliminas un elemento, string no libera la memoria que asignó, lo que lo hace más eficiente la próxima vez que se use.
Debido a que la cadena tendrá memoria reservada, si se usa en grandes cantidades, habrá un desperdicio de memoria, lo cual debe tenerse en cuenta. Además, es necesario considerar no liberar demasiada memoria al momento de eliminar elementos.
La memoria en la cadena se asigna en el montón, por lo que la longitud de la cadena puede ser muy grande, mientras que char[] se asigna en la pila y su longitud está limitada por la longitud máxima de la pila que puede ser usado.
Si conoce la longitud máxima de la cadena que se utilizará, puede utilizar char[] normal en lugar de cadena.
Utilice cadenas cuando la longitud de la cadena sea desconocida o varíe mucho.
Si la cadena se agrega y elimina varias veces, su tamaño será mucho menor que el valor máximo. Para reducir el tamaño de la cadena puedes usar:
String s =
"abcdefg";
String y(s); // Porque cuando la memoria Si se asigna nuevamente, Y solo asignará memoria mayor que S, por lo que el desperdicio no será enorme.
Intercambio estándar (y);
//Reduce la memoria utilizada por s.
Si tienes suficiente memoria, no tienes que preocuparte por esto.
La capacidad es una función que comprueba la memoria utilizada actualmente.
Puede intentar asignar el valor de retorno después de la capacidad cadena por cadena y el valor de retorno después de otras operaciones.
2. Vector
Un vector es una matriz dinámica. También asigna memoria en el montón. Los elementos se almacenan de forma contigua y tienen memoria reservada. Si reduce el tamaño, la memoria no se liberará. Si el nuevo valor > la memoria no se asignará hasta el tamaño actual.
Tiene un espacio de memoria continuo y su dirección inicial es la misma, por lo que puede admitir acceso aleatorio, es decir, el operador []. Sin embargo, dado que su espacio de memoria es continuo, las inserciones y eliminaciones intermedias provocarán la copia de bloques de memoria. Además, cuando el espacio de memoria detrás de la matriz no es suficiente, debe volver a solicitar una memoria lo suficientemente grande y copiarla. Estos afectan en gran medida la eficiencia del vector.
La operación en el último elemento es la más rápida (la adición y eliminación posteriores son las más rápidas).
En este momento, normalmente no es necesario mover la memoria, solo cuando la memoria reservada no es suficiente.
Agregar y eliminar elementos en el medio y al principio requiere mover memoria. Si sus elementos son estructuras o clases, se construirán y destruirán al mismo tiempo, por lo que el rendimiento no es alto.
Es mejor colocar el puntero de la estructura o clase en el vector en lugar de la estructura o clase en sí, para evitar la construcción y destrucción al moverse.
En términos de acceso, el acceso a cualquier elemento es O(1), que es una constante, por lo que el vector se utiliza a menudo para contener contenido que requiere acceso aleatorio frecuente y no requiere la adición o eliminación frecuente de elementos intermedios.
En comparación, podemos ver que las propiedades del vector son similares a las de la cadena, y también podemos usar capacidad para ver la memoria actualmente reservada e intercambiar para reducir la memoria que usa.
Resumen
Si necesita acceso aleatorio frecuente, utilice el vector
3. Lista
La lista es una lista doblemente enlazada y los elementos también se almacenan en el montón. Cada elemento se coloca en un fragmento de memoria y su espacio de memoria puede ser discontinuo. El acceso a los datos a través de punteros hace que el acceso aleatorio sea muy ineficiente, por lo que no sobrecarga el operador []. Sin embargo, debido a las características de la lista vinculada, puede admitir la eliminación e inserción en cualquier lugar y es muy eficiente.
La lista no tiene la costumbre de reservar espacio, por lo que cada elemento asignado se asignará desde la memoria y cada elemento eliminado liberará la memoria que ocupaba.
List tiene un alto rendimiento a la hora de agregar y eliminar elementos desde cualquier lugar y no requiere mover memoria. Por supuesto, no requiere la construcción y destrucción de cada elemento, por lo que a menudo se utiliza como contenedor de operaciones aleatorias.
Pero al acceder a elementos de una lista, el primer y último acceso son los más rápidos.
El acceso a otros elementos es O(n)
Así que si necesitas acceso aleatorio frecuente, será mejor que utilices otro.
Resumen
Si desea agregar y eliminar objetos grandes con frecuencia, utilice una lista.
El objeto a guardar no es grande y las operaciones de construcción y destrucción no son complicadas. En su lugar, se puede utilizar Vector.
List & lt pointer> es el rendimiento más bajo. En este caso, es mejor usar vector, porque los punteros no se construyen ni destruyen y no ocupan demasiada memoria.
4. Deque
double es una cola de dos extremos), que también guarda el contenido en el montón. El formato de almacenamiento es el siguiente:
[Heap 1]
...
[Heap 2]
...< /p >
[Montón 3]
Cada montón guarda varios elementos y luego hay un puntero entre el montón y el montón. Parece una combinación de una lista y un vector, pero es así. es verdad.
Deque le permite agregar y eliminar elementos rápidamente en el frente, o agregar y eliminar elementos rápidamente en la parte posterior, y luego puede tener una velocidad de acceso aleatorio relativamente alta.
Admite el operador [], es decir, admite acceso aleatorio, lo que le permite agregar y eliminar rápidamente elementos delante o detrás, y luego puede tener una velocidad de acceso aleatorio relativamente alta, que es casi lo mismo que el vector. La eficiencia es la misma. Admite operaciones en ambos extremos: push_back, push_front, pop_back, pop_front, etc. , la eficiencia de las operaciones en ambos extremos es similar a la de la lista.
En la biblioteca estándar, vector y deque proporcionan casi la misma interfaz. La diferencia estructural entre ellos es que los dos contenedores organizan la memoria de manera diferente. Un deque asigna memoria en páginas o bloques, y cada página contiene un número fijo de elementos. Por el contrario, el vector asigna memoria contigua y solo es válido cuando se inserta un elemento al final de la secuencia. La organización paginada de Deque puede incluso proporcionar operaciones de inserción y borrado en tiempo constante en la parte frontal del contenedor, y es más eficiente en el crecimiento del volumen que el vector.
Resumen:
Vector puede agregar y eliminar elementos rápidamente al final y proporcionar acceso rápido a cualquier elemento.
La lista puede agregar y eliminar elementos rápidamente en cualquier lugar, pero solo se puede acceder rápidamente al primer y último elemento.
Deque agrega elementos tan rápido como al principio y al final, y proporciona un método de acceso aleatorio. Al igual que el vector, utiliza [] para acceder a cualquier elemento, pero el acceso aleatorio no es tan rápido como el vector porque tiene que manejar los saltos del montón internamente.
Deque también tiene espacio reservado. Además, dado que deque no requiere espacio continuo, puede guardar más elementos que vector, lo cual también debe tenerse en cuenta. Además, al agregar elementos antes y después, no es necesario mover elementos de otros bloques, por lo que el rendimiento también es alto.
Por lo tanto, en el uso real, la forma de elegir cuál de estos tres contenedores debe determinarse según sus necesidades y, en general, se deben seguir los siguientes puntos.
Principios:
1. Si necesita un acceso instantáneo eficiente, independientemente de la eficiencia de la inserción y eliminación, utilice vector.
2. Si necesita muchas inserciones y eliminaciones y no le importa el acceso inmediato, debe utilizar una lista.
3. Si necesita acceso inmediato y se preocupa por la inserción y eliminación de datos en ambos extremos, debe utilizar deque.