Example: doublevec

Introduction

vector is one of the most useful classes in C++

it is like an array, except it knows its size and can also expand to contain more data

lets implement our own version of it called doublevec that is similar to vector<double>

The Basic Idea

create a class called doublevec

it stores three things

• a double* pointer to an underlying array of doubles
• an int called cap (short for capacity) that stores the size of the underlying array
• an int called sz (short for size) that stores the size of the vector

the functions in doublevec will manage all the details of these variables

when necessary, doublevec will automatically re-size the underlying array

re-sizing is an expensive operation, and so we try to do it as infrequently as possible

also note how the constructor and destructor work together to manage the underlying array

the constructor calls new to make the array, and the destructor calls delete to delete the array (i.e. give the array back to the free store so that it can be used again)

the destructor is guaranteed to be called exactly once when the object goes out of scope (or is deleted), thus there is no memory leak

// doublevec.cpp

#include "error.h"
#include <iostream>
#include <algorithm>
#include <cassert>

using namespace std;


class doublevec {
private:
    int cap;  // capacity, i.e. size of the underlying array
    int sz;   // size of the vector; sz <= cap

    double* arr; // pointer to the first element of the
                 // underlying array

    // Re-sizes the array arr points to be size n.
    // If cap >= n, then nothing is done.
    void reallocate_arr(int n) {
        if (n < 0) cmpt::error("reallocate_arr n < 0");

        if (cap < n) {
            // copy arr into a new array of size n
            double* temp = new double[n];
            for(int i = 0; i < cap; ++i) {
                temp[i] = arr[i];
            }

            // delete the old array
            delete[] arr;  // note the use of delete[] with square brackets
                           // necessary because arr points to an array

            // make arr point to the new array
            arr = temp;

            // set the new capacity
            cap = n;
        }
    }

public:
    // default constructor
    doublevec()
    : cap(10), sz(0)  // note the initial capacity is 10
    {
        arr = new double[cap];
    }

    // The explicit keyword ensures this constructor is not silently called to
    // covnert an int to a doublevec: it can only be called explicitly by the
    // programmer (and not implicitly by the compiler).
    explicit doublevec(int n)
    : cap(n), sz(n)
    {
        if (n < 0) cmpt::error("negative size");
        arr = new double[cap];
        for(int i = 0; i < sz; ++i) {
            arr[i] = 0;
        }
    }

    // copy constructor
    doublevec(const doublevec& other)
    : cap(other.cap), sz(other.sz)
    {
        arr = new double[cap];
        for(int i = 0; i < sz; ++i) {
            arr[i] = other.arr[i];
        }
    }

    // assignment operator
    doublevec& operator=(const doublevec& other) {
        if (&other != this) {
            delete[] arr;
            arr = new double[other.cap];
            for(int i = 0; i < other.sz; ++i) {
                arr[i] = other.arr[i];
            }
            cap = other.cap;
            sz = other.sz;
        }
        return *this;
    }

    // destructor
    ~doublevec() {
        delete[] arr;
    }

    int size() const {
        return sz;
    }

    int capacity() const {
        return cap;
    }

    bool empty() const {
        return size() == 0;
    }

    void clear() {
        sz = 0;
    }

    // Both set and get check that the passed-in index variable i is
    // in range, i.e. 0 <= i < size(). If not, an error is thrown.
    double get(int i) const {
        if (i < 0 || i >= sz) cmpt::error("get index out of bounds");
        return arr[i];
    }

    void set(int i, double val) {
        if (i < 0 || i >= sz) cmpt::error("set index out of bounds");
        arr[i] = val;
    }

    // Returns a copy of the element at arr[i].
    double operator[](int i) const {
        if (i < 0 || i >= sz) cmpt::error("[] const index out of bounds");
        return arr[i];
    }

    // Returns a reference to the element at location arr[i], which allows the
    // actual array to be set.
    double& operator[](int i) {
        if (i < 0 || i >= sz) cmpt::error("[] index out of bounds");
        return arr[i];
    }

    void push_back(double val) {
        if (sz == cap) {
            reallocate_arr(2 * cap);  // double the capacity
        }                             // to avoid frequent
                                      // re-allocations
        arr[sz] = val;
        sz++;
    }

    double pop_back() {
        if (sz == 0) cmpt::error("popped empty vector");
        sz--;
        return arr[sz];
    }

    // Put val at the front (left side) of this vector. All the other elements
    // are moved one position towards the right, so it is often less efficient
    // than push_back.
    void push_front(double val) {
        if (sz >= cap) {
            reallocate_arr(2 * cap);  // double the capacity
        }                             // to avoid frequent
                                      // re-allocations
        // move each element up one index
        for(int i = sz; i > 0; --i) {
            arr[i] = arr[i - 1];
        }

        arr[0] = val;

        // increase the size
        sz++;
    }

    // Remove the first element of the vector. The elements from the second
    // onwards are all moved position towards the left, so it is often less
    // efficient than pop_back.
    double pop_front() {
        if (sz == 0) cmpt::error("popped empty vector");

        // save the popped element
        double result = arr[0];

        // move each element down on index
        for(int i = 1; i < sz; ++i) {
            arr[i - 1] = arr[i];
        }

        // decrease the size
        sz--;

        return result;
    }

}; // class doublevec


// Returns true iff a and b have the same elements in the same order. Not that
// this is a global function that is *not* inside the doublevec class.
bool operator==(const doublevec& a, const doublevec& b) {
    if (a.size() != b.size()) return false;
    for(int i = 0; i < a.size(); ++i) {
        if (a[i] != b[i]) {
            return false;
        }
    }
    return true;
}

// Returns true iff a and b *don't* have the same elements in the same order.
// Not that this is a global function that is *not* inside the doublevec
// class.
bool operator!=(const doublevec& a, const doublevec& b) {
    return !(a == b);
}

// Print a doublevec in a standard {}-style format.
ostream& operator<<(ostream& out, const doublevec& v) {
    int n = v.size();
    if (n == 0) {
        out << "{}";
    } else {
        out << '{' << v[0];
        for(int i = 1; i < n; ++i) {
            out << ", " << v[i];
        }
        out << '}';
    }
    return out;
}

int main() {
    // assert(bool_expr) does nothing if bool_expr evaluates to true, and
    // throws an exception if bool_expr is false. It's useful for debugging,
    // use assert to test that important facts are in fact true at points in
    // your program.

    doublevec v;
    for(int i = 0; i < 10; ++i) {
        v.push_back(i);
        assert(v[i] == i);
        assert(v.size() == i + 1);
    }
    cout << "v = " << v << "\n";

    doublevec w(v);
    assert(v == w);
    assert(w == v);
    assert(!(v != w));
    assert(v == v);

    // double all the elements
    for(int i = 0; i < v.size(); ++i) {
        v[i] = 2 * v[i];
    }
    cout << "v = " << v << "\n";

    // pop all the elements
    while (!v.empty()) {
        double x = v.pop_back();
        cout << x << " popped\n";
    }
    cout << "v = " << v << "\n";

    // create {1, 2, ..., 10} using push_front
    for(int i = 1; i <= 10; ++i) {
        v.push_front(i);
        assert(v[0] == i);
        assert(v.size() == i);
    }
    cout << "v = " << v << "\n";
} //main