35 Working with Vector Algorithms

Technique

Save Time By

Using the STL’s built-in algorithms

Using vector algorithms

Interpreting output

The real power of the Standard Template Library lies not in its ability to simply store and retrieve data in templated form. Rather, it lies in the built-in algorithms you can use on the various storage

facilities in the STL. Although the container classes do an excellent job of holding onto the data you put into them, the templated algorithms allow you to work with that data, sorting it, searching it, and converting it into other forms.

When you need to search, process, or remove specific items from a group, strongly consider the STL storage classes rather than creating your own classes to do the same work. You can manipulate any of them with well-proven and debugged algorithms.

The STL includes algorithm functions for iterating over collections, finding specific entries, removing specific entries, and sorting the entries in collections — to name but a few. In this technique, we look at the ways to manipulate data efficiently in a collection, using the algorithms available for vectors. In this technique, we will examine ways in which to sort, search and remove items in an STL container. These algorithms are available for any of the STL container classes, using the same names in each case. Although we will focus on the vector class in this technique, the same algorithms will work with stacks, maps, queues, and all of the rest of the STL containers. Using these algorithms will save you time in doing the most likely tasks required of applications today.

Working with Vector Algorithms

If you are presented with an array, or vector, of data, certain functions are almost always going to be requested by the user. The ability to sort the data according to its value is one of them. Another requirement is almost certainly going to be the ability to find a given data value in the vector. Finally, inserting and removing data are essential for any array. Let’s take a look at techniques for doing all of these tasks, using the STL vector class and the STL algorithms. Here’s how:

		Working with Vector Algorithms	201
1. In the code editor of your choice, create a new	2.	Type the code from Listing 35-1 into your file.
file to hold the code for the implementation of		Better yet, copy the code from the source file on
the source file.
		this book’s companion Web site.
In this example, the file is named ch35.cpp,
although you can use whatever you choose.
LISTING 35-1: USING THE STL ALGORITHMS WITH THE VECTOR CLASS
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
bool contains_c( const std::string& s )
{
for ( int i=0; i<s.length(); ++i )
if ( s[i] == ‘c’ )
return true;
return false;
}
int main(int argc, char **argv)
{
// First, create a vector out of all
// of the input strings
std::vector< std::string > elements;				1
for ( int i=0; i<argc; ++i )
elements.insert( elements.end(), argv[i] );

//Print out the elements. printf(“Original list:\n”);

std::vector< std::string >::iterator iter;

for ( iter = elements.begin(); iter != elements.end(); ++iter ) printf(“Element %s\n”, (*iter).c_str() );

//Now, sort the elements.

std::sort(	elements.begin(), elements.end() );	2
// Print them out again.
printf(“Sorted list:\n”);
for ( iter	= elements.begin(); iter != elements.end(); ++iter )

printf(“Element %s\n”, (*iter).c_str() );

(continued)

202	Technique 35: Working with Vector Algorithms
LISTING 35-1 (continued)
	// Find a specific element, if it exists.
	std::vector< std::string >::iterator ptr_iter;
	ptr_iter = std::find( elements.begin(), elements.end(), “Hello”);		3
	if ( ptr_iter != elements.end() )

printf(“Found the element %s\n”, (*ptr_iter).c_str() ); else

printf(“Didn’t find the requested element\n”);

// If we found it, remove it from the list. if ( ptr_iter != elements.end() )

elements.erase( ptr_iter );

// And relist them. printf(“Altered list:\n”);

for ( iter = elements.begin(); iter != elements.end(); ++iter ) printf(“Element %s\n”, (*iter).c_str() );

// See how many times “Why” is in the list.

int cnt = std::count( elements.begin(), elements.end(), “Why” ); printf(“Found %d entries with the name \’Why\’\n”, cnt );

// Remove entries only if they contain the letter ‘c’ std::remove_if( elements.begin(), elements.end(), contains_c ); printf(“Final list:\n”);

for ( iter = elements.begin(); iter != elements.end(); ++iter ) printf(“Element %s\n”, (*iter).c_str() );

return 0;

}

3. Save the source file in your code editor and close the code editor.

This source code utilizes the power and functionality of the Standard Template Library to do simple array manipulations. Adding items, removing them, counting the number that match a given string, searching, and sorting the array are all illustrated.

4. Compile the source code with the compiler of your choice on the operating system of your choice.

When the program is run, if you have done everything properly, you should see the output shown in Listing 35-2 in the shell window.

Working with Vector Algorithms 203

LISTING 35-2: OUTPUT FROM THE VECTOR ALGORITHM PROGRAM

