Home > Articles > Programming > C/C++

  • Print
  • + Share This
From the author of

Class Invariants

Consider a simple vector class:

class Vector {
        // v points to an array of sz ints
        int sz;
        int* v;
        explicit Vector(int n);           // create vector of n ints
        Vector(const Vector&);
        ~Vector();                        // destroy vector
        Vector& operator=(const Vector&); // assignment
        int size() const;
        void resize(int n);               // change the size to n
        int& operator[](int);             // subscripting
        const int& operator[](int) const; // subscripting

A class invariant is a simple rule, devised by the designer of the class, that must hold whenever a member function is called. This Vector class has the simple invariant v points to an array of sz ints. All functions are written with the assumption that this is true. That is, they can assume that this invariant holds when they're called. In return, they must make sure that the invariant holds when they return. For example:

int Vector::size() const { return sz; }

This implementation of size() looks clean enough, and it is. The invariant guarantees that sz really does hold the number of elements, and since size() doesn't change anything, the invariant is maintained.

The subscript operation is slightly more involved:

struct Bad_range { };

int& Vector::operator[](int i)
        if (0<=i && i<sz) return v[i];

        trow Bad_range();

That is, if the index is in range, return a reference to the right element; otherwise, throw an exception of type Bad_range.

These functions are simple because they rely on the invariant v points to an array of sz ints. Had they not been able to do that, the code could have become quite messy. But how can they rely on the invariant? Because constructors establish it. For example:

Vector::Vector(int i) :sz(i), v(new int[i]) { }

In particular, note that if new throws an exception, no object will be created. It's therefore impossible to create a Vector that doesn't hold the requested elements.

The key idea of the preceding section was that we should avoid resource leaks. So, clearly, Vector needs a destructor that frees the memory acquired by a Vector:

Vector::~Vector() { delete[] v; }

Again, the reason that this destructor can be so simple is that we can rely on v pointing to allocated memory.

Now consider a naive implementation of assignment:

Vector& Vector::operator=(const Vector& a)
        sz = a.sz;              // get new size
        delete[] v;             // free old memory
        v = new int[n];         // get new memory
        copy(a.v,a.v+a.sz,v);   // copy to new memory

People who have experience with exceptions will look at this assignment with suspicion. Can an exception be thrown? If so, is the invariant maintained?

Actually, this assignment is a disaster waiting to happen:

int main()
        Vector vec(10);
        cout << vec.size() << '\n';   // so far, so good
        Vector v2(40*1000000);         // ask for 160 megabytes
        vec = v2;                      // use another 160 megabytes
catch(Range_error) {
        cerr << "Oops: Range error!\n";
catch(bad_alloc) {
        cerr << "Oops: memory exhausted!\n";

If you hope for a nice error message Oops: memory exhausted! because you don't have 320MB to spare, you might be disappointed. If you don't have (about) 160MB free, the construction of v2 will fail in a controlled manner, producing that expected error message. However, if you have 160MB, but not 320MB (as I do on my laptop), that's not going to happen. When the assignment tries to allocate memory for the copy of the elements, a bad_alloc exception is thrown. The exception handling then tries to exit the block in which vec is defined. In doing so, the destructor is called for vec, and the destructor tries to deallocate vec.v. However, operator=() has already deallocated that array. Some memory managers take a dim view of such (illegal) attempts to deallocate the same memory twice. One system went into an infinite loop when someone deleted the same memory twice.

What really went wrong here? The implementation of operator=() failed to maintain the class invariant v points to an array of sz ints. That done, it was just a matter of time before some disaster happened. Once we phrase the problem that way, fixing it is easy: Make sure that the invariant holds before throwing an exception. Or, even simpler: Don't throw a good representation away before you have an alternative:

Vector& Vector::operator=(const Vector& a)
        int* p = new int[n];    // get new memory
        copy(a.v,a.v+a.sz,p);   // copy to new memory
        sz = a.sz;              // get new size
        delete[] v;             // free old memory
        v = p;

Now, if new fails to find memory and throws an exception, the vector being assigned will simply remain unchanged. In particular, our example above will exit with the correct error message: Oops: memory exhausted!.

Please note that Vector is an example of a resource handle; it manages its resource (the element array) simply and safely through the resource acquisition is initialization technique described earlier.

  • + Share This
  • 🔖 Save To Your Account