Section 3 - Pushing and Popping to/from a vector

2A.3.1 Vector Vocabulary

A vector is a funny thing. On the one hand, it is advertized as the politically correct version of an array, while on the other hand it has additional methods that invoke images of a stack data structure, namely, push_back() and pop_back(). We need to acknowledge this odd behavior so we don't get confused.

If one thinks of vectors as super-arrays, then we should emphasize the brackets operator as being the primary goal of our implementation. Using brackets in concert with an occasional resize() for growth potential will accomplish our goal of super-sizing arrays.

On the other hand, there is a time-honored tradition of including push_back() and pop_back() as a simple means of increasing and decreasing the container size. They have the look and feel of a stack, which is not technically part of an array (or a vector for that matter) but it does help us when we ultimately do design a stack data structure based on vectors.

In addition, we will be nesting the iterator mechanism since this is part of all containers.

I think of a vector as a nicely protected and flexible bracketed array that contains some non-array bonus tools like push_back(), pop_back() and iterator-hopping. On this page, we will show the push_back(), pop_back() and the brackets operators, which make up the core of any vector, including STL vectors and our FHvector.

2A.3.2 Including Exceptions

Since we want to protect our container and report bounds violations, we will create an exception for that purpose, OutOfBoundsException. While we're at it, let's provide a VectorEmptyException in case a client wants to grab something from a vacuous FHvector object. Here are the one-line trivial definitions of these exceptions, shown in the context of the FHvector class prototype:

template <class Object>
class FHvector
{

   // all sorts of things we will skip  followed by...
   
public:
   // for exception throwing
   class OutOfBoundsException { };
   class VectorEmptyException { };
};

We can now throw these exceptions at will, providing our client with adequate error reporting. We'll do so in what follows.

2A.3.3 front() and back()

These two functions return, without modification of the container, the front and back of the FHvector. They are used when we want to retrieve something on either end of the array. We have another technique for running through the vector, and that will utilize iterators. However, we sometimes don't need an iterator, because we merely want one or the other end of the array. Here they are with the promised error reporting:

template <class Object>
const Object& FHvector<Object>::back() const
{
  if (mSize <= 0)
      throw VectorEmptyException();
  return mObjects[mSize - 1];
}

template <class Object>
const Object& FHvector<Object>::front() const
{
  if (mSize <= 0)
      throw VectorEmptyException();
  return mObjects[0];
}

back() helps us really understand the meaning of mSize, the size of the container. This is equally true for STL vector, so it's a very good time to absorb the code thoroughly. mSize is to be interpreted as the number of accessible items currently in the vector, meaning we can ask about data from the 0th to the (mSize-1)-th element. This range can be increased or decreased either directly, through resize(), or indirectly, through calls to push_back() which automatically increments the size each time it is called.

2A.3.4 push_back() and pop_back()

These are two, somewhat asymmetric, methods. We will mimic STL vector behavior which can be confusing. Since push_back() (correctly) adds a new object to the "tail" of the vector, we would expect pop_back() to remove and return this object. However, many computer scientists, the implementers of STL vector included, believe that pop_back() should only remove the item on the back of the array, not return it. If the client wants that object, it must first call back(), discussed above, then follow it by pop_back(). Reminding ourselves that this is, after all, just a vector, and not a stack data structure, we will not rant too harshly about this asymmetry, but simply make the observation.

With that editorial, let's see these two method implementations.

template <class Object>
void FHvector<Object>::push_back( const Object& x )
{
   if (mSize == mCapacity)
      reserve(2*mCapacity + 1);
   mObjects[mSize++] = x;
}

template <class Object>
void FHvector<Object>::pop_back()
{
   if (mSize > 0)
      mSize--;
}

2A.3.5 The Brackets Operator

Now comes the juicy part. The reason for this data structure is, after all, to give us a robust version of an array, so we want the brackets operator to behave as it would in an array, but provide protection through exception throwing and simultaneously allowing the container to grow We have done all the hard work ahead of time, and we now reap the rewards in a concise pair of operator functions. As discussed in a previous section, we will provide an accessor as well as a mutator version for [].

template <class Object>
Object& FHvector<Object>::operator[]( int index )
{
   if (index < 0 || index >= mSize)
      throw OutOfBoundsException();
   return mObjects[index];
}

template <class Object>
const Object& FHvector<Object>::operator[] (int index ) const
{
   if (index < 0 || index >= mSize)
      throw OutOfBoundsException();
   return mObjects[index];
}

2A.3.6 Iterators

We complete the design of our FHvector with the definition of the iterators. A vector iterator has to have the following properties to be usable by an applications programmer:

An iterator is a pointer to one Object (or null) in our container.
An iterator can be manufactured and returned by the begin(), end() method of the vector class.
An iterator has an increment (i.e., ++) and decrement (i.e., --) operation.
begin() (of the vector class) returns an iterator that points to the first item (the front) of the vector.
end() (of the vector class) returns an iterator that points one element past the last item (the back) of the vector.

This is easily done directly in the template prototype as follows:

   typedef Object *iterator;
   typedef const Object *const_iterator;
    
   iterator begin() { return &mObjects[0]; }
   const_iterator begin() const { return &mObjects[0]; }
   iterator end() { return &mObjects[ size() ]; }
   const_iterator end() const { return &mObjects[ size() ]; }

By defining an iterator to be nothing more than an Object *, we are taking the easy path to the list of requirements above. This will do the job, as you can verify by observation. And, because we sometimes want iterators that are used to mutate the Objects to which they point, and other times we want accessor-only behavior, we have provided two flavors of iterator, the normal version and the const version.

For a more robust, but trickier to code, implementation of iterator, please see how we implement FHlist iterators in the next week. Those iterators will protect the container by throwing exceptions that the client can catch if the iterator goes bezonkers. Because there are more ways for an iterator to get into trouble in a linked-list than there are in a vector, these extra safety measures are not quite as critical for us here. Therefore, this pointer-only implementation is quite adequate for the current task.

2A.3.7 Remaining Functions

There are a few more functions that parallel the STL vector class which I have implemented in FHvector. Most are simple, but they are not critical to our current purpose. If you are interested in gaining a mastery of memory management, I invite you to look at the header file and view the definitions of erase() and clear() which imply a sound understanding of C++ deep copies and pointers.