Safe C++

Chapter 4. Index Out of Bounds

There are several ways in C++ to create an array of objects of some type T. Three common methods are:

#define N 10  // array size N is known at compile time
  T static_array[N];

  int n = 20; // array size n is calculated at runtime
  T* dynamic_array = new T[n];

  std::vector<T> vector_array; // array size can be changed at runtime

Of course, you can still use the calloc() and malloc() functions and your program will compile and run, but it’s not a good idea to mix C and C++ unless you have to because you’re relying on legacy C libraries. However you allocate the array, you can access an element in it using an unsigned integer index:

const T& element_of_static_array  = static_array[index];
const T& element_of_dynamic_array = dynamic_array[index];
const T& element_of_vector_array  = vector_array[index];

Let’s deal with dynamic arrays and vectors first, and return to the static array later in this chapter.

Dynamic Arrays

What would happen if we provide an index value that is larger than or equal to the array size? In all three of the preceding examples, the code will silently return garbage. (The exception to this rule for Microsoft Visual Studio 2010 is discussed later.) The situation is even worse if you decide to use the operator [] in the left-hand side of an assignment:

some_array[index] = x;

Depending on your luck (or lack of thereof) you might overwrite some other unrelated variable, an element of another array, or even a program instruction, and in the latter case your program will most likely crash. Each of these errors also provides opportunities for malicious intruders to take over your program and turn it to bad ends. However, the std::vector provides an at(index) function, which does bounds checking by throwing an out_of_range exception. The problem with this is that if you want to do this sanity check, you have to rigorously use the at() function everywhere for accessing an array element. And naturally, this slows your code down, so once you are done testing, you’ll want to replace it everywhere with the [] operator, which is faster. But doing that replacement requires massive editing of your code, which is a lot of work, followed by a need to retest it, because during that tedious process you could accidentally mistype something.

So instead of the at() function, I suggest the following. Although a dynamic array leaves the [] operator totally out of your control, the STL vector implements it as a C++ function that we can rewrite according to our bug-hunting goals. And that’s what we’ll do here. In the file scpp_vector.hpp we redefine the [] operators as follows:

T& operator [] (size_type index) {
  SCPP_TEST_ASSERT(index < std::vector<T>::size(),
    "Index " << index << " must be less than "
             << std::vector<T>::size());
  return std::vector<T>:: operator[](index);
}

const T& operator [] (size_type index) const {
  SCPP_TEST_ASSERT(index < std::vector<T>::size(),
    "Index " << index << " must be less than "
             << std::vector<T>::size());
  return std::vector<T>::operator[](index);
}

Let’s see how this works. Here is an example of how to use it (including—intentionally—how not to use it):

#include <iostream>
#include "scpp_vector.hpp"

using namespace std;

int main() {
  scpp::vector<int> vect;
  for(int i=0; i<3; ++i)
    vect.push_back(i);

  cout << "My vector = " << vect << endl;

  for(int i=0; i<=vect.size(); ++i)
    cout << "Value of vector at " << i << " is " << vect[i] << endl;

  return 0;
}

First, note that instead of writing std::vector<int> or just vector<int> we wrote scpp::vector<int>. This is to distinguish our vector from the STL’s vector. By using our scpp::vector we replace the standard implementation—in this case, the implementation of operator []—by our own safe implementation, and you will see the same approach to preventing other bugs later in this book. scpp::vector also gives you a << operator for free, so you can print your vector as long as it is not too big, and as long as the type T defines the << operator.

The next thing to notice is that in the second loop, instead of writing i<vect.size() we wrote i<=vect.size(). This is a very common programming error, and we did it just to see what happens when the index is out of bounds. Indeed, the program produces the following output:

My vector = 0 1 2
  
  Value of vector at 0 is 0
  
  Value of vector at 1 is 1 Value of vector at 2 is 2
           
  Index 3 must be less than 3 in file scpp_vector.hpp
        #17

This sanity check works as long as the symbol SCPP_TEST_ASSERT_ON is defined, and is easy to switch on and off at compile time when necessary. The problem with this approach is that the vector’s [] operator is very often used inside loops, so this sanity check is used a lot and therefore slows the program down significantly just as using at() would. If you feel that this is becoming a problem in your program, feel free to define a new macro, such as SCPP_TEST_ASSERT_INDEX_OUT_OF_BOUNDS, which would work exactly the same way as SCPP_TEST_ASSERT but would be used only inside scpp::vector::operator[]. SCPP_TEST_ASSERT_INDEX_OUT_OF_BOUNDS should differ from SCPP_TEST_ASSERT only by the fact that it can be switched on and off independently of the SCPP_TEST_ASSERT macro, so you can deactivate it after you are sure that your code does not have this bug while keeping the rest of your sanity checks active.

