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.).¿Por qué los montones en C++ se implementan como algoritmos en lugar de contenedores?
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 proveer a su propio almacenamiento;. Por defecto se crea un std :: vector como su almacén de respaldo)
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.
Una razón obvia es que puede organizar elementos como un montón dentro de otro contenedor.
Para que pueda llamar al make_heap() en un vector o un deque o incluso un array en C.
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 una forma de organizar los datos.
Dicho de otra manera, un contenedor estándar es más que solo su estructura de datos subyacente.
Los montículos * 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 la prioridad de STL requiere un contenedor (que por defecto 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.
* Binary montones en particular. Otras formas de montones (Binomial, Fibonacci, etc.) no lo son.
Para el registro, hay un montón contenedor a base de datos: 'priority_queue'. – avakar
¿Por qué NO? Para un montón, puede usar cualquier secuencia de acceso aleatorio. No obligarlo a usar un contenedor especial es bueno. Uno debe tratar de desacoplar las cosas. No, los conjuntos y los mapas no funcionan bien usando secuencias. Es mucho más fácil usar árboles binarios reales para esos. – sellibitze
Como algunas personas parecen estar confundidas: kts se refiere a la estructura de datos [http://en.wikipedia.org/wiki/Heap_(data_structure)], no a la tienda gratuita. –