DynamicArray

Array Implementations --> DynamicArray class

Introduction

A dynamic array is an array with the following capabilities:

Checking the size of the array.
Checking the validity of the operation array[i] for a given i.
Checking the content of the array. The content of an array is defined to be the largest index among the indices used for reading or writing. When the content of an array is k, the largest index of the used elements is k-1.
The array is never full - if the size of the array is n, once the element with index n-1 is used (which means content == size), the array grows larger (in a preset manner, e.g. doubles its size).

By definition, a dynamic array must use dynamic allocation because when the array changes its size, it must reallocate its contained memory. This makes maintaining exception safety a lot trickier than in the FixedArray class. A common technique of better encapsulation solves the exception safety problem.

Requirements From A DynamicArray Class

A dynamic array class should:

Support all the requirements of the static array class, and
provide all the requirements that derive from its definition, and
be exception safe.

The Implementation And Exception Safety

This is the interesting part. The implementation could have been simple if the exception safety requirement was not there. A simple example why this is important can be seen in the following (naive) assignment operator implementation:

template <typename T>
class DynamicArray {
public:
...
DynamicArray& operator=(const DynamicArray& other) {
	if (this == &other)
		return *this;

	size_ =  other.size_;
	content_ = other.content_;
	delete[] arr_;
	arr_ = new T[size_];
	for (size_type i=0; i<content_; ++i) {
		arr_[i] = other.arr_[i]; // may throw
	}

	return *this;
}
...
private:
	size_type size_;
	size_type content_;
	T* arr_;
};

This assignment operator is fine, unless T's assignment operator throws an exception in one of the assignments done in the bolded line. In such cases, the DynamicArray object will be left in an invalid state because the content_ member will suggest there are more valid members than there actually are.
The copy constructor imposes the same limitations.

There are many solutions to the exception safety problem. The solution shown here, called The "Impl" Idiom [1], uses better encapsulation. Namely, the implementation details are moved to another class, called DynamicArrayImpl, which contains all of DynamicArray's private members and some helper functions. As you will see in the implementation, DynamicArrayImpl is a struct, which implies the fact that it should be used by some other class. Let's look at DynamicArrayImpl:

template <typename T>
struct DynamicArrayImpl {
    DynamicArrayImpl(const size_type size)
        : size_(size), content_(0), arr_(size==0 ? 0 : new T[size]) {}

    ~DynamicArrayImpl() 
    { 
		delete[] arr_; 
    }

    void swap(DynamicArrayImpl& other) throw()
		// this function cannot throw an exception
    {
        std::swap(size_, other.size_);
        std::swap(content_, other.content_);
        std::swap(arr_, other.arr_);
    }

    void fill_from(const DynamicArrayImpl& other)
    {
        content_ = 0;

        while (content_ < other.content_ && content_ < size_)
        {
            arr_[content_] = other.arr_[content_];
            ++content_;
        }

    }

    size_type size_;
    size_type content_;
    T* arr_;

private:
    // Do not allow copies
    DynamicArrayImpl(const DynamicArrayImpl& other);
    DynamicArrayImpl& operator=(const DynamicArrayImpl& other);
};

The constructor and destructor are straight-forward. The interesting things are the helper function swap() and fill_from(). swap() simply swaps the members between this instance and the other DynamicArrayImpl instance. Like the bolded comment says, swap() cannot throw an exception, and even explicitly says it using the throw() declaration. This is very important for the exception safety of DynamicArray.
fill_from() simply copies elements from another DynamicArrayImpl instance into this instance. The way it is written solves the exception safety issue of the copying showed in the previous code sample - if, during the copying, one of the assignments throws the DynamicArrayImpl will stay valid in the sense that content_ will be true to the actual number of valid T objects in the array (content_ is incremented only after each successful assignment.)
Now let's see how DynamicArray is implemented using DynamicArrayImpl:

template <typename T>
class DynamicArray {
public:
    typedef T value_type;
    typedef T* iterator;
    typedef const T* const_iterator;
    typedef T& reference;
    typedef const T& const_reference;

    explicit DynamicArray(const size_type sz) : impl_(sz) {}
    DynamicArray(const DynamicArray& other) 
        : impl_(other.impl_.size_) // may throw an exception
    {
        impl_.fill_from(other.impl_); // may throw an exception
    }
    DynamicArray& operator=(const DynamicArray& other)
    {
        DynamicArray arr_copy(other); // may throw an exception
        impl_.swap(arr_copy.impl_); // cannot throw an exception
        return *this;
    }

    iterator begin() { return impl_.arr_; }
    iterator end() { return &impl_.arr_[content()]; }
    const_iterator begin() const 
        { return const_cast<DynamicArray&>(*this).begin(); }
    const_iterator end() const 
        { return const_cast<DynamicArray&>(*this).end(); }

    size_type size() const { return impl_.size_; }
    size_type content() const { return impl_.content_; }
    bool empty() const { return content() == 0; }

    // Unchecked references
    reference operator[] (const size_type n) 
    { 
        if (n == size()-1) // last element accessed - increase size
            resize(size()*2); // may throw an exception (see resize())

        if (n >= content())
            impl_.content_ = n+1;

        return impl_.arr_[n]; 
    }
    const_reference operator[] (const size_type n) const 
        { return const_cast<DynamicArray&>(*this)[n]; }

    // Checked references
    reference at(const size_type pos)
    {
        if (pos >= size())
            throw OutOfRange();

        return (*this)[pos];
    }
    const_reference at(const size_type pos) const 
        { return const_cast<DynamicArray&>(*this).at(pos); }

private:
    void resize(const size_type new_size)
    {
        DynamicArray resized_arr(new_size); // may throw an exception
        resized_arr.impl_.fill_from(impl_); // may throw an exception
        impl_.swap(resized_arr.impl_); // cannot throw an exception
    }

private:
    DynamicArrayImpl<T> impl_;
};

The interesting lines are marked in bold font-face. Let's review the function which contains these lines:

The constructor can throw an exception while allocating space for the elements in the array. That is ok because if it fails the object is deallocated from memory and is never created (no memory leaks and the program can continue).
The copy constructor can throw an exception in two places - the first time when allocating space for the elements of the array (new operator fails) and the second time when copying the elements from the other instance. Again, if the copy constructor throws, the new object is never created and the program stays in a valid state.
The assignment operator can throw an exception, but note the use of the copy constructor during the assignment. This is a bonus which is earned from the use of the "Impl" idiom. There is no need to test for self assignment, because self assignment will work just fine (the reason is left as an exercise for the reader). Now, if the assignment operator's first line throws, this instance has not changed yet and the object stays in the same state as it was before the assignment. If the first line is executed successfully, the other lines cannot throw an exception, and the assignment is successful. This is why it is so important the DynamicArrayImpl's swap() function will not throw.
Here we see the most important rule: Write all the code that can throw an exception first. Only then modify your object. Not only does the use of the "Impl" idiom helps us achieve just that, but also allows us to write elegant, simple code.
operator[] can throw an exception because resize() can throw an exception. Again, if it throws, the object's state has not changed and the program can go on.

Let's examine how the class template answers the requirements:

Requirements From The Stored Type, T

T is required to have:

A default constructor.
An assignment operator.
A destructor.

These are very similar to the requirements in the FixedArray class, only the copy constructor is not required here. This is good because a class template is better if it imposes fewer requirements on the contained type. This "bonus" is because we are using dynamic allocation for allocating T objects.

References And Notes

[1]
The "Impl" idiom is presented in the book Exceptional C++, and a great part of it can be found in Guru Of The Week column number 28.