$ ./a.exe Hello Goodbye Why What Iditarod Alpha Why Me Accord

Original list: Element ./a Element Hello Element Goodbye Element Why Element What Element Iditarod Element Alpha Element Why Element Me Element Accord Sorted list: Element ./a Element Accord Element Alpha Element Goodbye Element Hello Element Iditarod Element Me Element What Element Why Element Why

Found the element Hello Altered list:

Element ./a Element Accord Element Alpha Element Goodbye Element Iditarod Element Me Element What Element Why Element Why

Found 2 entries with the name ‘Why’ Final list:

Element ./a Element Alpha Element Goodbye Element Iditarod Element Me Element What Element Why Element Why Element Why

The output breaks down into several steps, matching the program steps. First, we input the data from the command line and store it into the original list, as it is

marked in the output. This occurs at the line				1 in
		the STL
the code listing. Next, we sort the list, using
sort algorithm (shown at		2 in the code listing).
sorts the entire array, com-
This single line of code

paring each element to the next and swapping them into place. The data is then output with the header sorted list. Our next task is to locate a specific string,

in this case “Hello”, within the array (see		3). If it
array is
is found, that element is removed and the

printed out once more, using the title altered list. Our next task is to count the number of times a given string (“Why”) appears in the list and print out that value. Finally, we remove all the items beginning with the letter c and print the list. All of this takes place in but a handful of lines of code, illustrating just how powerful and time saving the STL algorithms can be.

As you can see, with a minimum of code, we accomplished a rather large amount of functionality. For this reason alone, you should strongly consider using the STL vector class in your own code.

The vector class implements numerous algorithms for sorting, searching, and manipulation. You can write a single function with multiple algorithms to process large amounts of data — or even selected portions of data — simply by using iterators and the algorithm functions.

36 Deleting an Array

of Elements

Technique

Save Time By

Using the delete function with arrays

Deleting a single element from an array

Deleting an entire array

Matching deletion methods with the appropriate allocation methods

Interpreting output

Using the delete function with arrays can be one of the most confusing constructs in C++. When do you need to delete a single element, as opposed to an entire array of elements? What happens if

you don’t use the proper deletion method with the proper allocation method? Deleting a single element, when you allocate an array of elements, results in the failure of destructors to be called. Not deleting an element you allocate results in memory leaks and potential system crashes. In general, the correct deletion method must be matched with the proper invocation of the new method. Failure to do this matchup will result in memory leaks that are very hard to trace — which will eventually crash your application with enough use. If you do the work up front of matching correct allocations and de-allocations, you will save a lot of time during the debugging and maintenance process.

Always match up the allocation with the deletion of elements in your application. When in doubt, use the delete array operations (delete [] array) rather than the “normal” deletion operation (delete array) to make sure your arrays are properly deleted. Even for nonclass elements, failure to delete arrays properly can cause memory leaks. Note, however, that calling delete [] when you have allocated a pointer with new <Type> will cause a crash.

Examining Allocations

of Arrays and Pointers

The only real way to understand exactly how allocations and deallocations work is to look at an example of working with allocating single objects, with and without pointers, in either single objects or arrays of objects. Let’s do that right now, with a short example program.

1. In the code editor of your choice, create a new file to hold the code for the implementation of the source file.

In this example, the file is named ch36.cpp, although you can use whatever you choose.

Examining Allocations of Arrays and Pointers

205

2. Type the code from Listing 36-1 into your file.

Better yet, copy the code from the source file on this book’s companion Web site.

LISTING 36-1: ALLOCATING OBJECTS WITH AND

WITHOUT POINTERS

#include <stdio.h> #include <vector>

class NoPointer

{

int x; public:

NoPointer()

{

printf(“NoPointer: Void Constructor called\n”);

x = 0;

}

NoPointer( int num )

{

printf(“NoPointer: Full constructor called\n”);

x = num;

}

NoPointer( const NoPointer& aCopy )

{

printf(“NoPointer: Copy constructor called\n”);

x = aCopy.x;

}

virtual ~NoPointer()

{

printf(“NoPointer: Destructor called\n”);

}

NoPointer operator=( const NoPointer& aCopy )

{

printf(“NoPointer: operator= called\n”);

x = aCopy.x; return *this;

}

void setX( int num )

{

x = num;

}

int getX (void)

{

return x;

}

};

class PointerClass

