14.1 Memory Management
14.1.1 Memory Allocation in C++
14.1.2 Garbage Collection
14.2 External Memory and Caching
14.2.1 The Memory Hierarchy
14.2.2 Caching Strategies
14.3 External Searching and B-Trees
14.3.1 (a,b) Trees
14.4 External-Memory Sorting
14.4.1 Multi-Way Merging
In order to implement any data structure on an actual computer, we need to use computer memory. Computer memory is simply a sequence of memory words, each of which usually consists of 4, 8, or 16 bytes (depending on the computer). These memory words are numbered from 0 to N − 1, where N is the number of memory words available to the computer. The number associated with each memory word is known as its address. Thus, the memory in a computer can be viewed as basically one giant array of memory words. Using this memory to construct data structures (and run programs) requires that we manage the computer's memory to provide the space needed for data—including variables, nodes, pointers, arrays, and character strings—and the programs the computer runs. We discuss the basics of memory management in this section.
A C++ program is compiled into a binary executable file, which is then executed within the context of the C++ run-time environment. The run-time environment provides ...