CSCE 121 Chapter 19

« previous | Wednesday, November 10, 2010 | next »

Vectors, Templates, and Exceptions

Resizing Vectors

How do we address changes in size?

vector v;
v.resize(10)
v.push_back(i)

New data member: space = # elements + "free slots" for new elements

space now refers to size of allocated array

sz refers to how much data is in that allocated array; size of array from user's viewpoint

vector::reserve()

Make sure that vector has space for 'newalloc' elements

void vector::reserve(int newalloc) {
  if (newalloc <= space) return;     // never decrease allocation
  double* p = new double[newalloc];  // allocate new space
  for (int i=0; i<sz; ++i) p[i] = elem[i];
  delete[] elem;
  elem = p;
  space = newalloc;
}

vector::resize()

void vector::resize(int newsize) {
  reserve(newsize);
  for (int i=sz; i<newsize; ++i) elem[i] = 0;
  space = newsize;
}

vector::push_back()

void vector::push_back(double d) {
  if (sz==0) reserve(8);                // no space; grab some
  else if (sz==space) reserve(2*space)  // run out of space; double size of the allocated free-store array
  elem[sz] = d;
  ++sz;

vector

class vector {
  int sz;
  double* elem;
  int space;
  public:
    vector() : sz(0), elem(0), space(0) {}
    explicit vector(int s) : sz(s), elem(new double[s]), space(s) {}
    vector(const vector&);
    vector& operator=(const vector&);
    ~vector() { delete[] elem; }

    double& operator[](int n) { return elem[n]; }
    int size() const { return sz; }

    void resize(int newsize);
    void push_back(double d);

    void reserve(int newalloc);
    int capacity() const { return space; }
}

explicit

Use when constructor only contains one parameter

????

this

Pointer to self; return object from assignment operator so we can chain assignments together.

vector& vector::operator=(const vector& a) {
  if (this == &a) return *this;  // self-assignment
  if (a.sz<=space) {   // enough space, no allocation necessary
    for (int i=0; i<a.sz; ++i) elem[i] = a.elem[i];
    space += sz.a.sz;
    sz = a.sz;
    return *this;
  }
  double* p = new double[a.sz];
  for (int i=0; i<a.sz; ++i) p[i] = a.elem[i];
  delete[] elem;
  sz = a.sz;
  space = a.sz;
  elem = p;
  return *this
}

Templates

Basis for "generic programming": "parametric polymorphism" Parameterization of type (and functions) by types (and integers)

Unsurpassed flexibility and performance

Defining a template

// Declaration:
template<class T, int N> class Buffer { /* ... */ }
template<class T, int N> void fill(Buffer<T,N>& b) { /* ... */ }

// Instantiation:
Buffer<char,1024> buf;  // for buf, T is char and N is 1024

Use in Vector

Place in header files only!

template<class T> class vector {  // Read "for all types T" (like in math)
  // ... replace "double" with "T" ...
};

vector<double> vd;        // T is double
vector<int vi;            // T is int
vector<vector<int>> vvi;  // T is a vector of integers

Note: does not work at runtime; all templates have to be resolved at compilation. If there is an error, it will be nasty!

Range checking

struct out_of_range{ /* ... */ }

template<class T> T& vector<T>::operator[](int n) {
  if (n>space || n<0) throw out_of_range();
  // ...
}

RAII

Resource Acquisition is Initialization

Also called "scoped resource management"