Click Here!
home account info subscribe login search FAQ/help site map contact us


 
Brief Full
 Advanced
      Search
 Search Tips
[an error occurred while processing this directive]
Previous Table of Contents Next


7.1 Create a container object that automatically grows or shrinks as needed?

Problem

My program has to read an unknown number of data items into a buffer. However, the size of the buffer has to vary at runtime to accommodate every new item read. Because the number of items can only be known after all the items have been read, it is impossible to allocate in advance a buffer of the appropriate size. What I really need is a buffer that adjusts its size automatically at runtime. It should take care of increasing its storage as required, avoid memory leaks and overruns, and optimize memory usage.

Technique

The Standard Template Library provides several class templates that automatically manage their memory. This How-To will show how to use STL containers for efficient, reliable, portable, and robust applications.

Steps

1.  Change to your base source directory and create a new subdirectory named DYNAMIC_VECTOR.
2.  Start your source code editor and type the following code into a file named MAIN.CPP.
// main.cpp this program demonstrates
// how to use STL vector class
// as a dynamic buffer

#include <vector>
#include <iostream>
using namespace std;
void main()
{
  vector <int> vi; //create a vector of ints
  for (;;) //read numbers from a user’s console until 0 is input
  {
    int temp;
    cout<<”enter a number; press 0 to terminate” <<endl;
    cin>>temp;
    if (temp == 0 ) break; //exit from loop?
    vi.push_back(temp); //insert int into the buffer
  }
  cout<< “you entered “<< vi.size() <<
  ⇒” elements into a dynamic vector” << endl;
}//end main
3.  Save MAIN.CPP and return to the command line. Next, compile and link MAIN.CPP.
If your compiler complains about the following #include statements:
#include <vector>
#include <iostream>

comment out (or remove) the using directive just below these #include statements and change them to
#include <iostream.h>
#include <vector.h>
4.  Compile and link the program.
5.  Run the program; the output should be as follows:
enter a number; press 0 to terminate
6.  Press 1 and then Enter. The output should be as follows:
enter a number; press 0 to terminate
7.  Press 10 and Enter. Again, the output should be as follows:
enter a number; press 0 to terminate
8.  Now press 0 and Enter. The output should be as follows:
you entered 2 elements into a dynamic vector

How It Works

Let us begin by examining the first #include statement in MAIN.CPP:

#include <vector>

vector is a class template defined in the standard <vector> header file. Because all STL containers are declared in namespace std, a using directive is required to instruct the compiler to resolve all subsequent references to vector to namespace std.

The first source line in main() defines an instance of vector:

vector <int> vi;

The angle brackets after a template’s name declare the particular type for which the template is defined. The sequence of a template name and angle brackets containing a type is termed specialization. In this case, vi is a vector object of the specialization vector<int>. Remember that a template’s name alone is not a type; a specialization is.

Please note the size of the vector is not specified, nor is the size of an element in it. The object, vi, takes care of all the necessary bookkeeping automatically.

The following for statement is an infinite loop that reads a number from the standard input, tests whether it’s not zero, and inserts it into the vector. The loop exits when the user inputs 0.

for (;;) //read numbers from a user’s console until 0 is input

The first source line inside the for statement body declares an int serving as a temporary storage. After instructing the user to input a number and press Enter, read the number into the temporary int, and test its value.

cin>>temp;
    if (temp == 0 ) break; //exit from loop?

Because our loop is infinite, a zero value is the signal to exit from the loop. As you can see, the number of the loop iterations is unlimited, as long as the user does not enter zero.

The real action begins at the following statement:

vi.push_back(temp); //insert int into the buffer

It inserts the value of the temporary int into the vector. The member function push_back() adds its argument at the end of its vector object. In other words, a vector is a dynamic array that adjusts its size as needed.

The for loop could, in fact, insert as many numbers as you like into vi. However, you didn’t see any explicit operations associated with memory management at all—the operators new and delete are never called. The secret lies inside the vector object.

Every STL container has an embedded allocator, which is basically a memory manager. After a vector object is instantiated, it starts its life with a default size of a pre-allocated memory buffer. The actual initial size is implementation dependent, but on most platforms, it is equivalent to the size of a memory page. The vector object stores its elements in the pre-allocated buffer. When no available room exists for additional elements, vector first tries to reallocate a contiguous chunk of memory. However, the neighboring memory might not be available (it can be too small, or it is already used to store other variables in the program). In that case, a full reallocation takes place—raw memory from the heap is allocated with a size large enough to store all the current elements plus additional headroom. The existing vector elements are copied to the new memory location, and the original storage is freed. Of course, the programmer is free from that bother—those operations are automatic. Still, when reallocation occurs frequently, the incurred performance penalty might become unacceptable. Remember that copying elements implies construction of every element object in its new memory location, and destruction of every element object in the previous memory location.


Previous Table of Contents Next


Products |  Contact Us |  About Us |  Privacy  |  Ad Info  |  Home

Use of this site is subject to certain Terms & Conditions, Copyright © 1996-1999 EarthWeb Inc.
All rights reserved. Reproduction whole or in part in any form or medium without express written permision of EarthWeb is prohibited.