Array Implementations

Amit Schreiber §

Introduction

This website contains implementations of an Array wrapper class in the C++ language, along with descriptions of class design decisions and the evolvement up to the final code. Some very common programming techniques are introduced, along with some more advanced ones. References to books and websites are also provided for those who want to learn more.

Target Readers

The target audiences for this website are beginner C++ programmers, who want to learn more about common techniques in C++ programming.

A Note About Style

The style used for the code presented here resembles the C++ STL (Standard Template Library) code style. For more information about STL, see [1].

A Short Introduction To Iterators

An iterator is an abstraction of a pointer to some data, in the sense that it supports dereferencing (operator*), forward and backward movement over the data (operator++ and operator--) and comparison (at least operator== and operator!=). Iterators are usually used to traverse (go over) the data inside a container, like a linked list, just as "simple" pointers are used to traverse arrays.

It is obvious that pointers are one kind of iterators, but thanks to operator overloading a class can implement the required operators to be considered and used where a pointer is used. This is useful, for example, when the data is not contiguous in memory.

Consider the following code:

int arr[] = {1,2,3}; // the size of array is determined by the compiler
int* arr_end_p = &arr[sizeof(arr)/sizeof(arr[0])]; // pointer to one position past the last element in the array
for (int* parr = arr; parr != arr_end_p; ++parr) {
	std::cout << *parr << std::endl;
}

Now let's assume a more dynamic container, like a linked list, is required for this piece of code (for example, the elements in the container can be determined only during program run):

IntList ints;
ints.add(1);
ints.add(2);
ints.add(3);
for (IntListIterator it = ints.begin(); it != ints.end(); ++it) {
	std::cout << *it << std::endl;
}

Without getting into details about IntListIterator, one thing is certain about it: it is not a simple C++ pointer [2]. A dynamic linked list, such as the IntList used in this example, does not hold its data in contiguous memory, so to iterate over it, an entity which "knows something" about the internal structure of the list is required. That is the class IntListIterator.

Type Requirements In Templated Code

Type requirements are the operations required from the type used inside templated code, imposed by the use of the type by the code. For example, consider the following code:

template <typename T> void DoOpen(T t) {
	t.open();
	return;
}

There is one obvious requirement from the type T, and another two a little less obvious:

a member function by the name of open, which can be called without any parameter [3],
a copy constructor, because the variable t is passed by value to DoOpen(), and
a destructor, because the variable t is destroyed when DoOpen() returns and it goes out of scope.

Exception Safety

Exception safety is the notion of "good behavior" of a class if an exception occurs while executing its code. This is especially critical for class templates and even more for containers.

Exception safety for a class template Array (whose template argument is T) is divided into 3 levels of safety (called guarantees):

Basic guarantee: Even in the presence of exceptions thrown by T or other exceptions, the Array objects do not leak resources.
Strong guarantee: If an operation terminates because of an exception, program state will remain unchanged.
Nothrow guarantee: The function will not emit an exception under any circumstances.

In the presented code the strong guarantee will be achieved, assuming the following:

T has a default constructor.
T has a nonthrowing destructor [4].
T has an exception-safe copy assignment (assignment operator), meaning if the assignment of one T object to another leaves the target (l-value) T object in a valid state even if an exception occurred during the assignment.

The need for these assumptions will be explained further in the FixedArray and DynamicArray pages. For a detailed explanation and for more information about the levels of exception safety, see [5].

Arrays Implementations

The implementations provided are divided into 2 main sections: fixed arrays, and dynamic arrays. Fixed refers to the fact that the size of the array is a known constant at compilation time and cannot change at runtime. Dynamic means the size of the array can change during runtime.

An additional implementation of an array that can change its size in log(size) time is supplied without further explanations. The coding style and design resembles DynamicArray's, only a little more complicated.

The files of the implementations discussed here can be downloaded:

Common.h is required for every compilation, since it contains common definitions. FixedArray.h is required to compile and run FixedArray. DynamicArrayImpl.h and DynamicArray.h are required to compile and run DynamicArray.
Note: The entire code is inside a namespace, Arrays. To compile the array classes add the following line at the beginning of your code:

using namespace Arrays;

References And Notes

[1]
For a complete STL implementation see SGI's STL implementation and documents.
A good book to learn practical STL (and C++ in general) from is C++ Primer.

[2]
This is actually not 100 percent correct. If, for some strange reason, the linked list is implemented as a continuous array in memory - then IntListIterator can be a "simple" pointer.

[3]
This means that either open() has no parameters or all its parameters have default values.

[4]
To understand why destructors should not throw see this article by Herb Sutter, at the section "Destructors That Throw and Why They're Evil".

[5]
An example of exception safe class design can be found in the Guru Of The Week column number 59.
A good book to learn about exception safety and many other interesting issues is Exceptional C++.
More about the different kinds of exception safety guarantees can be found here.

This page has been visited times since last reset

This work was done as a programming project under the supervision of Dr. Yechiel Kimchi
This is the top of a multifile document. © 2003 Amit Schreiber & Yechiel M. Kimchi. All rights reserved.
Permission is granted to print these pages for personal use only.
Permission to quote parts of this work for academic usage and research is granted,
provided an appropriate credit is given and a reference to this original document is supplied.
For all other purposes a written permission in advance from at least one of the CopyRight holders
is required prior to any usage.
We appreciate any constructive comment that will improve the contents of these pages
and the presentation of the subject.
Location: http://www.cs.technion.ac.il/users/yechiel/CS/AmitSchreiber/index.html
Created: 2003/08/13 Last updated: 2003/08/13