Computer Science 3710 -- March 05, 2004

Most of the textbook that we have covered so far has dealt with writing programs using the classes available to us in the standard C++ library. Starting with Chapter 9, we started to create our own classes. In Chapters 11, 12, and 13 we continue to look under the hood, to get a rough idea of technical details behind how some of these standard classes work.

The purpose of this chapter is to create a (simplified) version of the standard library's vector class to demonstrate several important aspects of the implementation of C++ classes. Like the vector class, we will want our new vector class (called Vec) to be able to hold values of any type specified by the user, therefore, we need a way to create a generic class in C++.

Template classes

During our definition of the class, we can specify that the vector is to hold any type by defining a template class which, in principle, is the same as a template function except that the template/instantiation mechanism is applied to classes instead of functions. We create a template class using the syntax:

In the class definition, all occurrences of the generic T type will be replaced with the type specified by the user when an object of the Vec class is created. When creating an object of type Vec we must specify the type of the elements that the Vec contains. We do this the same way that we created a vector or list — we specify the actual element type inside angle brackets after the class name:

This will create a version of the Vec class that can store double values as its elements. A double version of the Vec class will be instantiated in which all occurrences of the generic type T are replaced with double.

Internal representation

Next we have to think about the internal representation of our vector container. The elements in the vector will be stored in a contiguous memory region which will be allocated and maintained by our Vec class. In the spirit of iterators, we will store two pointers — the data pointer will point to the first element of the vector (i.e. the beginning of the memory region) and the limit pointer will denote one past the vector's last element (i.e. one element past the memory region allocated by our Vec class). Because these members form the implementation of our class, we will put them in the private section.

The (generic) type of the elements of the Vec is given by T. Therefore, data and limit are of type T*. In order to actually manage these two pointers, we'll use a memory allocation class provided by the standard C++ library that allows for more flexibility than new and delete. More information on this flexible memory allocator, which will allow us to appropriately initialize each element of our vector, will be presented later.

Constructors

Next, we need to instruct the Vec class how to build a Vec object. Initially, we'll define three constructors:

We can combine the second and third constructors into a single constructor which takes a default argument for the element value. The value of this default argument will be the result of the element's default constructor, if it has one. Again, remember that because this is a generic class, the elements stored in the vector are of type T. We delegate all the work for these two constructors to an overloaded function called create() whose definitions we will add later to the private part of the class. These methods will appropriately set the data and limit data members.

The explicit keyword prevents implicit conversions of values of type std::size_t to a Vec. More information on implicit conversions is presented in the next chapter.

Type definitions

Next, we define the types for our Vec class. These types include size_type, iterator and const_iterator which we have seen before. The iterators are simply variants of the T* type. We also define a reference, const_reference and value_type, whose types should be obvious from their names. These last three types (in addition to the push_back() method that we will define later), will enable users of our Vec class to use the back_inserter iterator adapter to automatically extend the vector when used, for example, in the context of one of the functions from the <algorithm> library (e.g. copy()).

Note that for consistency, we changed the std::size_t type of the first parameter of the second constructor to size_type and we also changed the T* type of the data and limit data members to iterator. We do this so that if we decide to change the iterator or size_type types later on, we only have to modify the corresponding typedef and nothing else in the class definition.

Indexing: Overloading operator[]

The standard library's vector class provides a way to randomly access elements using the indexing operator []. In order to add this capability to our Vec class, we must override the [] operator by supplying our own function or method to retrieve the appropriate element. We do this by introducing two variants of the operator [](size_type i) method. The syntax looks a bit strange at first — what is being defined is a new operator function whose name is [] and whose parameter (i.e. the index) is of type size_type.

Because we want the ability to use the indexing operator on the left hand side of an assignment, we return a reference to the element retrieved by the method. This way, we can use our Vec class in the following context:

and 1.23 will be assigned to the first element (provided that vdbl had previously allocated space for at least one element.) We define two variants of the [] operator, a non-const and a const version, both of which essentially do the same thing (i.e. return the element stored at the ith position from the data pointer), except that the second version can be used in a const context.

When overloading operators, we generally have the choice as to whether the operator function will be a member function (i.e. a method) or a non-member function (i.e. a global function). If a binary operator function (e.g. operator+) is defined as a member function, then it will take one argument, namely the right-hand operand (the left hand operand will be implicitly passed, as discussed earlier). If a binary operator function is implemented as a global function, then the argument list for the operator function will have two (explicit) parameters representing the left-hand and right-hand operands. The same idea for unary operators holds except that in both cases, the number of arguments is decreased by one.

