Allocating memory for an array c. Dynamic memory allocation in C. Standard dynamic memory allocation functions
Last update: 28.05.2017
When creating an array with fixed dimensions, a certain memory is allocated for it. For example, let's say we have an array with five elements:
Double numbers = (1.0, 2.0, 3.0, 4.0, 5.0);
For such an array, memory is allocated 5 * 8 (size of the double type) = 40 bytes. Thus, we know exactly how many elements are in the array and how much memory it takes. However, this is not always convenient. Sometimes it is necessary that the number of elements and, accordingly, the size of the allocated memory for the array were determined dynamically, depending on some conditions. For example, the user himself can enter the size of the array. And in this case, we can use dynamic memory allocation to create an array.
A number of functions are used to manage dynamic memory allocation, which are defined in the stdlib.h header file:
malloc (). Has a prototype
Void * malloc (unsigned s);
Allocates memory s bytes long and returns a pointer to the beginning of the allocated memory. Returns NULL on failure
calloc (). Has a prototype
Void * calloc (unsigned n, unsigned m);
Allocates memory for n elements of m bytes each and returns a pointer to the beginning of the allocated memory. Returns NULL on failure
realloc (). Has a prototype
Void * realloc (void * bl, unsigned ns);
Resizes the previously allocated block of memory pointed to by bl to ns bytes. If the bl pointer is NULL, that is, no memory was allocated, then the function is similar to malloc.
free (). Has a prototype
Void * free (void * bl);
Frees a previously allocated block of memory pointed to by bl.
If we do not use this function, then the dynamic memory will be released automatically anyway when the program exits. However, it is still good practice to call the free () function, which allows you to free memory as soon as possible.
Let's consider the application of functions to a simple problem. The length of the array is unknown and is entered during program execution by the user, and also the values of all elements are entered by the user:
#include Console output of the program: Size of array = 5 block = 23 block = -4 block = 0 block = 17 block = 81 23 -4 0 17 81 Here, a block pointer of type int is defined for memory management for the array. The number of array elements is not known in advance; it is represented by the variable n. First, the user enters the number of elements that fall into the variable n. After that, you need to allocate memory for the given number of elements. To allocate memory here, we could use any of the three functions described above: malloc, calloc, realloc. But in this particular situation, we will use the malloc function: Block = malloc (n * sizeof (int)); First of all, it should be noted that all three above-mentioned functions return a void * pointer as a result for the universality of the return value. But in our case, an array of type int is created, for which a pointer of type int * is used, so the result of the malloc function is implicitly cast to the type int *. The number of bytes for the allocated block is passed to the malloc function itself. It is quite easy to calculate this number: it is enough to multiply the number of elements by the size of one element n * sizeof (int). After completing all the actions, the memory is freed using the free () function: Free (block); It is important that after executing this function, we will no longer be able to use the array, for example, display its values to the console: Free (block); for (int i = 0; i And if we try to do this, we get undefined values. Instead of malloc in a similar way, we could use the calloc () function, which takes the number of elements and the size of one element: Block = calloc (n, sizeof (int)); Or the realloc () function could also be used: Int * block = NULL; block = realloc (block, n * sizeof (int)); When using realloc, it is desirable (in some environments, for example, in Visual Studio, required) to initialize the pointer to at least NULL. But in general, all three calls in this case would have the same effect: Block = malloc (n * sizeof (int)); block = calloc (n, sizeof (int)); block = realloc (block, n * sizeof (int)); Now let's look at a more complex task - dynamic memory allocation for a two-dimensional array: #include The variable table represents a pointer to an array of pointers of type int *. Each table [i] pointer in this array represents a pointer to a subarray of int elements, that is, individual table rows. And the table variable actually represents a pointer to an array of pointers to table rows. A rows pointer of type int is defined to store the number of elements in each subarray. It actually stores the number of columns for each row of the table. First, the number of rows is entered into the rowscount variable. The number of rows is the number of pointers in the array pointed to by the table pointer. And furthermore, the number of rows is the number of elements in the dynamic array pointed to by the rows pointer. Therefore, first, it is necessary to allocate memory for all these arrays: Table = calloc (rowscount, sizeof (int *)); rows = malloc (sizeof (int) * rowscount); Next, in the loop, the number of columns is entered for each row. The entered value goes into the rows array. And according to the entered value, the required memory size is allocated for each line: Scanf ("% d", & rows [i]); table [i] = calloc (rows [i], sizeof (int)); Then you enter the items for each line. At the end of the program, memory is freed during output. In the program, memory is allocated for table rows, so this memory must be freed: Free (table [i]); And in addition, the memory allocated for the table and rows pointers is freed: Free (table); free (rows); Console output of the program: Rows count = 2 Columns count for 1 = 3 table = 1 table = 2 table = 3 Columns count for 2 = 2 table = 4 table = 5 1 2 3 4 5 To work with arrays of information, programs must allocate memory for these arrays. To allocate memory for arrays of variables, the corresponding operators, functions, etc. are used. In the C ++ programming language, the following methods of memory allocation are allocated: 1. Static
(fixed) memory allocation. In this case, memory is allocated only once at compile time. The size of the allocated memory is fixed and unchanged until the end of the program execution. An example of such an allocation is the declaration of an array of 10 integers: 2. Dynamic
memory allocation. In this case, a combination of the new and delete operators is used. The new operator allocates memory for a variable (array) in a special area of memory called the heap. The delete operator releases the allocated memory. Each new operator must have its own delete operator. Dynamic memory allocation has the following advantages over static memory allocation: Advantages of a static way of allocating memory: Depending on the task at hand, the programmer must be able to correctly determine which way of allocating memory is suitable for a particular variable (array). The general form of allocating memory for a single variable using the new operator is as follows: If the memory for a variable is allocated with the new operator, then after the end of using the variable, this memory must be released with the delete operator. In the C ++ language, this is a prerequisite. If you do not free memory, then the memory will remain allocated (occupied), but no program can use it. In this case, there will be "memory leak"
(memory leak). In the Java, C # programming languages, there is no need to free memory after allocation. This is done by the garbage collector. The general form of the delete operator for a single variable is: where ptrName- the name of the pointer for which memory was previously allocated by the new operator. After executing the delete operator, the pointer ptrName points to an arbitrary piece of memory that is not reserved (allocated). The examples demonstrate the use of the new and delete operators. The examples are simplified. Example 1. Pointer to int type. The simplest example Example 2. Pointer to type double « Memory leak"- this is when the memory for a variable is allocated by the new operator, and at the end of the program's work, it is not released by the delete operator. In this case, the memory in the system remains occupied, although there is no longer a need to use it, since the program that used it has long since completed its work. Memory leak is a typical programmer's mistake. If the "memory leak" is repeated many times, then a possible situation when all the available memory in the computer will be "occupied". This will lead to unpredictable consequences for the operating system. When using the new operator, it is possible that the memory will not be allocated. Memory may not be allocated in the following situations: In this case, a bad_alloc exception is thrown. The program can catch this situation and handle it accordingly. Example. The example takes into account the situation when memory may not be allocated by the new operator. In this case, an attempt is made to allocate memory. If the attempt is successful, then the program continues. If the attempt is unsuccessful, then the function exits with the code -1. The allocation operator new for a single variable allows simultaneous initialization with the value of that variable. In general, memory allocation for a variable with simultaneous initialization is of the form Example. Allocating memory for variables with simultaneous initialization. Following is the main () function for a console application. Demonstrated memory allocation with simultaneous initialization. It also takes into account the situation when an attempt to allocate memory fails (critical situation bad_alloc). Dynamic memory allocation is essential for efficient use of computer memory. For example, we wrote some kind of program that processes an array. When writing this program, it was necessary to declare an array, that is, to give it a fixed size (for example, from 0 to 100 elements). Then this program will not be universal, because it can process an array of no more than 100 elements. And if we need only 20 elements, but space for 100 elements will be allocated in memory, because the array declaration was static, and this use of memory is extremely inefficient. In C ++, the new and delete operations are for dynamically allocating computer memory. The new operation allocates memory from the free memory area, and the delete operation releases the allocated memory. The allocated memory, after its use, must be released, so the new and delete operations are used in pairs. Even if you do not explicitly free memory, it will be freed by OS resources upon program termination. I still recommend not to forget about the delete operation. // example of using the operation new int * ptrvalue = new int; // where ptrvalue is a pointer to the allocated area of memory of type int // new is the operation of allocating free memory for the object being created. The new operation creates an object of the specified type, allocates memory to it, and returns a pointer of the correct type to the given memory location. If memory cannot be allocated, for example, if there are no free areas, then a null pointer is returned, that is, the pointer will return the value 0. Memory allocation is possible for any data type: int, float,double,char etc. // example of using the delete operation: delete ptrvalue; // where ptrvalue is a pointer to the allocated memory area of int type // delete is an operation to free memory Let's develop a program in which a dynamic variable will be created. // new_delete.cpp: defines the entry point for the console application. #include "stdafx.h" #include // code Code :: Blocks // Dev-C ++ code // new_delete.cpp: defines the entry point for the console application. #include (! LANG: B line 10
shows a way to declare and initialize a dynamic object with a nine, all you need to do is specify the value in parentheses after the data type. The result of the program is shown in Figure 1. Ptrvalue = 9 Press any key to continue. ... ... Figure 1 - Dynamic variable As mentioned earlier, arrays can also be dynamic. Most often, the new and delete operations are used to create dynamic arrays, and not to create dynamic variables. Let's look at a code snippet for creating a one-dimensional dynamic array. // declaration of a one-dimensional dynamic array with 10 elements: float * ptrarray = new float; // where ptrarray is a pointer to the allocated memory area for an array of real numbers of float type // in square brackets we indicate the size of the array After the dynamic array has become unnecessary, you need to free the memory area that was allocated for it. // freeing memory allocated for a one-dimensional dynamic array: delete ptrarray; After the delete operator, square brackets are placed, which indicate that a piece of memory allocated for a one-dimensional array is being freed. Let's develop a program in which we will create a one-dimensional dynamic array filled with random numbers. // new_delete_array.cpp: defines the entry point for the console application. #include"stdafx.h"
#include !} // code Code :: Blocks // Dev-C ++ code // new_delete_array.cpp: defines the entry point for the console application. #include The created one-dimensional dynamic array is filled with random real numbers obtained using the functions of generating random numbers, and the numbers are generated in the range from 1 to 10, the interval is set as follows - rand ()% 10 + 1 .
To get random real numbers, a division operation is performed using an explicit cast to the real type of the denominator - float ((rand ()% 10 + 1)). To show only two decimal places, use the setprecision (2) function ,
the prototype of this function is in the header file Array = 0.8 0.25 0.86 0.5 2.2 10 1.2 0.33 0.89 3.5 Press any key to continue. ... ... Figure 2 - Dynamic array in C ++ Upon completion of work with the array, it is deleted, thus freeing the memory allocated for its storage. We have learned how to create and work with one-dimensional dynamic arrays. Now let's look at the code snippet that shows how a two-dimensional dynamic array is declared. // declaration of a two-dimensional dynamic array with 10 elements: float ** ptrarray = new float *; // two lines in the array for (int count = 0; count< 2; count++)
ptrarray = new float ; // и пять столбцов
// где ptrarray – массив указателей на выделенный участок памяти под массив вещественных чисел типа float
First, a second-order pointer float ** ptrarray is declared, which refers to an array of float * pointers, where the size of the array is two .
Then, in the for loop, each line of the array declared in line 2 memory for five elements is allocated. The result is a two-dimensional dynamic array ptrarray. Consider an example of freeing memory allocated for a two-dimensional dynamic array. // freeing memory allocated for a two-dimensional dynamic array: for (int count = 0; count< 2; count++)
delete ptrarray;
// где 2 – количество строк в массиве
Declaring and deleting a two-dimensional dynamic array is done using a loop, as shown above, you need to understand and remember how this is done. Let's develop a program in which we will create a two-dimensional dynamic array. // new_delete_array2.cpp: defines the entry point for the console application. #include "stdafx.h" #include // code Code :: Blocks // Dev-C ++ code // new_delete_array2.cpp: defines the entry point for the console application. #include When displaying the array, the setw () function was used, if you have not forgotten, then it allocates a space of a given size for the output data. In our case, there are four positions for each element of the array, this allows you to align, by columns, numbers of different lengths (see Figure 3). 2.7 10 0.33 3 1.4 6 0.67 0.86 1.2 0.44 Press any key to continue. ... ... Figure 3 - Dynamic array in C ++ Working with dynamic memory is often a bottleneck in many algorithms, if you do not apply special tricks. I'll cover a couple of these techniques in this article. The examples in the article differ (for example, from this one) in that the overloading of the new and delete operators is used, and due to this, the syntax will be minimalistic, and the program rework will be simple. The pitfalls found in the process are also described (of course, gurus who have read the standard from cover to cover will not be surprised). Let's write simple tests for C ++ and C # (C # is known for an excellent memory manager that divides objects by generations, uses different pools for objects of different sizes, etc.). Class Node (public: Node * next;); // ... for (int i = 0; i< 10000000; i++) {
Node* v = new Node();
}
Class Node (public Node next;) // ... for (int l = 0; l< 10000000; l++)
{
var v = new Node();
}
Despite all the "spherical vacuum" of the example, the time difference turned out to be 10 times (62 ms versus 650 ms). In addition, the c # example is complete, and according to the rules of good form in c ++, the selected objects must be deleted, which will further increase the gap (up to 2580 ms). Since the goal is minimal intervention in the program, all that can be done is to add a BlockAlloc mixin to the Node class: First of all, we need a pool of large blocks (pages) that we take from the OS or C-runtime. It can be organized on top of malloc and free functions, but for greater efficiency (to skip an unnecessary level of abstraction), we use VirtualAlloc / VirtualFree. These functions allocate memory in blocks that are multiples of 4K and also reserve the process address space in blocks that are multiples of 64K. By specifying the commit and reserve options at the same time, we skip another level of abstraction, reserving address space and allocating memory pages in one call. PagePool class inline size_t align (size_t x, size_t a) (return ((x-1) | (a-1)) + 1;) // # define align (x, a) ((((x) -1) | ( (a) -1)) + 1) template Then we organize a pool of blocks of a given size BlockPool class template Commentary // todo: lock (this)
places that require inter-thread synchronization are marked (for example, use EnterCriticalSection or boost :: mutex). Let me explain why the "formatting" of the page does not use the FreeBlock abstraction to add a block to the pool. If something like For (size_t i = 0; i< PageSize; i += BlockSize) FreeBlock((char*)tmp+i);
Then the page, according to the FIFO principle, would be marked up "in reverse": Several blocks requested from the pool in a row would have descending addresses. And the processor does not like to go back, from this it breaks Prefetch ( UPD: Not relevant for modern processors). If you do the markup in a loop Now that the preparations are made, we can define the mixin class. I will explain why checks are needed if (s! = sizeof (T)) Ready. We inherit Node from BlockAlloc and re-run the test. Do you often come across classes that store a lot of different child objects, such that the lifetime of the latter is no longer than the lifetime of the parent? For example, it can be an XmlDocument class filled with Node and Attribute classes, as well as c-strings (char *) taken from the text inside the nodes. Or a list of files and directories in the file manager, loaded once when rereading a directory and no longer changing. As shown in the introduction, delete is more expensive than new. The idea of the second part of the article is to allocate memory for child objects in a large block associated with the Parent object. When the parent object is deleted, the child's destructors will be called, as usual, but the memory will not need to be returned - it will be freed in one large block. Let's create the PointerBumpAllocator class, which can bite off pieces of different sizes from a large block and allocate a new large block when the old one is exhausted. PointerBumpAllocator Class template Finally, let's describe the ChildObject mixin with new and delete overloaded referring to the given allocator: Template In this case, in addition to adding a mixin to the child class, you will also need to fix all calls to new (or use the "factory" pattern). The syntax for the new operator will be as follows: New (... parameters for operator ...) ChildObject (... constructor parameters ...) For convenience, I've defined two new operators that take either A & or A *. There is no special syntax for calling delete, the compiler will call the standard delete (marked with * 1), regardless of which of the new operators was used to create the object. That is, the delete syntax is normal: If an exception occurs in the constructor of ChildObject (or its successor), delete is called with the signature corresponding to the signature of the new operator used to create this object (the first parameter size_t will be replaced with void *). Placing the new operator in the private section protects against calling new without specifying an allocator. Here's a complete example of using the Allocator-ChildObject pair: Example class XmlDocument: public DefaultAllocator (public: ~ XmlDocument () (for (vector Conclusion. The article was written 1.5 years ago for the sandbox, but alas, the moderator did not like it. In C ++, as in many other languages, memory can be allocated statically (memory is allocated before the program starts executing and freed after the program finishes) or dynamically (memory is allocated and freed during program execution). Static memory allocation is performed for all global and local variables that have explicit descriptions in the program (without using pointers). In this case, the memory allocation mechanism is determined by the location of the variable declaration in the program and by the memory class specifier in the description. The type of the variable determines the size of the allocated memory area, but the memory allocation mechanism does not depend on the type. There are two main mechanisms for static memory allocation. · Memory for each of the global and static (declared with the static specifier) variables is allocated before starting the program execution in accordance with the type description. From the beginning to the end of the program execution, these variables are associated with the memory area allocated for them. Thus, they have a global lifetime, while their field of visibility is different. For local variables that are declared inside a block and do not have a specifier static, memory is allocated in a different way. Before the program starts executing (when it is loaded), a fairly large area of memory is allocated, called stack(sometimes the terms are used program stack or call stack to make a distinction between the stack as an abstract data type). The stack size depends on the development environment, for example, in MS Visual C ++, by default, 1 megabyte is allocated for the stack (this value can be configured). During program execution, when entering a certain block, memory is allocated on the stack for variables localized in the block (in accordance with the description of their type); when exiting the block, this memory is freed. These processes are performed automatically, which is why local variables in C ++ are often called automatic. When a function is called, memory is allocated on the stack for its local variables, parameters (the value or address of a parameter is placed on the stack), the result of the function, and the return point is saved - the address in the program where you need to return when the function ends. When a function exits, all data associated with it is removed from the stack. The use of the term "stack" is easy to explain - with the accepted approach to allocating and freeing memory, the variables that are pushed onto the stack last (these are variables located in the deepest block) are removed from it first. That is, the allocation and release of memory occurs according to the LIFO principle (LAST IN - FIRST OUT, last in - first out). This is how the stack works. The stack as a dynamic data structure and its possible implementation will be discussed in the next section. In many cases, static memory allocation leads to its inefficient use (this is especially typical for large arrays), since the statically allocated memory area is not always actually filled with data. Therefore, in C ++, as in many languages, there are convenient tools for dynamically generating variables. The essence of dynamic memory allocation is that memory is allocated (captured) upon request from the program and released also upon request. In this case, the memory size can be determined by the type of the variable or explicitly indicated in the request. Such variables are called dynamic.
The ability to create and use dynamic variables is closely related to the pointer mechanism. Summarizing all of the above, we can imagine the following memory allocation scheme during program execution (Figure 2.1). The location of the regions relative to each other in the figure is rather arbitrary, since the operating system takes care of the details of memory allocation. Figure 2.1 - Scheme of memory allocation To conclude this section, we will touch upon one painful problem in the process of working with the stack - the possibility of its overflow (this emergency situation is usually called Stack Overflow). The reason that gave rise to the problem is understandable - the limited amount of memory that is allocated for the stack when the program is loaded. The most likely situations for stack overflow are local arrays of large sizes and deep nesting of recursive function calls (usually occurs when programming recursive functions inaccurately, for example, some terminal branch is forgotten). In order to better understand the problem of stack overflow, we advise you to conduct such a simple experiment. In function main declare an array of integers with a size of, say, a million elements. The program will compile, but it will generate a stack overflow error when it is run. Now add the specifier to the beginning of the array description static(or remove the description of the array from the function main) - the program will work! There is nothing wonderful in this - it's just that now the array is not pushed onto the stack, but into the area of global and static variables. The size of the memory for this area is determined by the compiler - if the program was compiled, then it will work. However, as a rule, there is no need to declare huge statically generated arrays in your program. In most cases, dynamically allocating memory for such data will be more efficient and flexible.Dynamic and static memory allocation. Advantages and disadvantages. Memory allocation for single variables using the new and delete operators. Possible critical situations when allocating memory. Initialization on memory allocation
1. Dynamic and static (fixed) memory allocation. Major differences
2. Advantages and disadvantages of using dynamic and static memory allocation methods
3. How to allocate memory using the new operator for a single variable? General form.
4. How to free the memory allocated for a single variable using the delete operator? General form
5. Examples of allocating (new) and freeing (delete) memory for pointers of base types
6. What is a memory leak?
7. How to allocate memory using the new operator with the interception of a critical situation in which memory may not be allocated? Exception bad_alloc. Example
8. Allocating memory for a variable with simultaneous initialization. General form. Example
Creating dynamic arrays
0. Do we need manual work with memory?
First of all, let's check how a smart allocator can speed up the work with memory. 1. Pool of objects
The obvious solution is to take a large block of memory from the OS and split it into equal blocks of sizeof (Node) size, when allocating memory, take a block from the pool, and when freeing it, return it to the pool. The easiest way to organize a pool is to use a singly linked list (stack).
class Node: public BlockAlloc
for (size_t i = PageSize- (BlockSize- (PageSize% BlockSize)); i! = 0; i - = BlockSize) FreeBlock ...
then the markup loop would go backward.
template
When do they fire? Then, when creating / deleting a class inherited from the base T.
Descendants will use the usual new / delete, but BlockAlloc can also be mixed in with them. Thus, we can easily and safely determine which classes should use the pools without fear of breaking something in the program. Multiple inheritance also works great with this mixin.
The test time is now 120 ms. 5 times faster. But in c #, the allocator is still better. It's probably not just a linked list. (If, however, immediately after new, immediately call delete, and thereby not waste a lot of memory, fitting the data into the cache, we get 62 ms. Strange. Exactly like the .NET CLR, as if it returns the freed local variables immediately to the corresponding pool, without waiting for GC)2. The container and its colorful contents
If the allocator is added to the parent class as a member, the first option is more convenient:
node = new (allocator) XmlNode (nodename);
If the allocator is added as an ancestor (mixin), the second one is more convenient:
node = new (this) XmlNode (nodename);
delete node;