programas - ¿Por qué los montones en c++ se implementan como algoritmos en lugar de contenedores?
manual completo de c++ pdf (5)
Bueno, los montones no son realmente un contenedor genérico en el mismo sentido que un conjunto o un mapa. Por lo general, usa un montón para implementar algún otro tipo de datos abstractos. (El más obvio es una cola de prioridad.) Sospecho que esta es la razón del tratamiento diferente.
Me preguntaba por qué el concepto de montón se implementa como algoritmos ( make_heap , pop_heap , push_heap , sort_heap ) en lugar de un contenedor. Estoy especialmente interesado es que la solución de alguien también puede explicar por qué set y map son contenedores en lugar de colecciones similares de algoritmos (make_set add_set rm_set, etc.).
Los montones * casi siempre se implementan utilizando una matriz como la estructura de datos subyacente. Como tal, se puede considerar un conjunto de algoritmos que operan en la estructura de datos de matriz. Esta es la ruta que tomó el STL al implementar el montón: funcionará en cualquier estructura de datos que tenga iteradores de acceso aleatorio (una matriz estándar, vector, deque, etc.).
También notará que STL priority_queue requiere un contenedor (que de forma predeterminada es un vector). Este es esencialmente su contenedor de montón: implementa un montón en su estructura de datos subyacente y proporciona un contenedor contenedor para todas las operaciones de montón típicas.
* Montones binarios en particular. Otras formas de montones (Binomial, Fibonacci, etc.) no lo son.
STL proporciona un montón en forma de std :: priority_queue. Las funciones make_heap, etc. están ahí porque tienen usos fuera del ámbito de la propia estructura de datos (por ejemplo, clasificación), y para permitir que montones de montones se construyan sobre estructuras personalizadas (como matrices de pila para un "keep the top 10" envase).
Por analogía, puede usar un std :: set para almacenar una lista ordenada, o puede usar std :: sort en un vector con std :: adjacent_find; std :: sort es el más general y hace pocas suposiciones sobre la estructura de datos subyacente.
(Como nota, la implementación std :: priority_queue en realidad no proporciona su propio almacenamiento, por defecto crea un std :: vector como su almacén de respaldo).
Un montón es una estructura de datos específica. Los contenedores estándar tienen requisitos de complejidad pero no especifican cómo se implementarán. Es una distinción fina pero importante. Puede make_heap en varios contenedores diferentes, incluido uno que usted mismo haya escrito. Pero un set o map significa más que solo una forma de organizar los datos.
Dicho de otra manera, un contenedor estándar es más que solo su estructura de datos subyacente.
Una razón obvia es que puede organizar los elementos como un montón dentro de otro contenedor.
Entonces puedes llamar a make_heap() en un vector o en un deque o incluso en un array en C.