c++ - programming - ¿Por qué dos conceptos diferentes se llaman "montón"?
heap vs stack diferencia (8)
¿Por qué se utiliza el almacenamiento dinámico de tiempo de ejecución para la asignación de memoria dinámica en lenguajes de estilo C y la estructura de datos se llama "el montón"? ¿Hay alguna relación?
¿Quizás el primer montón de memoria implementado fue administrado por una estructura de montón?
Donald Knuth dice (The Art of Computer Programming, Third Ed., Vol. 1, p.435):
Varios autores comenzaron alrededor de 1975 para llamar al conjunto de memoria disponible un "montón".
Él no dice qué autores y no da referencias a ningún documento específico, pero sí dice que el uso del término "montón" en relación con las colas de prioridad es el sentido tradicional de la palabra.
El algoritmo de búsqueda de asignación de memoria disponible utiliza la estructura de datos similar a un montón. Lo siguiente está extraído de http://www.cprogramming.com/tutorial/virtual_memory_and_heaps.html .
Cuando se invoca
new, comienza a buscar un bloque de memoria libre que se ajuste al tamaño de su solicitud. Suponiendo que se encuentra un bloque de memoria así, se marca como reservado y se devuelve un puntero a esa ubicación. Hay varios algoritmos para lograr esto porque se debe hacer un compromiso entre escanear toda la memoria para encontrar el bloque libre más pequeño que el tamaño de su objeto, o devolver el primero donde la memoria necesaria se ajusta. Para mejorar la velocidad de obtener un bloque de memoria, las áreas libres y reservadas de la memoria se mantienen en una estructura de datos similar a los árboles binarios llamados un montón.
El nombre colisión es desafortunado, pero no tan misterioso. Heap es una palabra pequeña y común que se usa para referirse a una pila, colección, grupo, etc. El uso de la palabra para la estructura de datos es anterior (estoy bastante seguro) del nombre del conjunto de memoria. De hecho, el pool habría sido una opción mucho mejor para este último, en mi opinión. El montón connota una estructura vertical (como una pila), que se ajusta a la estructura de datos, pero no al conjunto de memoria. No pensamos en un montón de pool de memoria como jerárquico, mientras que la idea fundamental detrás de la estructura de datos es mantener el elemento más grande en la parte superior del montón (y sub-montones).
Heap la estructura de datos se remonta a mediados de los años 60; acumular el grupo de memoria, a principios de los 70. El término montón (que significa reserva de memoria) fue utilizado al menos desde 1971 por Wijngaarden en las discusiones de Algol.
Posiblemente, el uso más temprano de montón como una estructura de datos se encuentra siete años antes en
Williams, JWJ 1964. "Algoritmo 232 - Heapsort", Comunicaciones del ACM 7 (6): 347-348
En realidad, leer sobre la manera en que se asigna la memoria (ver Bloques de amigos ) me recuerda un montón de estructuras de datos.
La memoria de pila de términos coloquiales y la memoria de pila no se utilizan en el estándar de C ++. El estándar utiliza almacenamiento estático, almacenamiento de subprocesos, almacenamiento automático y almacenamiento dinámico.
Se puede encontrar más información en la sección Duración de almacenamiento de la norma.
Por lo tanto, desde el punto de vista de la lengua y la biblioteca estándar, no hay confusión.
Tienen el mismo nombre, pero en realidad no son similares (incluso conceptualmente). Un montón de memoria se llama montón de la misma manera en que se referiría a un cesto de ropa como un "montón de ropa". Este nombre se utiliza para indicar un lugar algo desordenado donde la memoria se puede asignar y desasignar a voluntad. La estructura de datos (como lo señala el enlace de Wikipedia a la que hace referencia) es bastante diferente.