34 Implementing Your

Own Array Class

Technique

Save Time By

Implementing array classes with limited overhead

Using a vector class that stores strings

Interpreting the output

After you have learned how to use the STL vector class (see Technique 33), it is very instructive to see how you might implement the same sort of class yourself — but with more limited over-

head. Here’s a look at implementing a simple vector class that not only stores strings, but can also insert, delete, and iterate.

Creating the String Array Class

As we saw in Technique 33, the overhead in using the Standard Template Library (STL) is rather high when you want to add only a single array to your program. If you are using multiple array classes, you might as well use the STL, because that way you only have to pay the price (in terms of memory and application size) once. Each array class beyond the first uses negligible space in your application. Let’s create a simple string array class that illustrates how easy it is to create array classes for your application that work with specific data types. The following steps show you how:

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 ch34.cpp, although you can use whatever you choose.

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

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

Creating the String Array Class 197

LISTING 34-1: CREATING YOUR OWN STRING ARRAY CLASS

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

using namespace std;

class MyStringArray

{

string *_strings;

int	_numstrings;
int	_chunksize;
int	_numused;

void expand()

{

// Allocate a new block

string *newBlock = new string[ _numstrings + _chunksize ];

_numstrings += _chunksize;

for ( int i=0; i<_numused; ++i ) newBlock[i] = _strings[i];

// Delete the old array delete [] _strings;

// Re-assign the pointer _strings = newBlock;

}

public:

MyStringArray(void)

{

_chunksize = 10;

_strings = new string[ _chunksize ]; for ( int i=0; i<_chunksize; ++i )

_strings[i] = “”; _numstrings = _chunksize; _numused = 0;

}

MyStringArray( int nSize )

{

_chunksize = 10;

if ( nSize <= _chunksize )

{

_strings = new string[ _chunksize

];

_numstrings = _chunksize;

}

else

{

_strings = new string[ nSize ]; _numstrings = nSize;

}

_numused = 0;

}

virtual ~MyStringArray(void)

{

delete [] _strings;

}

// Insert at start

void insert_string( const string& s )

{

// See if it will fit.

if ( _numused == _numstrings ) expand();

//It will now fit, move everything up for ( int i=_numused; i>=0; --i )

_strings[i] = _strings[i-1];

//Put in the new one

_strings[0] = s; _numused ++;

}

void append_string( const string& s )

{

// See if it will fit.

if ( _numused == _numstrings ) expand();

// Put in the new one _strings[_numused] = s; _numused ++;

}

string remove_at( int idx )

{

if ( idx < 0 || idx >= _numused ) return string(“”);

// Save this one

string ret_string = _strings[idx]; // And copy all the others after it

back

for ( int i=idx; i<_numused; ++i ) _strings[i] = _strings[i+1];

_numused--; return ret_string;

}

string get_at(int idx)

{

if ( idx < 0 || idx >= _numused ) return string(“”);

return _strings[idx];

}

int size()

(continued)

198 Technique 34: Implementing Your Own Array Class

LISTING 34-1 (continued)

{

return _numused;

}

};
int main(int argc, char **argv)
{
MyStringArray s(5);
for ( int i=0; i<argc; ++i )
{	printf(“Appending %s\n”, argv[i] );
		1
}	s.append_string( argv[i] );
printf(“Initial String Array:\n”);
for ( int j=0; j<s.size(); ++j )
	printf(“String %d = [%s]\n”, j,
s.get_at(j).c_str());
if	( s.size() > 5 )
{	string str = s.remove_at(5);		4
	printf(“Removed string %s\n”,

str.c_str());

}

printf(“Final String Array:\n”); for ( int i=0; i<s.size(); ++i )

printf(“String %d = [%s]\n”, i, s.get_at(i).c_str());

}

This source code utilizes our simple array functionality to add, remove, and iterate over strings in an open-ended array structure.

Now, our code is not quite as polished as the STL vector class, but it should work just as well. More importantly, when the code is compiled on my system, it produces an executable of less than 100 KB (rather than the 400KB executable of our previous example), the majority of which is the STL string 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.

When the program is run, if you have done everything properly, you should see the following output in the shell window:

$ ./a.exe 1	2	3 4 5 6 7			2
Appending ./a
Appending	1
Appending	2
Appending	3
Appending	4
Appending	5
Appending	6
Appending	7
Initial String			Array:		3
String 0 = [./a]
String 1 = [1]
String 2 = [2]
String 3 = [3]
String 4 = [4]
String 5 = [5]
String 6 = [6]
String 7 = [7]
Removed string			5

Final String Array:

String 0 = [./a]

String 1 = [1]

String 2 = [2]

String 3 = [3]

String 4 = [4]

String 5 = [6]

String 6 = [7]

The output from this program is as expected: We append each of the input arguments to our array, watching it grow as we do so. This is illustrated begin-

ning at the lines marked			1 in the code and 2 in
the output. Next, we	print out the array, expecting to
see all of the values displayed (see						3 in the out-
put). As expected, we see all eight				data values. Next,

the code removes the fifth data element, as shown at 4 in the code listing. We then print out the arrayonce more, to show that the value was removed and

the other data values remain.

Creating the String Array Class 199

Implementing your own array class can save you considerable time in trying to reduce code size, and allows you to use your code in places where it might not otherwise fit due to memory constraints.

As you can see from this output, we can create our own array class that implements the majority of the functionality of the STL vector class at a fraction of the memory and speed needed.

If memory or speed is an issue, stay away from the Standard Template Library and its array classes; roll your own. You will see marked speed increases, vastly less memory consumption, and greater ease of debugging. If you are not as concerned about memory usage, use the STL: It is already debugged and (no offense) probably better documented than your own classes. In addition, STL code is versatile: Versions of the STL have been ported to nearly all compilers and operating systems.