Dynamic memory allocation¶
Dynamic data structures are such structures, for which memory is allocated (and possibly also deallocated) dynamically, based on the commands written by the programmer. This happens at run time.
Dynamic data structures usually consist of
several elements of the same type.
Such an element can be defined as a C++ struct with several fields.
The elements are linked together such that each element has a link field
(pointer) to another element(s) of the same structure.
Examples of dynamic data structures are linked lists, stacks, queues, trees, networks etc. These structures are typically defined as classes, and they can be operated by the member functions specific for the structure in question. As with any class, the programmer is responsible for implementing the member functions.
From these structures, we will introduce a linked list more precisely later on this round.
Variable’s lifetime and how to control it¶
Until now, we have only used automatic variables, which means that allocating (reserving) memory for them and afterwards deallocating (releasing) it was automated:
At variable definition, the compiler has taken care of finding the necessary amount of memory somewhere and allocated it.
When a variable reached the end of its lifetime, the compiler, again, has deallocated the memory that was no longer needed.
However, there are many situations when a programmer has to be able to control the lifetime of a variable (starting from the allocation of memory for a variable and ending with the deallocation of the reserved memory) in order to create dynamic data structures. When the control over the lifetime of a variable is completely the programmer’s responsibility, the variable is called a dynamic variable. The mechanisms and tools used for controlling dynamic variables are called dynamic memory management.
If there is not enough free memory space when the user tries to allocate it, an exception occurs and the program execution terminates. However, handling that exception is, even on a conceptual level, so challenging that, on this course, we will pretend that we never run out of memory.