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 ofdouble
s - an
int
calledcap
(short for capacity) that stores the size of the underlying array - an
int
calledsz
(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