Home > Articles > Programming > C/C++

  • Print
  • + Share This

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.

  • + Share This
  • 🔖 Save To Your Account

Related Resources

There are currently no related titles. Please check back later.