C++ es uno de los lenguajes más recomendados en la programación competitiva (consulte nuestro artículo anterior para conocer el motivo)
C++ STL contiene muchos contenedores que son útiles para diferentes propósitos. En este artículo, nos vamos a centrar en los contenedores más importantes desde el punto de vista de la programación competitiva y la preparación de entrevistas.
vector : (#include<vector>) Array de tamaño dinámico que permite inserciones y eliminaciones sin importar el tamaño de la array. También tiene las ventajas de las arrays simples, como el acceso aleatorio y la compatibilidad con la memoria caché. El vector C++ admite muchas operaciones adicionales como erase(), push_front(), insert(), etc.
queue : (#include<queue>) Útil en situaciones en las que deseamos tener un orden FIFO de elementos. Los problemas de ejemplo son, generar números con un dígito dado , el primer carácter que no se repite en una secuencia , el orden de nivel transversal de un árbol y sus variaciones, BFS de un gráfico y sus variaciones. Consulte los problemas de práctica de la cola para obtener más práctica.
stack : (#include<stack>) Usado en situaciones donde deseamos tener orden LIFO. Los problemas de ejemplo son el paréntesis equilibrado , el problema de stock span , el siguiente elemento mayor y el área más grande en un histograma . Consulte los problemas de práctica de Stack para obtener más práctica.
set y map : (#include<set> y #include<map>) Ambos implementan un árbol de búsqueda binaria autoequilibrado ( Red Black Tree en particular). Útil en situaciones en las que deseamos mantener elementos ordenados con un tiempo de búsqueda, inserción y eliminación moderado (mejor que array y peor que hashing). Los problemas de ejemplo son, el valor más cercano mayor o igual en el lado izquierdo , encontrar el valor más cercano para cada elemento en una array , etc. Usamos set cuando deseamos almacenar solo claves y map cuando deseamos almacenar pares de valores clave.
unordered_set y unordered_map :(#include<unordered_set> and #include<unordered_map>) Ambos implementan hashing con enstringmiento. Útil cuando deseamos tener una búsqueda rápida, insertar y borrar (las tres operaciones son O(1)). Esta es una de las estructuras de datos más utilizadas en la industria y más subestimada en el mundo académico. Hay muchos problemas populares, contar elementos distintos , frecuencias de elementos de array , subarreglo con suma 0 y unión e intersección de dos arrays no ordenadas . Consulte Problemas de práctica de hashing para obtener más práctica .
cola_de_prioridad : (#include<cola_de_prioridad>) Implementa Max Heap de forma predeterminada. También podemos crear un Min Heap . Se utiliza siempre que deseemos encontrar eficientemente el elemento mínimo o máximo. Se utiliza para implementar algoritmos populares como el algoritmo de Prim, la ruta más corta de Dijkstra , la codificación de Huffman , los elementos más grandes de K , la cantidad máxima de juguetes para comprar y fusionar arrays ordenadas de K , la mediana de un flujo . Consulte Problemas de práctica de montones para obtener más práctica.
deque : (#include<deque> Dequeue admite inserciones y eliminaciones en ambos extremos en tiempo O(1). Dado que se implementa usando una array, también permite el acceso aleatorio. Podemos usar dequeue para implementar Queue y Stack. Problemas de ejemplo en Deque son, visitar todos los surtidores de gasolina y los máximos de todos los subarreglos de tamaño k .
Cubriremos bibliotecas de C++ más importantes en la siguiente parte de este artículo.