Strong Vectors
The standard library's support for resource management begins and ends with the auto_ptr. Not even the simplest containers support ownership semantics. You might think that combining auto_ptr with any of the standard containers would do the trick, but it doesn't. For instance, you might try this, only to find out that you can't index it in a standard way:
vector< auto_ptr<Item> > autoVector;
This construct won't compile:
Item * item = autoVector [0];
On the other hand, this construct will result in the ownership transfer from autoVector to auto_ptr:
auto_ptr<Item> item = autoVector [0];
We have no choice but to build our own strong vector. The minimum interface should look something like this:
template <class T>
class auto_vector
{
public:
explicit auto_vector (size_t capacity = 0);
T const * operator [] (size_t i) const;
T * operator [] (size_t i);
void assign (size_t i, auto_ptr<T> & p);
void assign_direct (size_t i, T * p);
void push_back (auto_ptr<T> & p);
auto_ptr<T> pop_back ();
};
You might notice a very defensive attitude in this design. I decided against providing an lvalue-indexed access to the vector. Instead, if you want to set a value, you have to use one of the assign or assign_direct methods. My philosophy is that resource transfer shouldn't be taken lightly; besides, it isn't needed all that often. In my experience, a strong vector is usually filled using the push_back method.
A strong vector is best implemented as a dynamic array of strong pointers:
template <class T>
class auto_vector
{
private
void grow (size_t reqCapacity);
auto_ptr<T> *_arr;
size_t _capacity;
size_t _end;
};
The grow method allocates a larger array of auto_ptr<T>, transfers all the items from the old array, swaps it in, and deletes the old array.
The rest of the implementation of auto_vector is pretty straightforward, since all the complexity of resource management is built into auto_ptr. For instance, the assign method simply utilizes the overloaded assignment operator to both deallocate the old object and transfer the new object in one simple statement:
void assign (size_t i, auto_ptr<T> & p)
{
_arr [i] = p;
}
I already discussed the likes of push_back and pop_back methods. The pop_back method returns auto_ptr by value, because it transfers the ownership away from auto_vector.
Indexed access to auto_vector is implemented in terms of the get method of auto_ptr, which simply returns the internal pointer.
T * operator [] (size_t i)
{
return _arr [i].get ();
}
No container can live without iterators. We need an iterator that would make an auto_vector look like a regular vector of pointers. In particular, when we de-reference such an iterator, we want to get a pointer, not an auto_ptr. We don't want an auto_vector iterator to be used for inadvertent resource transfer.
template<class T>
class auto_iterator: public
iterator<random_access_iterator_tag, T *>
{
public:
auto_iterator () : _pp (0) {}
auto_iterator (auto_ptr<T> * pp) : _pp (pp) {}
bool operator != (auto_iterator<T> const & it) const
{ return it._pp != _pp; }
auto_iterator const & operator++ (int) { return _pp++; }
auto_iterator operator++ () { return ++_pp; }
T * operator * () { return _pp->get (); }
private
auto_ptr<T> * _pp;
};
We provide the auto_vector with standard begin and end methods to retrieve these iterators:
class auto_vector
{
public:
typedef auto_iterator<T> iterator;
iterator begin () { return _arr; }
iterator end () { return _arr + _end; }
};
You might be asking whether we have to reimplement every single container from the standard library to make it resource-management aware? Fortunately, no; it turns out that a strong vector fulfills most of the ownership needs. Once you have all your objects safely tucked into a strong vector, you can use all the rest of the standard containers for rearranging (weak) pointers.
Suppose, for instance, that you want to sort a set of dynamically allocated items. You store pointers to these items in a strong vector. Then you create a standard vector and fill it with (weak) pointers obtained from the strong vector (use the above iterator). You can then use a standard library algorithm to sort this vector any way you want. This intermediate vector is often called a permutation vector. Similarly, you can use standard maps, priority queues, heaps, hash tables, etc.