c++, ¿puedes decirme algo sobre vectores y mapeo?
1. Vectores y matrices dinámicas
(1) Los vectores tienen operaciones de expansión automática, y cada expansión va acompañada de la operación de "asignar nuevo espacio/mover datos antiguos/liberar espacio antiguo". " , por lo que hay un cierto costo de tiempo.
(2) Vector proporciona una interfaz reservada. Si puede tener una idea aproximada de la cantidad de elementos, puede asignar el espacio apropiado al principio.
(3) El espacio de memoria del vector es continuo. Para la operación de inserción de elementos, insertar al final del vector es una opción adecuada.
(4) Para la operación de insertar elementos, insertar al final del vector es una opción adecuada.
(4) Cuando el tamaño de un vector aumenta dinámicamente, no continúa después del espacio original (no hay garantía de que habrá espacio libre después del espacio original), sino que asigna un espacio más grande con el tamaño es el doble del espacio original, luego copia el contenido original y comienza a construir nuevos elementos después del contenido original, liberando el espacio original. Por lo tanto, cualquier operación vectorial que resulte en una reconfiguración espacial invalida todos los iteradores del vector original.
2. La diferencia entre vectores y matrices
Los vectores y las matrices son muy similares. Las matrices son espacios estáticos que no se pueden cambiar una vez configurados; los vectores son espacios dinámicos y, a medida que se agregan elementos, su mecanismo interno expande el espacio para acomodar nuevos elementos. Por tanto, el uso de vectores es de gran ayuda para la utilización racional y el uso flexible de la memoria.
La estructura de datos utilizada es muy sencilla: espacio lineal continuo. Para minimizar el costo de velocidad al asignar espacio, el tamaño real del vector se puede configurar un poco más grande que las necesidades del cliente para permitir una posible expansión futura. Este es el concepto de capacidad. Este es el concepto de capacidad. Al agregar un nuevo elemento, si la capacidad es insuficiente, amplíelo al doble del tamaño original (si el tamaño original es 0, configúrelo en 1), si 2 veces el tamaño original aún es insuficiente, amplíelo a un tamaño lo suficientemente grande capacidad.
2. Características de la lista
(1) En comparación con el espacio lineal continuo de vectores, la lista es mucho más compleja.
(2) Su ventaja es que cada vez que se inserta o elimina un elemento, se asignará o liberará espacio para un elemento.
(2) La ventaja de una lista es que asigna o libera espacio para un elemento cada vez que se inserta o elimina un elemento. Como resultado, las listas utilizan el espacio con absoluta precisión y sin desperdicio alguno.
(3) El tiempo de una lista siempre es constante para cualquier elemento insertado o eliminado en cualquier posición.
(4) La lista no es solo una lista doblemente enlazada, sino también una lista circular doblemente enlazada. Solo requiere un puntero para representar completamente toda la lista vinculada.
(5) Ni las operaciones de inserción ni de unión hacen que el iterador de la lista original sea invalidado, lo cual no ocurre en los vectores. Porque la operación de inserción del vector puede provocar la reconfiguración de la memoria, lo que hace que todos los iteradores originales dejen de ser válidos. Incluso si se realiza una operación de borrado en la lista, solo invalidará el iterador que "apunta al elemento eliminado" y otros iteradores no se verán afectados de ninguna manera.
(6) Las listas ya no pueden usar punteros ordinarios como iteradores como vectores, porque no se garantiza que sus nodos sean continuos en el espacio de almacenamiento.
Las listas proporcionan iteradores bidireccionales.
slist
La diferencia entre lista y lista:
(1) La lista STL es una lista doblemente vinculada, mientras que slist es una lista simplemente vinculada.
(2) El iterador de la lista STL es un iterador bidireccional, mientras que el iterador de la lista es un iterador directo unidireccional.
(3) Las listas enlazadas unidireccionales ocupan menos espacio y algunas operaciones son más rápidas.
(4) Ambos tienen la misma característica: operaciones como inserción, borrado y empalme no harán que el iterador grueso falle. (Después de la operación de eliminación, ¿el iterador que apunta al elemento eliminado definitivamente dejará de ser válido)?
(5) Dado que una lista enlazada individualmente solo puede iterar hacia adelante, no se pueden proporcionar muchas operaciones, e incluso si se proporcionan estas operaciones, son operaciones ineficientes para atravesar desde el nodo principal.
No es aconsejable utilizar la función de inserción o borrado en cualquier otra posición excepto en el área cercana al principio de la lista. Esta es también la mayor desventaja de las listas en comparación con slist.
(6) El iterador slist es un iterador directo unidireccional, por lo que además de las operaciones básicas del iterador, solo se implementa la operación del operador ++.
deque
1. La diferencia entre deque y vector
(1) el vector es un espacio lineal continuo abierto unidireccional, el usuario solo puede ingresar en el final del vector Realice operaciones de inserción y eliminación (también se permite la inserción en una determinada posición, pero dado que la implementación subyacente del vector es una matriz, demasiadas inserciones en posiciones distintas al final de la cola provocarán un consumo de rendimiento). Un deque es un espacio lineal continuo con aberturas bidireccionales, que permite operaciones de inserción y eliminación en la cabeza y la cola, respectivamente.
(2) deque permite la inserción o eliminación de elementos principales en tiempo constante.
(3) deque no tiene concepto de capacidad. Se ensambla dinámicamente con segmentos espaciales continuos y se pueden agregar y conectar nuevos segmentos espaciales en cualquier momento. Por lo tanto, no es necesario proporcionar la denominada función de reserva de espacio (reserva).
(4) La tarea más importante de deque es mantener la ilusión de continuidad general en estos espacios continuos cuantitativos segmentados y proporcionar una interfaz de acceso aleatorio. Esto evita el ciclo de "reconfigurar, copiar, liberar", pero a costa de una arquitectura de iterador compleja.
(5) Dado que es un espacio lineal continuo por partes, debe tener un control centralizado y, para mantener la ilusión de continuidad general, el diseño de la estructura de datos y las operaciones frontal y posterior del iterador son bastante engorrosos. El código de implementación de deque es mucho más que el de vector o lista.
2. El controlador central de Deque
Deque utiliza un llamado mapa (nota, no el contenedor de mapas STL) como control principal. El llamado mapeo aquí es un pequeño espacio continuo, en el que cada elemento (aquí llamado nodo) es un puntero a otro espacio lineal continuo (más grande) (llamado búfer). El buffer es el cuerpo principal del espacio de almacenamiento deque. SGI STL nos permite especificar el tamaño del búfer, con un valor predeterminado de 0, lo que significa que se utilizará un búfer de 512 bytes.
Resumen:
(1) Un mapa es un bloque de espacio contiguo en el que cada elemento es un puntero a un búfer.
(2) Descubrimos además que el mapa es en realidad un T**, es decir, es un puntero que apunta a un puntero a un espacio de tipo T.
3. Iterador Deque
Deque es un espacio continuo segmentado. La tarea de mantener la ilusión de continuidad recae en el operador++ y el operador-operadores del iterador.
¿Cómo debería ser la estructura del iterador deque?
(1) ¿Debe poder señalar la ubicación del espacio continuo segmentado (es decir, buffer)?
(2) Debe poder determinar si ya está en el borde del búfer en el que se encuentra. Si es así, debe saltar al búfer siguiente o anterior después de avanzar o retroceder. Para saltar correctamente, el deque siempre debe realizar un seguimiento del centro de control (mapa).
Entonces necesitas definir en el iterador: un puntero al elemento actual, un puntero al inicio del búfer donde está el elemento actual, un puntero al final del búfer donde está el elemento actual y un puntero al búfer en el mapa donde está el puntero a la dirección del área.
Deque no es tan eficiente como vector, por lo que al ordenar un deque, a veces es necesario mover elementos al vector antes de ordenar y luego moverlos hacia atrás.
4. Construcción de Deque y gestión de memoria
Dado que deque está diseñado para conectar cachés a través de bloques, su gestión de memoria será más compleja. Al insertar, debe considerar si saltar al caché y si crear un nuevo nodo de mapeo (para los vectores, en realidad es reasignar un espacio para el mapeo y eliminar el espacio original Después de insertar, si se debe mover el elemento anterior hacia adelante). o para mover el siguiente elemento El elemento se mueve hacia atrás (quien lo mueva más pequeño).
Al eliminar un elemento, debe considerar si mover el elemento frontal hacia atrás para cubrir el lugar donde se debe eliminar el elemento o mover el elemento trasero hacia adelante para cubrirlo (quien mueva el más pequeño). Una vez completado el traslado, se deben destruir los elementos redundantes y liberar las cachés redundantes.
4. Pila
La pila es una estructura de datos de primero en entrar, primero en salir con una sola salida. Permite agregar elementos, eliminar elementos y obtener el elemento superior. No se permite el comportamiento transversal.
En el diseño del código fuente
la pila no proporciona funcionalidad transversal ni iteradores.
5. cola
la cola es una estructura de datos de primero en entrar, primero en salir. Dispone de dos salidas que permiten añadir, quitar elementos, unir por la parte inferior y sacar el elemento superior. No se permite el comportamiento transversal.
Deque es una cola bidireccional, mientras que queue es una cola unidireccional.
Una deque es una estructura de datos bidireccional, por lo que puede formar fácilmente una cola si usa una deque como estructura subyacente y cierra las salidas subyacentes y las entradas de front-end.
La cola no proporciona recorrido ni iteradores.
Mapa y multimapa
Características del mapa:?
(1) Todos los elementos se ordenarán automáticamente según el valor clave del elemento.
(2) Todos los elementos del mapa están en pares, donde el primer valor es el valor clave y el segundo valor es el valor real.
(3) el mapa no permite que dos elementos tengan el mismo valor clave.
(4) Puede cambiar el valor real del elemento a través del iterador del mapa, pero no puede cambiar el valor clave; de lo contrario, violará las reglas de disposición de los elementos.
(5) Después de que el cliente realiza una operación de inserción o eliminación en el mapa, el iterador anterior sigue siendo válido. Excepto, por supuesto, los iteradores de elementos eliminados.
(6) El mecanismo subyacente es el árbol RB, y casi todas las operaciones son rellamadas de operaciones del árbol RB.
Multimapa y mapa son casi iguales, la única diferencia es que multimapa permite valores clave duplicados. Por lo tanto, el mapa usa insert_unique() del árbol RB subyacente para implementar la inserción, mientras que la inserción de multimap usa insert_equal() del árbol RB en lugar de insert_unique().
hashtable
1. Descripción general de hashtable
Hashtable puede proporcionar operaciones de acceso y eliminación a cualquier elemento con nombre. El propósito de esta estructura es proporcionar tiempo básico. constante La operación, y no depende de la aleatoriedad de los elementos insertados, se basa en estadísticas.
Función hash (función hash): Responsable de mapear elementos a "índices de tamaño aceptable". En resumen, asigna números grandes a decimales.
El problema con el uso de funciones hash: puede haber diferentes elementos mapeados en la misma posición (mismo índice). Éste es el problema de la colisión o el conflicto. Los métodos para resolver el problema de colisión incluyen: detección lineal, detección secundaria, cadena de separación, etc.
(1) Detección lineal: después de que la función hash calcula la posición de inserción del elemento, el espacio de posición ya no está disponible. El método más sencillo es buscar uno a uno en orden hasta encontrar un espacio disponible.
Se requieren dos supuestos: a. La tabla es lo suficientemente grande. b. Cada elemento puede ser independiente.
El sondeo lineal puede conducir al principal problema de agrupación: el coste medio de inserción aumenta mucho más que el factor de carga.
(2) Detección secundaria: se utiliza principalmente para resolver problemas de agrupamiento primario. La ecuación que resuelve la colisión es F(i) = i^2. Si la función hash calcula que la posición del nuevo elemento es H, y la posición realmente se usa, pruebe con H+1^2, H+2^2, H+3^2, H+4^2,... ,H+i^2, que es diferente de los intentos de sondeo lineal H+1, H+2, H+3, H+4, ....
H+i.
La agrupación secundaria puede eliminar la agrupación primaria, pero también puede causar agrupación secundaria: si la posición de dos elementos es la misma que la posición calculada por la función hash, se insertarán en la mismo lugar detectado, provocando así algún tipo de residuo. La forma de eliminar la agrupación secundaria es utilizar hash complejo.
(3) Cadena abierta: este enfoque consiste en mantener un elemento de lista en cada formulario. La función hash nos asigna una determinada lista y luego realizamos operaciones como insertar, buscar, eliminar elementos de esa lista. Si la lista es lo suficientemente corta, sigue siendo lo suficientemente rápida.
La tabla hash SGI STL utiliza una lista enlazada abierta.
Para obtener más información sobre C++, visite mi blog: enlaces web.