In addition to allowing you to catch this index-out-of-bounds error, the template vector has one advantage over statically and dynamically allocated arrays: its size grows as needed (as long as you don’t run out of memory). However, this advantage comes at a cost. The vector, if not told in advance how much memory will be needed, allocates some default amount (called its “capacity”). When the actual size reaches this capacity, the vector will allocate a bigger chunk of memory, copy old data into the new memory area, and release the old chunk of memory. So from time to time, adding a new element to a template vector could suddenly become slow. Therefore, if you know in advance what number of elements you will need, as with both static and dynamically allocated arrays, tell the vector up front, for instance, in the constructor:

scpp::vector<int> vect(n);

This creates a vector with a specified number of elements in it. You could also write:

scpp::vector<int> vect(n, 0);

which would also initialize all elements to a specified value (in this case zero, but any other value will work too).

An alternative is to create a vector with zero elements in it but to specify the desired capacity:

scpp::vector<int> vect;
vect.reserve(n);

The difference between this example and the previous one is that in this case the vector is empty (i.e., vect.size() returns 0), but when you start adding elements to it, you will not run into the incrementing capacity procedure with the corresponding slowdown until you reach the size of n.

Can We Derive from std::vector?

At this point you may have looked at the definition of the scpp::vector in the scpp_vector.hpp file:

namespace scpp {
template <typename T>
class vector : public std::vector<T> {

You may have asked yourself whether it is a good idea to derive a class from a base class that does not have a virtual destructor. Indeed, if we have the following situation:

class Base {
  // not virtual !!!
  ~Base();
};

class Derived : public Base {
  // also not virtual !!!
  ~Derived() {
    // some non-trivial code releasing resources
  }
}

and we use these classes like this:

Base* p = new Derived;
// some code using p
delete p;

the delete statement will actually call the destructor of the base class ~Base() and none of the code of the ~Derived() destructor will be executed, thus leading to unreleased resources such as memory leaks, etc. The same situation will occur even if we did not write any non-trivial code in the ~Derived() destructor, but added to the derived class some new data members that do have non-trivial destructors, such as containers or smart pointers. Even though we do not write the ~Derived() code ourselves, the compiler will do it for us, calling all the destructors of the added data members. In the example just shown, this ~Derived() destructor will not be called, which represents a problem. However, in our concrete example of scpp::vector, the situation is different:

• We do not expect these two classes to be used in the manner of std::vector* p_vect = new scpp::vector. scpp::vector must be used as a plain vector, as if it was never derived from anything.

• We did not add any data members to scpp::vector, and its destructor does not do any work except to call the destructor of the base class. Even if we did something like what is described in the previous example with Base and Derived, in this particular case nothing bad will happened.

• If this violation of C++ purity still bothers you, you could use composition instead of derivation, e.g., write a scpp::vector that contains std::vector as a private data member, and wrap each of its methods in the corresponding method of the derived class, which is a lot of coding but would produce the same results as my implementation.

There is one more consequence of this derivation: if you have any function that expects std::vector, you can still pass to it scpp::vector, which is being publicly derived from the former, and therefore is a std::vector. Here is an example:

void FunctionTakingRefToSTLVector(const std::vector<int>& v) {
  cout << "ATTENTION, we are about to test index-out-of-bounds "
       << "for STL vector reference to scpp::vector" << endl << flush;

  for(int i=0; i<=v.size(); ++i)
    cout << "Value of vector at " << i << " is " << v[i] << endl;
}

int main() {
  scpp::vector<int> v;
  for(int i=0; i<3; ++i)
    v.push_back(i);
  cout << "Initial vector: " << v << endl;

  FunctionTakingRefToSTLVector(v);
}

The vector created here has three elements, and the FunctionTakingRefToSTLVector() function tries to access an element with index 3, which is out of bounds. This code produces the following output:

ATTENTION, we are about to test index-out-of-bounds for
        STL vector reference to scpp::vector
        
        Value of vector at 0 is 0
        
        Value of vector at 1 is 1
        
        Value of vector at 2 is 2
        