For the index operator (and the assignment operator, which we will see below), however, we have no choice — the operator function must to be defined as a member function of the appropriate class.

Size and iterators

Next, we define the size() and the iterator methods. The size() method is trivial — we simply return the difference between the limit and data pointers. This result, which will be of type ptrdiff_t, is then (implicitly) typecast to a size_type value for consistency. Similarly, the begin() and end() iterator methods are trivially defined to return the data and limit pointers, respectively. As with the [] operator method, we define non-const and const versions of these two iterator methods:

Copy Control

One important feature that we have not yet considered in the class design is that of copy control. We have to ask ourselves the following questions:

A designer of a C++ class that manages its own resources (e.g. in the case of our Vec class, we are managing a dynamic memory resource) must carefully consider these questions and provide an appropriate implementation that does the ``right thing'' in all these circumstances.

Copy Constructor

The issues presented by the first three questions above are all handled by the copy constructor. In general for a class named V, the copy constructor is of the form:

(note that constructors have no return value). This constructor basically tells an object how to make a duplicate of itself. In the case of our Vec class below, we rely on yet another variant of our already overloaded create() member function to build an entirely new Vec object whose elements are copies of the original. The implementation of this method will be presented later. One important aspect of the copy constructor in this context is that it cannot simply copy the data and limit pointers. If we did, then any changes the elements of the copy would affect the original elements as well, since data and limit would denote the same region in memory. We want the Vec copy constructor to generate a true copy of the original Vec object. This will be taken care of by the third variant of the create() method.

As mentioned, the copy constructor is used to build a copy of an object when one object is used in the initialization of another. For example:

Note that in the above case, v2 is constructed using the copy constructor. The copy constructor is also called (implicitly) when passing an object by value into a function or method and when returning an object by value from a function or a method.

Assignment Operator

Next, we must define an assignment operator to take care of Question #4 above. In general, for a class V, the assignment operator will be of the form:

This is similar to the prototype of [] operator, defined earlier. The const V& parameter represents the object on the right-hand side of the assignment operator. The left-hand operand is an implicit argument because, as with the [] operator, we must define the assignment operator as a member of the class. Note that the assignment operator returns a reference so that the assignment operator can be chained (e.g. v1 = v2 = v3).

Definition of the assignment operator

Unlike the copy constructor, which is creating a new element from scratch, we have to be careful when defining the assignment operator. In particular, we must be careful of assignments such as

v1 =
v1

(i.e. self-assignments). The definition of the assignment operator function is presented below:

Note that we check for self assignment by comparing the address of the method's parameter (i.e. the right-hand side of the assignment operator) with the this pointer. this is a pointer to the object upon which the member function was invoked — in this context, it is a pointer to the object on the left-hand side of the assignment operator. As mentioned earlier, whenever we call a member function, a pointer to the object upon which the member function was called is implicitly passed to the member function. This pointer is stored in the this pointer.

If we are not doing self assignment, then we must deallocate the storage occupied by the object on the left hand side and create new storage that is initialized with all the elements in the Vec object on the right hand side. We do this using the uncreate() member function (which we will define later) and the create() function. We then always return a reference to the left-hand side of the assignment operator by deferencing the this pointer. If we didn't check for self assignment, then we would end up deallocating the Vec's member and then attempt to make a copy the deallocated storage. Needless to say, this will cause run-time errors.

Something else you should note about the assignment operator method is that because we are defining this method outside the class, we must use the Vec<T> syntax whenever referring to the Vec type before the scope resolution operator, therefore, we must write:

After the scope resolution operator, we no longer have to use the Vec<T> syntax and can therefore write the parameter as const Vec& rhs. We could also have written the parameter type as const Vec<T>& rhs, but it is not necessary.

One important distinction should be made between the copy constructor and the assignment operator. Consider the following code:

When we create v2, the syntax would suggest that we are using the assignment operator method. However, this is not the case. Because we are initializing (a previously non-existent) v2 with v1, the statement Vec v2 = v1 is actually calling the copy constructor to make a copy of v1 to be stored in v2. Assignment and initialization in C++ are two different operations!

Destructors

Finally, in answer to Question #5 above, we must write a function that will deallocate the region of memory that was allocated by the create() methods. To do this, we must define a destructor for our class. Generally, given a class named V, the destructor is of the form:

The destructor takes no parameters and returns no value. In our Vec class below, we simply call the uncreate() method (introduced when we defined the assignment operator) to delete the elements from the memory region and then to delete the memory region itself. Again, we'll define the uncreate() method in the next section. Whenever a Vec object goes out of scope, the destructor will be automatically called to give the object an opportunity to deallocate its resources.

