C 스타일 언어의 동적 메모리 할당과 데이터 구조를 모두 “힙”이라고 하는 런타임 힙이 사용되는 이유는 무엇 입니까? 어떤 관계가 있습니까?
답변
도널드 크 누스 (Donald Knuth)는 다음과 같이 말한다 (컴퓨터 프로그래밍 기술, 제 3 판, Vol.
몇몇 저자들은 1975 년경에 사용 가능한 메모리 풀을 “힙”이라고 부르기 시작했습니다.
그는 어떤 저자를 언급하지 않고 특정 논문을 언급하지 않지만 우선 순위 대기열과 관련하여 “힙”이라는 용어를 사용하는 것이 전통적인 단어의 의미라고 말합니다.
답변
그들은 같은 이름을 가지고 있지만 실제로는 개념적으로도 비슷하지 않습니다. 세탁물 바구니를 “옷 더미”라고하는 것과 같은 방식으로 메모리 힙을 힙이라고합니다. 이 이름은 마음대로 메모리를 할당하고 할당을 해제 할 수있는 다소 지저분한 장소를 나타내는 데 사용됩니다. 데이터 구조 (참조하는 Wikipedia 링크)는 매우 다릅니다.
답변
이름 충돌은 유감 스럽지만 그다지 신비로운 것은 아닙니다. 힙 은 더미, 수집, 그룹 등을 의미하는 데 사용되는 작고 일반적인 단어입니다. 데이터 구조에 대한 단어 사용은 메모리 풀의 이름보다 이전 날짜입니다. 사실, 수영장 은 후자의 경우 훨씬 더 나은 선택이라고 생각합니다. 힙 은 데이터 구조에 맞지만 메모리 풀에는 맞지 않는 수직 구조 (파일과 같은)를 의미합니다. 우리는 메모리 풀 힙을 계층 적이라고 생각하지 않지만, 데이터 구조의 기본 개념은 가장 큰 요소를 힙 (및 하위 힙)의 맨 위에 유지하는 것입니다.
데이터 구조 날짜는 60 년대 중반으로 거슬러 올라갑니다. 70 년대 초의 메모리 풀을 힙합니다. 힙 (메모리 풀을 의미)이라는 용어는 적어도 1971 년 Wijngaarden 이 Algol에 대한 토론에서 사용했습니다.
데이터 구조로 힙 을 가장 먼저 사용 하는 것은
JWJ 1964 년 윌리엄스 에서 7 년 전에 발견 되었다. “알고리즘 232-힙 정렬”, ACM 7 (6)의 통신 : 347-348
답변
실제로 메모리가 할당되는 방식 ( 버디 블록 참조 )에 대한 정보는 데이터 구조의 힙을 상기시킵니다.
답변
답변
힙과 유사한 데이터 구조는 사용 가능한 메모리 할당을 찾는 알고리즘에 의해 사용됩니다. 다음은 http://www.cprogramming.com/tutorial/virtual_memory_and_heaps.html 에서 발췌 한 것 입니다.
new호출 되면 요청 크기에 맞는 여유 메모리 블록을 찾기 시작합니다. 이러한 메모리 블록이 발견되면 예약 된 것으로 표시되고 해당 위치에 대한 포인터가 리턴됩니다. 객체 크기보다 큰 최소 여유 블록을 찾기 위해 전체 메모리를 스캔하거나 메모리가 필요한 첫 번째 블록을 반환하기 위해 전체 메모리를 스캔해야하기 때문에이를 수행하기위한 여러 알고리즘이 있습니다. 메모리 블록을 확보하는 속도를 향상시키기 위해 여유 및 예약 된 메모리 영역은 힙이라고하는 이진 트리와 유사한 데이터 구조로 유지됩니다.
답변
구어체 용어 스택 메모리 및 힙 메모리는 C ++ 표준에서 사용되지 않습니다. 표준은 정적 저장소, 스레드 저장소, 자동 저장소 및 동적 저장소를 사용합니다.
자세한 내용은 표준의 스토리지 내구성 섹션 에서 확인할 수 있습니다 .
따라서 언어 및 표준 라이브러리 관점에서 혼동이 없습니다.