        Value of vector at 3 is 1

Note that the code happily prints the value at the index 3, even though the maximum valid index is 2, which means that our sanity check did not work inside FunctionTakingRefToSTLVector(). The reason is that the function uses the original [] operator of std::vector because the version used is determined by the type of the reference to the vector, which in this case comes from the declaration in the function’s argument list, const std::vector<int>&. The [] operator was never declared as virtual, and we couldn’t do so if we wanted to because the declaration is in the code of the STL vector. Declaring it virtual would not be a good idea anyway because it would slow it down. So this is a risk of our approach. To make it work, you must be careful to use scpp::vector everywhere you want the sanity check to be active.

On the other hand, if you have a function taking std::vector <T>& and you trust that this function has already been tested, you can keep the original signature taking std::vector <T>& and it will run faster. At the same time, outside of this function you will be taking full advantage of checking for index-out-of bounds errors in the rest of the code.

Static Arrays

Now, as promised, let’s deal with the static array:

#define N 10  // array size N is known at compile time
  T static_array[N];

Here, the size is known at compile time and will not change. Of course, to use the safe array with its boundary check, you can use a template vector with the size specified in a constructor:

scpp::vector vect(N);

This will work exactly the same as the static array, but the problem here is efficiency. While the static array allocates its memory on stack, the template vector allocates memory inside the constructor using the new operator, and this is a relatively slow operation. If runtime efficiency is important in your case, it’s better to use a template array, defined as follows in the scpp_array.hpp file:

namespace scpp {

// Fixed-size array
template <typename T, unsigned N>
class array {
 public:
  typedef unsigned size_type;

  // Most commonly used constructors:
  array() {}

  explicit array(const T& initial_value) {
    for(size_type i=0; i<size(); ++i)
      data_[i] = initial_value;
  }

  size_type size() const { return N; }

  // Note: we do not provide a copy constructor and assignment operator.
  // We rely on the default versions of these methods generated by the compiler.

  T& operator[] (size_type index) {
    SCPP_TEST_ASSERT(index < N,
      "Index " << index << " must be less than " << N);
    return data_[index];
  }

  const T& operator [] (size_type index) const {
    SCPP_TEST_ASSERT(index < N,
      "Index " << index << " must be less than " << N);
    return data_[index];
  }

  // Accessors emulating iterators:
  T* begin() { return &data_[0]; }
  const T* begin()const { return &data_[0]; }

  // Returns an iterator PAST the end of the array.
  T* end() { return &data_[N]; }
  const T* end()const { return &data_[N]; }

 private:
  T data_[N];
};
} // namespace scpp

This array behaves exactly like a static C array. However, when compiled with the sanity check macro SCPP_TEST_ASSERT active, it provides an index-out-of-bounds check. The begin() and end() methods are provided to simulate iterators, so that you can use this array in some of the situations where you would have used the template vectors—for example, to sort numbers. The following code demonstrates how to sort this array using STL’s sort algorithm:

#include <algorithm>

  scpp::array<int, 5> a(0);
  a[0] = 7;
  a[1] = 2;
  a[2] = 3;
  a[3] = 9;
  a[4] = 0;

  cout << "Array before sort: " << a << endl;
  sort(a.begin(), a.end());
  cout << "Array after sort: " << a <<
  endl;

This produces the following output:

Array before sort: 7 2 3 9 0
      
Array after sort: 0 2 3 7 9

As a side benefit, you also get a << operator, which allows you to stream an array as shown in the previous example, assuming it is not too large and the template type T has a << operator. Of course, the use of this fixed-sized array must be limited to cases where the array size N is not too large. Otherwise, you’ll be spending your stack memory, a limited resource, on this array.

So the advice in this section is not to use static or dynamically allocated arrays, but a template vector or array instead. This solves another problem described in Chapter 1: when you use the new operator with brackets, you need to use the delete operator with brackets as well. If you cross-use these operators (new with brackets and delete without or vice versa) you will corrupt the memory heap, which generally leads to bad consequences. Once we decide not to use dynamically allocated arrays, which are created through the new operator with brackets, we’ve killed two birds with one stone: the problem of an index out of bounds, and the problem of mixing operators with and without brackets. In short, do not use the new operator (and the corresponding delete operator) with brackets. Your life will be easier.

Note

At the time of this writing, the newest version of Microsoft Visual Studio 2010 Ultimate diagnoses the index-out-of-bounds error in std::vector when compiled in a Debug mode, and pops up a dialog box (Figure 4-1).

This dialog offers you the choice to Ignore, Abort, or Retry (in which case you can debug the application). While “Ignore” seems appropriate only if you are extremely adventurous, one can hope that the rest of the compilers working under Unix, Linux, and Mac OS will catch up to the trend.

Figure 4-1. Microsoft Visual Studio “Index out of bounds” dialog box

Multidimensional Arrays

Now that we’ve settled on the use of a template vector or array as an implementation of a linear array, let’s consider what to do if you need a two-dimensional matrix, a three-dimensional array, or generally speaking, an n-dimensional array. Because all the issues in the general case of n-dimensional arrays can be illustrated using a two-dimensional matrix, we will limit our discussion to this case and call it simply a matrix, with the understanding that the same principles apply to three or more dimensions.

If the size of the matrix is known at compile time, you can easily implement it as an array of arrays, and be done with it. Therefore, we’ll concentrate on the more complex case of a matrix whose size is calculated at run time. Such a matrix can easily be created as a vector of vectors, and in fact this approach is the only one possible if different rows must be of different lengths. However, most of the time all rows should be of the same length (e.g., the matrix is rectangular or even quadratic), and in this case the approach of using a vector of vectors is inefficient: it requires multiple memory allocations, which is a relatively slow operation (and the same can be said about deallocation). Because our goal in using C++ is efficiency, we’ll try a different approach and create a rectangular matrix using only one memory allocation, as shown in the class matrix in the scpp_matrix.hpp file:

// Two-dimensional rectangular matrix.
template <typename T>
class matrix {
 public:
  typedef unsigned size_type;