Generally speaking, whenever a class does any resource management. you should always define a default constructor, copy constructor, assignment operator and destructor for the class. If you don't, the compiler will synthesize versions of these functions that will almost certainly not have the right behaviour.

The compiler will also synthesize a default constructor, but only if you don't define any constructor for the class.

Memory allocation using the allocator class

Finally, it is necessary to define our low-level memory management functions to actually allocate/initialize and deallocate the memory region that will be used to hold the elements in our Vec class. We cannot use the new/delete memory management functions because new requires that the element type stored in our Vec have a default constructor that will be called for every element in the array created by new. This not only restricts the types that we can store in our Vec, it also could be wasteful if we specify a value to use as the initial value of the elements of the vector since two separate initialization iterations would have to be done in that case.

To get around this we will use the allocator class of the standard library which provides us with a lower-level (and more flexible) facility for memory management. We introduce an allocator object object of the appropriate type (allocator<T>) that we can use to allocate and deallocate regions of memory.

Our strategy for doing the memory allocation is to always double the memory region whenever we run out of room to store new elements. As a result, we'll also introduce another private data member called avail that will denote the element that is one passed the last element in the vector. We will also change the meaning of the limit data member which will now denote one past the allocated memory. When avail == limit, then the class will have to allocate more memory.

The push_back() method, given in the class definition below, does this test and if it is true, it will call the grow() helper function. The push_back() method will then call the uncheck_append() method to store the new element in the vector. These helper methods are defined later.

Definition of the create()/uncreate() functions

We now give the definitions of the three overloaded create() methods and the uncreate() method. The first create() method has no parameters and is called by the default constructor. Its implementation sets all three data member pointers (data, avail and limit) to zero to indicate that the vector is empty and has no storage allocated for it:

The second create() method takes an initial vector size and a value. It will then allocate a region of the requested size and fill each element in the memory region with the given value. To allocate the memory, we use the allocate() method of the allocator object, passing it the number of elements we want to allocate. The allocate() method returns a pointer to the initial element, which we then assign to data. We then update the limit and avail members to point to one past the last allocated element in the memory region. Finally, we use the standard uninitialized_fill() function which will iterate over the (uninitialized) cells denoted by its two iterator arguments (data and limit in our case) and store a copy of the initial value in each location.

The third create() method was called by the copy constructor and assignment operator method and takes two iterators arguments that denote a range of elements to copy. It will allocate enough memory to store all the elements denoted by the range and will then call the uninitialized_copy() function to store a copy of each element in the given range to each cell of the newly allocated memory region.

Finally, the uncreate() function, which is called by the assignment operator and by the destructor, will deallocate each of the elements in the memory region and then delete the memory region itself. It does this by first checking the data member — if it is zero, then all it has to do is simply reset the data, limit and avail data members to zero. If it non-zero, then we use an iterator to move backwards through the memory region deallocating each of the elements as we go by calling the destroy() method of our allocator object. (By convention, we deallocate things in the reverse order that we allocated them). Finally, we call the deallocate() method of our allocator object. This function takes a pointer to the initial element as well as the number of elements to delete. It then frees up the corresponding memory region:

Support functions for push_back()

Lastly, we must define the two support functions that were called by our push_back() method. The grow() method is called when we have exhausted our memory region (i.e. when avail == limit) and must allocate more space. We first determine how much space to allocate. If we haven't allocated any space at all, then we will allocate room for one element, otherwise we will double the amount of memory we allocated previously. Note that to determine how much memory we allocated previously, we subtract the pointers limit and data, which yields a ptrdiff_t type. We then use the std::max() function to determine the larger of this number and 1. We must typecast the 1 to a ptrdiff_t type because std::max() requires that both of its arguments be exactly the same type. The std::max() call will either return 1 if no memory was previously allocated (i.e. we have an empty vector with limit = data = avail = 0) or it will return a number denoting twice as much memory as was previously allocated.

We then allocate the appropriate amount of storage and copy over the elements from the original memory region using the uninitialized_copy function (as before). After deallocating the memory used by the old memory region, we update our data, avail and limit pointers appropriately.

The unchecked_append() method simply builds a copy of the supplied value and stores it in the next available location in the memory region (denoted by avail) using the allocator's construct() method. The avail pointer is then updated to denote the next free cell in the memory region. Note that this method does not check to make sure that there is room in the allocated memory region for the new element, so the calling function must make sure that space exists in the memory region before calling this function (push_back() does satisfy this constraint).

The Completed Vec Class