{

char *ptr; public:

PointerClass()

{

printf(“PointerClass: Void Constructor called\n”);

ptr = NULL;

}

PointerClass( const char *str )

{

printf(“PointerClass: Full constructor

called\n”);		1
ptr = new char[ strlen(str)+1 ];
strcpy( ptr, str );

}

PointerClass( const PointerClass& aCopy )

{

printf(“PointerClass: Copy constructor called\n”);

if ( aCopy.ptr )

{

ptr = new char[ strlen(aCopy.ptr)+1 ]; strcpy( ptr, aCopy.ptr );

}

else

ptr = NULL;

}

virtual ~PointerClass()

{

	printf(“PointerClass: Destructor
	called\n”);	2
}	delete [] ptr;

PointerClass operator=( const PointerClass& aCopy )

{

printf(“PointerClass: operator= called\n”);

if ( aCopy.ptr )

{

ptr = new char[ strlen(aCopy.ptr)+1 ]; strcpy( ptr, aCopy.ptr );

}

else

ptr = NULL;

(continued)

206 Technique 36: Deleting an Array of Elements

LISTING 36-1 (continued)

return *this;

}

void setPtr( const char *str )

{

if ( str )

{

str = new char[ strlen(str)+1 ]; strcpy( ptr, str );

}

else

ptr = NULL;

}

const char *getPtr (void)

{

return ptr;

}

};

int main()

{

//Just create one of each to see what happens.

printf(“Creating np\n”); NoPointer *np = new NoPointer(5); printf(“Creating pc\n”); PointerClass *pc = new PointerClass(“Hello”); printf(“Deleting np\n”);

delete np; printf(“Deleting pc\n”); delete pc;

// Now, create an array of them.
printf(“Creating npa\n”);		3
NoPointer *npa = new NoPointer[5];
printf(“Creating pca\n”);
PointerClass *pca =	4
new PointerClass[5];

//Delete them. printf(“Deleting npa\n”); delete npa; printf(“Deleting pca\n”); delete pca;

//Now, do it the right way. printf(“Creating npa2\n”); NoPointer *npa2 = new NoPointer[5]; printf(“Creating pca2\n”);

PointerClass *pca2 = new PointerClass[5];

//Delete them. printf(“Deleting npa2\n”); delete [] npa2; printf(“Deleting pca2\n”); delete [] pca2;

//See what happens with a vector. printf(“Creating vector of PointerClass\n”);

std::vector< PointerClass > *pcv = new std::vector<PointerClass>;

for ( int i=0; i<5; ++i )

{

PointerClass pc; pcv->insert(pcv->end(), pc );

}

printf(“Deleting vector of PointerClass\n”);

delete pcv;

}

As you can see from the above code listing, we have created two different sorts of classes. The first class, NoPointer, is a simple class that contains only basic member variables, with no pointers stored in the member data of the class. The second class, PointerClass, contains pointer data that is allocated when an instance of the class is constructed and de-allocated when the instance is freed. If you look at line 1, you will see how the ptr member variable is allocated in the constructor for the PointerClass. That ptr member variable should be de-allocated at line

2 if all goes well in the class.

3.Save the source file in your code editor and close the code editor.

4.Compile the source code with the compiler of your choice on the operating system of your choice.

Examining Allocations of Arrays and Pointers

207

When the program is run, if you have done everything properly, you should see the output shown in Listing 36-2 in the shell window.

LISTING 36-2: THE OUTPUT FROM THE ALLOCATION EXAMPLE

$ ./a.exe
Creating np
NoPointer: Full constructor called
Creating pc
PointerClass: Full constructor called
Deleting np
NoPointer: Destructor called
Deleting pc
PointerClass: Destructor called		7
Creating npa
NoPointer: Void Constructor called
NoPointer: Void Constructor called
NoPointer: Void Constructor called
NoPointer: Void Constructor called
NoPointer: Void Constructor called
Creating pca
PointerClass: Void Constructor called
PointerClass: Void Constructor called
PointerClass: Void Constructor called
PointerClass: Void Constructor called
PointerClass: Void Constructor called		5
Deleting npa
NoPointer: Destructor called		6
Deleting pca
PointerClass: Destructor called

Creating npa2

NoPointer: Void Constructor called NoPointer: Void Constructor called NoPointer: Void Constructor called NoPointer: Void Constructor called NoPointer: Void Constructor called Creating pca2

PointerClass: Void Constructor called PointerClass: Void Constructor called PointerClass: Void Constructor called PointerClass: Void Constructor called PointerClass: Void Constructor called Deleting npa2

NoPointer: Destructor called NoPointer: Destructor called NoPointer: Destructor called NoPointer: Destructor called NoPointer: Destructor called

Deleting pca2

PointerClass: Destructor called