  matrix(size_type num_rows, size_type num_cols)
    : rows_(num_rows), cols_(num_cols), data_(num_rows * num_cols)
  {
    SCPP_TEST_ASSERT(num_rows > 0,
      "Number of rows in a matrix must be positive");
    SCPP_TEST_ASSERT(num_cols > 0,
      "Number of columns in a matrix must be positive");
  }

  matrix(size_type num_rows, size_type num_cols, const T& init_value)
    : rows_(num_rows), cols_(num_cols), data_(num_rows * num_cols, init_value)
  {
    SCPP_TEST_ASSERT(num_rows > 0,
      "Number of rows in a matrix must be positive");
    SCPP_TEST_ASSERT(num_cols > 0,
      "Number of columns in a matrix must be positive");
  }

  size_type num_rows() const { return rows_; }
  size_type num_cols() const { return cols_; }

  // Accessors: return element by row and column.
  T& operator() (size_type row, size_type col) {
    return data_[ index(row, col) ];
  }

  const T& operator() (size_type row, size_type col) const {
    return data_[ index(row, col) ];
  }

 private:
  size_type rows_, cols_;
  std::vector<T> data_;

  size_type index(size_type row, size_type col) const {
    SCPP_TEST_ASSERT(row < rows_, "Row " << row
      << " must be less than " << rows_);
    SCPP_TEST_ASSERT(col < cols_, "Column " << col
      << " must be less than " << cols_);
    return cols_ * row + col;
  }
};

First of all, there are two constructors. The first allows you to create a matrix with a specified number of rows and columns. The second, with the additional init_value argument, allows you also to initialize each element to a specified value (e.g., to set each element of a matrix<double> to 0.0). Note that access to elements is provided via the () operator, not []. This is because the [] operator in C++ takes only one argument, never two or more. So to access a multidimensional array, we either need to use multiple [] operators, such as my_matrix[i][j], or a single () operator, such as my_matrix(i,j).

The first approach could be achieved if we had the [] operator return a T* pointer to the zeroth element of the i-th row. However, this denies us the diagnosis of a column index out of bounds, which defeats the purpose of catching bugs at runtime. We could, of course, create some template class that would include a smart reference to a row, return an instance of it using the first operator ([i]), and then use the bounds check in the second operator ([j]). To some degree, it is a matter of taste. I did not see the value of resorting to this complex design just to preserve the my_matrix[i][j] syntax, and the () operator with multiple arguments seems just fine.

The checks for an index out of bounds are performed inside the index(row, col) function, separately for row and column numbers, and in the case of a runtime error lead to calls to an error handler that are familiar by now. Finally, at the end of the same file, you will discover a << operator for a template matrix<T>. They are provided so you can output your matrix like this:

cout << "my matrix =\n" << my_matrix << endl;

as long as the matrix is not too large and the type T defines the << operator.

Rules for this chapter to avoid “index out of bounds” errors:

• Do not use static or dynamically allocated arrays; use a template array or vector instead.

• Do not use new and delete operators with brackets—leave it up to the template vector to allocate multiple elements.

• Use scpp:vector instead of std::vector and scpp::array consistently instead of a static array, and switch the sanity checks on.

• For a multidimensional array, use scpp::matrix and access elements through the () operator to provide index-out-of-bounds checks.