The header file below contains the entire class definition. Note that a trivial empty() predicate and a clear() method were added to the class definition for completeness.

#ifndef VEC_H
#define VEC_H

#include <algorithm>
#include <cstddef>
#include <memory>

template <class T> class Vec {
public:
	typedef T* iterator;
	typedef const T* const_iterator;
	typedef size_t size_type;
	typedef T value_type;
	typedef T& reference;
	typedef const T& const_reference;

	Vec() { create(); }
	explicit Vec(size_type n, const T& t = T()) { create(n, t); }

	Vec(const Vec& v) { create(v.begin(), v.end()); }
	Vec& operator=(const Vec&);	// as defined in 11.3.2/196
	~Vec() { uncreate(); }

	T& operator[](size_type i) { return data[i]; }
	const T& operator[](size_type i) const { return data[i]; }

	void push_back(const T& t) {
		if (avail == limit)
			grow();
		unchecked_append(t);
	}

	size_type size() const { return avail - data; }

	iterator begin() { return data; }
	const_iterator begin() const { return data; }

	iterator end() { return avail; }
	const_iterator end() const { return avail; }
	void clear() { uncreate(); }
	bool empty() const { return data == avail; }

private:
	iterator data;	// first element in the `Vec'
	iterator avail;	// (one past) the last element in the `Vec'
	iterator limit;	// (one past) the allocated memory

	// facilities for memory allocation
	std::allocator<T> alloc;	// object to handle memory allocation

	// allocate and initialize the underlying array
	void create();
	void create(size_type, const T&);
	void create(const_iterator, const_iterator);

	// destroy the elements in the array and free the memory
	void uncreate();

	// support functions for `push_back'
	void grow();
	void unchecked_append(const T&);
};

template <class T> void Vec<T>::create()
{
	data = avail = limit = 0;
}

template <class T> void Vec<T>::create(size_type n, const T& val)
{
	data = alloc.allocate(n);
	limit = avail = data + n;
	std::uninitialized_fill(data, limit, val);
}

template <class T>
void Vec<T>::create(const_iterator i, const_iterator j)
{
	data = alloc.allocate(j - i);
	limit = avail = std::uninitialized_copy(i, j, data);
}

template <class T> void Vec<T>::uncreate()
{
	if (data) {
		// destroy (in reverse order) the elements that were constructed
		iterator it = avail;
		while (it != data)
			alloc.destroy(--it);

		// return all the space that was allocated
		alloc.deallocate(data, limit - data);
	}
	// reset pointers to indicate that the `Vec' is empty again
	data = limit = avail = 0;

}

template <class T> void Vec<T>::grow()
{
	// when growing, allocate twice as much space as currently in use
	size_type new_size = std::max(2 * (limit - data), ptrdiff_t(1));

	// allocate new space and copy existing elements to the new space
	iterator new_data = alloc.allocate(new_size);
	iterator new_avail = std::uninitialized_copy(data, avail, new_data);

	// return the old space
	uncreate();

	// reset pointers to point to the newly allocated space
	data = new_data;
	avail = new_avail;
	limit = data + new_size;
}

// assumes `avail' points at allocated, but uninitialized space
template <class T> void Vec<T>::unchecked_append(const T& val)
{
	alloc.construct(avail++, val);
}

template <class T>
Vec<T>& Vec<T>::operator=(const Vec& rhs)
{
	// check for self-assignment
	if (&rhs != this) {

		// free the array in the left-hand side
		uncreate();

		// copy elements from the right-hand to the left-hand side
		create(rhs.begin(), rhs.end());
	}
	return *this;
}

#endif
Vec.h

March 05, 2004 (Friday)

Chapter 11: Defining abstract data types

Template classes

Internal representation

Constructors

Type definitions

Indexing: Overloading `operator[]`

Size and iterators

Copy Control

Copy Constructor

Assignment Operator

Definition of the assignment operator

Destructors

Memory allocation using the `allocator` class

Definition of the `create()`/`uncreate()` functions

Support functions for `push_back()`

The Completed `Vec` Class

March 05, 2004 (Friday)

Chapter 11: Defining abstract data types

Template classes

Internal representation

Constructors

Type definitions

Indexing: Overloading operator[]

Size and iterators

Copy Control

Copy Constructor

Assignment Operator

Definition of the assignment operator

Destructors

Memory allocation using the allocator class

Definition of the create()/uncreate() functions

Support functions for push_back()

The Completed Vec Class

Indexing: Overloading `operator[]`

Memory allocation using the `allocator` class

Definition of the `create()`/`uncreate()` functions

Support functions for `push_back()`

The Completed `Vec` Class