PointerClass: Destructor called

PointerClass: Destructor called

PointerClass: Destructor called

PointerClass: Destructor called

Creating vector of	PointerClass
PointerClass: Void	Constructor called
PointerClass: Copy	constructor called
PointerClass: Destructor called
PointerClass: Void	Constructor called
PointerClass: Copy	constructor called
PointerClass: Copy	constructor called
PointerClass: Destructor called
PointerClass: Destructor called
PointerClass: Void	Constructor called
PointerClass: Copy	constructor called
PointerClass: Copy	constructor called
PointerClass: Copy	constructor called
PointerClass: Destructor called
PointerClass: Destructor called
PointerClass: Destructor called
PointerClass: Void	Constructor called
PointerClass: Copy	constructor called
PointerClass: Destructor called
PointerClass: Void	Constructor called
PointerClass: Copy	constructor called
PointerClass: Copy	constructor called
PointerClass: Copy	constructor called
PointerClass: Copy	constructor called
PointerClass: Copy	constructor called
PointerClass: Destructor called
PointerClass: Destructor called
PointerClass: Destructor called
PointerClass: Destructor called
PointerClass: Destructor called
Deleting vector of	PointerClass

PointerClass: Destructor called

PointerClass: Destructor called

PointerClass: Destructor called

PointerClass: Destructor called

PointerClass: Destructor called

The important part of this output is shown in the

lines marked with	5 and 6 As you can see, we
the pointers that we allocated in
are de-allocating
the code at lines marked 3 and			4. In both cases,
we have allocated an	array of objects. If you look at

208 Technique 36: Deleting an Array of Elements

the output, you will see that the constructor for the class is called multiple times (see lines starting with 7) but that the destructor is called only once.

This introduces an immediate memory leak in the application.

Always place debugging print statements in your constructors and destructor to verify that you have called each the proper number of times and in the proper manner.

37 Creating Arrays

of Objects

Technique

Save Time By

Understanding the various ways to create arrays of objects

Declaring arrays on the stack

C++ offers three different ways to create arrays of objects, using the language constructs and the Standard Template Library (STL):

Declaring arrays on the stack: This method, using the [] construct, creates a static array that exists from the point at which it is allocated. You create a static array by writing

object-type array[ num-elements];

Creating objects on the heap

Using STL container classes to create arrays

Interpreting your output

where object-type is the class of the object you wish to create an array of, and the number of elements in the array is represented by the num-elements parameter. The advantage to this approach is that the array size is known at compile time, and the program will be loaded with the proper amount of memory. The problem with this approach is that the array exists only as long as the array is in scope. When the array variable goes out of scope, the array is destroyed.

Creating objects on the heap: This approach has the advantage of allowing you to control exactly when the array is created or destroyed — but a disadvantage is that it will not automatically “clean up” (de-allocate) after you. If you fail to de-allocate an array

(or if you de-allocate it in the wrong way), you create a memory leak in your program. You create an object on the heap by writing

object-type object;

Using STL container classes to create arrays: (We could quibble over whether the various container classes in the STL constitute separate methods of creating arrays, but for the sake of this technique, we’ll just consider the use of all of the various container classes as a single approach.) The advantage of this method is that it does not create the objects until they are actually inserted into the container class — and it automatically destroys those objects when the container class goes out of scope. Containers can be dynamically created on the stack so you can control the scope of objects in the container as well. Two disadvantages to this method: The increase in overhead is significant, and

210 Technique 37: Creating Arrays of Objects

the container classes require you to implement a number of methods in your classes — such as copy constructors, assignment operators, and virtual destructors — to avoid memory leaks. You create an STL container class by writing:

vector<object-type> array;

This technique looks at the various advantages and disadvantages of creating objects in these three different ways. By understanding how you can most easily create an array of objects in your code, you will save time when writing, debugging, and optimizing your code.

The following steps take you through all three techniques for object-array allocation in a single example:

1. In the code editor of your choice, create a new file to hold the code for the implementation of the source file.

In this example, the file is named ch37.cpp, although you can use whatever you choose.

2. Type the code from Listing 37-1 into your file.

Better yet, copy the code from the source file on this book’s companion Web site.

LISTING 37-1: CREATING AN ARRAY OF OBJECTS

#include <stdio.h> #include <string> #include <vector>

class Foo

