Como todos estamos usando STL bastante en nuestros programas en entrevistas, concursos de codificación. Por lo tanto, conocer la complejidad del tiempo de la operación utilizada con más frecuencia y la estructura de datos utilizada detrás de escena (en la implementación interna de la biblioteca STL) es una información imprescindible.
Contenedores C++ STL con complejidad de tiempo y estructura de datos utilizados detrás de escena:
|
S. No. |
Nombre del contenedor STL |
Estructura de datos internos |
Complejidad del tiempo |
|---|---|---|---|
|
1. |
Conjunto desordenado | Tabla hash (una tabla hash utiliza una función hash para calcular un índice) |
Para Insertar, Buscar, Eliminar: Mejor: O(1) Promedio: O(1) Peor: O(N) |
|
2. |
Establecer | Red Black Tree (árbol de búsqueda binario autoequilibrado: mantiene la altura del registro del árbol N) |
Para Insertar, Buscar, Eliminar: Mejor: O(log N) Promedio: O(log N) Peor: O(log N) |
|
3. |
Mapa desordenado | Tabla hash (una tabla hash utiliza una función hash para calcular un índice) |
Para Insertar, Buscar, Eliminar: Mejor: O(1) Promedio: O(1) Peor: O(N) |
|
4. |
Mapa | Red Black Tree (árbol de búsqueda binario autoequilibrado: mantiene la altura del registro del árbol N) |
Para Insertar, Buscar, Eliminar: Mejor: O(log N) Promedio: O(log N) Peor: O(log N) |
|
5. |
Priority_queue | Montón máximo | Insertar/Pulsar: O(registro N) Eliminar/Abrir: O(registro N) Peek/Superior: O(1) |
|
6. |
Pila | Lista enlazada | Pulsar: O(1) Pop: O(1) Superior: O(1) |
|
7. |
Cola | Lista enlazada | Pulsar: O(1) Pop: O(1) Frente: O(1) Atrás: O(1) |
Esta es una especie de tabla de búsqueda para conocer la Complejidad de tiempo de cada operación , la breve razón se puede interpretar rápidamente a partir de la Estructura de datos utilizada para implementar internamente el contenedor en C++ STL.
También a partir de las Complejidades de Tiempo de cada operación, podemos calcular fácilmente la Complejidad de Tiempo de todo el programa.