C++/heap

Advertisement


Question
hello!
im a BS-information technology student.i have a problem with my assignment.can u please explain to me what is the concept of heap in c++??please give me also examples of program using the concept of heap??..

thanks in advance!!

Answer
A heap can be one of two things:

       - a data structure
       - another name for the free store which is used to obtain memory dynamically at runtime.

I shall concentrate on the second as it is more obviously a C++ sort of topic and you give no clues as to which it is you are asking about.

For more on the heap data structure refer to your notes - if you have covered them -  or look for further references online - there seems little point in me repeating (probably less clearly) what has been said on heap data structures already. You might like to start with:

   http://en.wikipedia.org/wiki/Heap_(data_structure)

The other use is to allow us to allocate memory at runtime. In C and C++ this is called the free store or heap.

A program typically uses three types of memory (excluding that used for the program code itself): static storage for global and static data, stack based storage for function call local 'automatic' data and dynamic memory that is allocated and managed at runtime.

The first two you are probably used to:

   int aGlobalVariable(1);
   static int aStaticGlobalVariable(2);

   int main()
   {
       static aStaticLocalVariable(3);
       int aStackBasedLocalVariable(4);
   }

The objects aGlobalVariable, aStaticGlobalVariable and aStaticLocalVariable are all allocated from static program storage and differ mainly by the scope in which they may be accessed:

aGlobalVariable is fully global and can be accessed from anywhere in the program - even from other compilation units (a compilation unit is what you hand the compiler to generate one object file generally a single source file, but takes into account code pulled in via #include directives). To achieve this it has to be visible to the linker and is said to have external linkage.

aStaticGlobalVariable is similar to aGlobalVariable, but can only be accessed from within the same compilation unit (source file) in which it is defined, from the point it is defined to the end of the file. It is not visible to the linker and is said to have internal linkage.

aStaticLocalVariable is also static but cannot be accessed from outside the function in which it is defined. In fact if it were defined within a sub-scope in the function (e.g. inside a compound block as part of an if statement) then the scope is reduced further to this sub-scope. It also has internal linkage.

All objects having static storage are initialised at the point they are defined (if in a function then they are initialised the first time the code execution runs through their definition) and exist until program termination. This means in the case of function local static objects that they keep their state between function calls.

aStackBasedLocalVariable is allocated from stack storage. It is allocated on a per function _call_ basis - note I said function call and not function. The stack storage for a function call is called a stack frame. Each time the function is called it gets a new stack frame thus each call to a function gets a new copy of objects allocated from stack storage. Such objects exist from the point where they are defined in the function to the end of the block they are defined in which will be no greater than the scope of the function itself. From the memory point of view it is probable that all memory for a stack frame is released on function return - whether normally or exceptionally via throwing of an exception. However, notionally objects with smaller scope than the whole function get created when execution runs past their definition and destroyed on block exit - for objects of user defined class types with constructors and destructors this means that the constructor has to be called for each creation at the point they are defined and the destructor called for such objects at the end of their scope. This in particular has an effect for code blocks of loops.

Both of the above storage types (storage classes) are not controllable at runtime. Although of course the storage is actually allocated at runtime - at program start up for static storage and for each function call for stack storage - there is no control over what is allocated - that decision was made when the code was written and all the actual allocation logic and management was provided for us by the compiler.

To actually allocate and release objects explicitly during runtime we require dynamic object management, and the storage for such objects has to come from somewhere - and this somewhere is the free store or heap.

In C++ we use the operators new and delete and their array counterparts new [] and delete [] to allocate objects one at a time or in blocks (arrays) at runtime. The new operator returns a pointer to the created object and new [] the pointer to the first created object of the array of objects. The delete operator deletes the object pointed to by the provided pointer which *must* have been allocated by new and likewise delete [] takes a pointer to the first element of an array of objects that *must* have been allocated with new [].

The creation and deletion of objects in C++ are both two stage processes. For each object first storage must be allocated - this is from the free store or heap. This is raw memory. To turn it into the required object(s) a constructor is then executed for each object created - once for new and as many times as there are objects in the requested array for new []. Likewise to destroy dynamically allocated objects they are first destroyed by calling their destructor - once for a single object for delete once for each object in an array for delete [] - and then the raw memory is unallocated, Note for arrays it is almost certain that the raw memory for all objects in the array are allocated and released as a single block large enough to contain all the required objects.

Ok you say why would I want to use dynamic memory allocation?

Well look at this program:

   main()
   {
       const unsigned int NumberOfValues(10);
       int values[NumberOfValues];
       DoSomething(values, NumberOfValues );
   }

Very simple - we create an array of a size determined by the constant value NumberOfValues and then do something with it.

Now consider this simple change:

   #include <iostream>

   main()
   {
       bool isRetry( false );
       unsigned int numberOfValues;
       do
       {
         if ( isRetry )
         {
         std::cout << "The value you entered was not an integer between 1 and 100, please try again.\n";
         }
         std::cout "Enter the number of values to be processed (an integer between 1 and 100): ";
         std::cin >> numberOfValues;
         isRetry = true;
       }
       while ( ! isValid(numberOfValues) );

       int values[numberOfValues];
       DoSomething( values, numberOfValues );
   }

Now we simply (well not that simply) request the number of values to be processed from the user at run time. In this case the program will _not_ compile because the compiler does not know the size of the values array and so cannot manage the allocation of the stack storage for it.

Because this information is only known at runtime we can only allocate the required storage at runtime, and this is where we require the use of dynamic object allocation with dynamic memory allocation using the free store or heap, viz:

   #include <iostream>

   main()
   {
       bool isRetry( false );
       unsigned int numberOfValues;
       do
       {
         if ( isRetry )
         {
         std::cout << "The value you entered was not an integer between 1 and 100, please try again.\n";
         }
         std::cout "Enter the number of values to be processed (an integer between 1 and 100): ";
         std::cin >> numberOfValues;
         isRetry = true;
       }
       while ( ! isValid(numberOfValues) );

       int * values = new int[numberOfValues]; // create array of integers with new [] getting memory from heap
       DoSomething( values, numberOfValues );
       delete [] values;          // delete array with delete [] returning memory to heap
   }

You might like to also look at:

   http://en.wikipedia.org/wiki/Dynamic_memory_allocation
   
for more information (note that C and C++ do not use garbage collection), and

   http://en.wikipedia.org/wiki/New_(C++)
   http://en.wikipedia.org/wiki/Delete_(C++)

for a bit more on C__ new and delete operators.

For some information on C++ techniques to help manage dynamic object and other resources see

   http://en.wikipedia.org/wiki/Smart_pointer
   http://en.wikipedia.org/wiki/Resource_Acquisition_Is_Initialization

for starters.

And of course for various questions on C++ free store / heap management see the C++ FAQ lite section at:

   http://www.parashift.com/c++-faq-lite/freestore-mgmt.html

You might want to peruse other section of t his FAQ e.g. the newbie section at:

   http://www.parashift.com/c++-faq-lite/newbie.html#faq-29.10

This has been of necessity a quick, simplified, tour of the subject(s) as your question was not very specific. If there is something you would like to know that I have not covered, or not in enough detail, or if there is something, maybe from the references I pointed you to, you do not understand, then please ask another (possibly follow up) question.  

C++

All Answers


Answers by Expert:


Ask Experts

Volunteer


Ralph McArdell

Expertise

I am a software developer with more than 15 years C++ experience and over 25 years experience developing a wide variety of applications for Windows NT/2000/XP, UNIX, Linux and other platforms. I can help with basic to advanced C++, C (although I do not write just-C much if at all these days so maybe ask in the C section about purely C matters), software development and many platform specific and system development problems.

Experience

My career started in the mid 1980s working as a batch process operator for the now defunct Inner London Education Authority, working on Prime mini computers. I then moved into the role of Programmer / Analyst, also on the Primes, then into technical support and finally into the micro computing section, using a variety of 16 and 8 bit machines. Following the demise of the ILEA I worked for a small company, now gone, called Hodos. I worked on a part task train simulator using C and the Intel DVI (Digital Video Interactive) - the hardware based predecessor to Indeo. Other projects included a CGI based train simulator (different goals to the first), and various other projects in C and Visual Basic (er, version 1 that is). When Hodos went into receivership I went freelance and finally managed to start working in C++. I initially had contracts working on train simulators (surprise) and multimedia - I worked on many of the Dorling Kindersley CD-ROM titles and wrote the screensaver games for the Wallace and Gromit Cracking Animator CD. My more recent contracts have been more traditionally IT based, working predominately in C++ on MS Windows NT, 2000. XP, Linux and UN*X. These projects have had wide ranging additional skill sets including system analysis and design, databases and SQL in various guises, C#, client server and remoting, cross porting applications between platforms and various client development processes. I have an interest in the development of the C++ core language and libraries and try to keep up with at least some of the papers on the ISO C++ Standard Committee site at http://www.open-std.org/jtc1/sc22/wg21/.

Education/Credentials

©2016 About.com. All rights reserved.