{

std::string _str; public:

Foo(void)

{

printf(“Foo: Void constructor\n”); _str = “”;

}

Foo ( const char *s )

{

printf(“Foo: Full constructor [%s]\n”, s);

_str = s;

}

Foo( const Foo& aCopy )

{

printf(“Foo: Copy constructor\n”); _str = aCopy._str;

}

virtual ~Foo()

{

printf(“Foo: Destructor\n”);

}

Foo operator=(const Foo& aCopy)

{

_str = aCopy._str; return *this;

}

std::string String()

{

return _str;

}

void setString( const char *str )

{

_str = str;

}

};
int main()
{
printf(“Creating array via new\n”);		1
Foo *f = new Foo[2](“Hello”);
printf(“Creating array on heap\n”);
Foo f1[3];	2
// Create a vector
printf(“Creating vector of foo\n”);	3
std::vector<Foo> fooVector;

printf(“Adding objects to vector\n”); Foo f2;

Foo f3; Foo f4;

fooVector.insert( fooVector.end(), f2 ); fooVector.insert( fooVector.end(), f3 ); fooVector.insert( fooVector.end(), f4 );

printf(“Deleting array on heap\n”); delete [] f;

}

Technique 37: Creating Arrays of Objects

211

Looking at the above code listing, you can see that there are three different arrays defined in the program. At 1, we allocate an array from the stack, using the new operator. At 2, we allocate an array on the heap, using the standard array syntax of C++. Finally, at 3, we see how the Standard Template Library vector class is used to define an array of objects.

3. Save the source file in your code editor and close the code editor.

4. Compile the source code with the compiler of your choice on the operating system of your choice.

When the program is run, if you have done everything properly, you should see the output shown in Listing 37-2 in the shell window.

LISTING 37-2: OUTPUT FROM THE ARRAY-ALLOCATION PROGRAM

$ ./a.exe			4
Creating array via new
Foo: Full	constructor [Hello]
Foo: Full	constructor [Hello]		5
Creating array on heap
Foo: Void	constructor
Foo: Void	constructor
Foo: Void	constructor		6
Creating vector of foo
Adding objects to vector
Foo: Void	constructor
Foo: Void	constructor
Foo: Void	constructor
Foo: Copy	constructor
Foo: Copy	constructor
Foo: Copy	constructor
Foo: Destructor
Foo: Copy	constructor
Foo: Copy	constructor
Foo: Copy	constructor
Foo: Destructor
Foo: Destructor			7
Deleting array on heap
Foo: Destructor

Foo: Destructor

Foo: Destructor

Foo: Destructor

Foo: Destructor

Foo: Destructor

Foo: Destructor

Foo: Destructor		8
Foo: Destructor
Foo: Destructor

Foo: Destructor

As you can see, the static array is created at the point at which the compiler finds the code for it. The dynamic array is created at the point at which the new operator is used to allocate it, and the vector array does not begin to allocate space for the objects until they are inserted into the vector.

Take a look at a breakdown of the lines shown in Listing 37-2:

4 This line shows the point at which the arrayis allocated with new. As you can see, two constructor calls are made, indicating that two objects were created and put into the array. Note that because we gave the new operator a constructor argument, it calls the full constructor for the class.

5 This line shows where we allocated a blockof objects on the heap, using standard C++ array syntax. Note that the void constructor is used for these objects, initializing all three of them (one for each array element).

6 This line shows where we used the StandardTemplate Library vector class to store objects. No objects were created in this call. We then allocate several objects on the heap and add them to the vector. Notice that the objects are copied into the vector using the copy constructor to create new instances of the class.

7 Here we delete the array that we allocatedwith the new call. There should be two objects deleted in this process and the output shows that there are, in fact, two objects destroyed.

8 This line shows the final destruction of theobjects that were allocated in the array on the heap.

If you count the total number of destructor calls at the end of the output listing, you will see that there are 11 of them. This might not seem obvious from the fact that we allocated only eight objects in the

212 Technique 37: Creating Arrays of Objects

main program (two in the new array, three in the heap array, and three in the vector). However, because the copy constructor was invoked three times, three additional objects were created, making a total of 11.

If you take a look at the output from the program (in Listing 37-2), you see that the vector class does significant manipulation of the data in the vector — that’s to store it efficiently and make room for new objects. Therefore, if your objects require a lot of overhead for their creation and destruction, the vector class is not a good choice for a container. You would be better off pre-allocating a large number of the objects — and using that array, whether static or dynamic, to store your information.

One important thing to notice in the code is that we always use the delete [] method for de-allocating arrays of objects. If you replace the delete [] method with a simple delete call, you will find that the code does not call the destructor for each member of the array, and that memory leaks can easily occur. This risk of memory leakage is particularly important if you store pointers to objects in your array, and access them through any sort of base class.