This shows how to implement a simple dynamic array using functions (i.e. a
non-object-oriented way). At the end a few examples of the standard C++
vector class are given to show that C++ provides a much nicer solution
using classes and objects.
A Dynamic Array Using FunctionsΒΆ
// dynamic_arr1.cpp
#include "cmpt_error.h"
#include <iostream>
#include <cassert>
#include <algorithm>
#include <vector>
using namespace std;
// The variables in int_vec are public, which means any code could modify them
// at any time.
struct int_vec {
int* arr; // pointer to the underlying array
int size; // # of elements in this int_vec from user's perspective
int capacity; // length of underlying array
}; // struct int_vec
// When an empty vector is created, its size is set to 0. But it is not
// obvious what its capacity should be. If the capacity is too big then it
// wastes space, but if it is too small then it will waste time re-sizing the
// underlying vector after only a few items are appended.
const int DEFAULT_CAPACITY = 10;
//
// Returns a new int_vec of size 0.
//
int_vec make_empty_vec(int cap = DEFAULT_CAPACITY) {
int_vec result = int_vec{new int[cap], 0, cap};
return result;
}
//
// Returns a new int_vec of size n, with every element set to fill_item.
//
int_vec make_filled_vec(int n, int fill_item) {
int cap = DEFAULT_CAPACITY;
// Set the capacity to be a little bit more than n so that appending a few
// extra elements is fast.
if (n > 0) {
cap += n;
}
int_vec result = int_vec{new int[cap], n, cap};
for(int i = 0; i < n; ++i) {
result.arr[i] = fill_item;
}
return result;
}
//
// Returns a new int_vec that is a copy of v. The returned int_vec does *not*
// share the same underlying array as v.
//
int_vec make_copy(const int_vec& v) {
int_vec result = int_vec{new int[v.capacity], v.size, v.capacity};
for(int i = 0; i < v.size; ++i) {
result.arr[i] = v.arr[i];
}
return result;
}
//
// Returns a copy of the int at index location i of v.
//
int get(const int_vec& v, int i) {
if (i < 0 || i >= v.size) {
cmpt::error("get: index out of range");
}
return v.arr[i];
}
//
// Sets index location i of v to be the value x.
//
void set(int_vec& v, int i, int x) {
if (i < 0 || i >= v.size) {
cmpt::error("get: index out of range");
}
v.arr[i] = x;
}
//
// Print v to the console in a nice format.
//
void print(const int_vec& v) {
if (v.size == 0) {
cout << "{}";
} else {
cout << "{";
cout << v.arr[0];
for (int i = 1; i < v.size; ++i) { // i starts at 1 (not 0)
cout << ", " << v.arr[i];
}
cout << "}";
}
}
//
// Print v to the console in a nice format, followed by a newline.
//
void println(const int_vec& v) {
print(v);
cout << '\n';
}
//
// Append adds x to the right end of v. If v doesn't have enough space to hold
// x, then the size of its underlying array is doubled.
//
void append(int_vec& v, int x) { // note that v is not const
if (v.size >= v.capacity) {
v.capacity = 2 * v.capacity; // double the capacity
int* new_arr = new int[v.capacity]; // make new underlying array
// twice size of old one
for(int i = 0; i < v.size; ++i) { // copy elements of v
new_arr[i] = v.arr[i]; // into new_arr
}
delete[] v.arr; // delete old arr
v.arr = new_arr; // assign new_arr
}
assert(v.size < v.capacity);
v.arr[v.size] = x;
v.size++;
}
//
// The programmer must remember to call deallocate exactly once on any int_vec
// they no longer want. Forgetting to call it results in a memory leak, and
// calling it more than once will most likely corrupt memory!
//
void deallocate(int_vec& v) {
delete[] v.arr; // delete with []-brackets is used because v.arr
} // points to an array
void test1() {
int_vec v = make_filled_vec(6, -1);
// int_vec v = make_empty_vec();
for(int i = 0; i < 15; ++i) {
append(v, i);
println(v);
}
int_vec w = make_copy(v);
for(int i = 0; i < w.size; ++i) {
set(w, i, i * i);
}
println(w);
deallocate(v);
deallocate(w);
// deallocate(v); // oops: uncommenting this will de-allocate v twice!
}
// To run this program at the command-line, you can do this:
//
// $ make dynamic_arr1.cpp
//
// $ ./dynamic_arr1 < numbers.txt
//
// numbers.txt is a text file containing numbers, e.g.:
//
// 3 1 2
// -5
// 1
//
// The output is:
//
// Sum = 2
// Average = 0.4
//
// The < is the BASH re-direction symbol, i.e. it makes the file numbers.txt
// be treated as cin from the program's point of view.
void test2() {
int_vec v = make_empty_vec();
// Keep reading ints from cin until end-of-file (ctrl-d) is encountered.
int x;
while (cin >> x) {
append(v, x);
}
// sum the elements of v
int sum = 0;
for(int i = 0; i < v.size; ++i) {
sum += get(v, i);
}
cout << "Sum = " << sum << "\n";
cout << "Average = " << sum / double(v.size)
<< "\n";
deallocate(v); // always remember to deallocate your intvecs
}
void sort(int_vec a) {
// sort is from the C++ Standard Teplate Library (the STL), which is a
// standard part of C++. The sort function that works on any type of of
// sequence, including arrays. It takes two pointers as input: a pointer
// to the first element, and a pointer one past the last element. In
// general, sort is an extremely efficient algorithm that you can use in
// most cases when you need to sort something in practice.
sort(a.arr, a.arr + a.size);
}
void test3() {
int_vec v = make_empty_vec();
// Keep reading ints from cin until end-of-file (ctrl-d) is encountered.
int x;
while (cin >> x) {
append(v, x);
}
println(v);
sort(v);
println(v);
deallocate(v); // always remember to deallocate your intvecs
}
// Here are some examples of things that can go wrong with an int_vec if
// you're not careful.
void test4() {
int_vec v; // oops: forgot to call a make function to initialize v;
println(v); // this compiles, runs, and prints a junk value.
v = make_filled_vec(5, 0); // okay, now v is initialized to be a
println(v); // an array of 5 0s
v = make_filled_vec(5, 6); // the order of the parameters to make_filled_vec
// can be confusing; this is a 5-element
// int_vec initialized to all 6s
println(v);
v = make_filled_vec(6, 5); // this is a 6-element int_vec initialized to all
// 5s
println(v);
deallocate(v); // Of course you should always deallocate int_vecs, but
// this one call to deallocate only deallocate the most
// recent int_vec. The arrays created by the previous calls
// to make are all still there, inaccessible! This is an
// a memory leak.
//
// Here are some examples of incorrectly accessing values of an int_vec.
//
int_vec w = make_filled_vec(10, 0);
w.arr = nullptr; // oops, memory leak: the underlying array is now
// inaccessible
println(w);
int_vec s = make_filled_vec(10, 0);
s.size = 100; // oops: now all functions that use size have the wrong
// value
println(s); // uh oh: this prints values past the end of the underlying
// array
int_vec t = make_filled_vec(10, 0);
t.capacity = 2 * t.capacity; // oops: now t has the wrong length for
// the underlying array
println(t); // interesting: should still work because println depends
// upon t.size, not t.capacity
}
//
// Now lets see some uses of the C++ standard vector class. The basic idea of
// a standard vector is essentially the same as our int_vec, but it is
// implemented using a class instead of a group of functions. This makes using
// a standard vector much easier and more pleasant than an int_vec.
//
void test5() {
vector<int> v; // creates an empty vector
v.push_back(5); // push_back does the same thing as the int_vec
v.push_back(2); // append function
v.push_back(4);
sort(v.begin(), v.end()); // The standard sort function sorts a vector
// using begin and end.
// v[i] is the element at index location i of v
for(int i = 0; i < v.size(); ++i) {
cout << "v[" << i << "]=" << v[i] << "\n";
}
// You can also use a for-each loop to get individual vector elements.
for(int n : v) {
cout << n << " ";
}
cout << "\n";
vector<int> w = {3, 5, 6, 1}; // very convenient initialization
v = w; // w is assigned to v: no memory leak!
// == (and !=) are pre-defined for standard vectors
if (v == w) {
cout << "v and w are the same!\n";
} else {
cout << "v and w are different!\n";
}
// You can put almost any type of value in a vector.
vector<string> names = {"Bob", "Neil", "Judy", "Ada"};
for(string s : names) {
cout << s << " ";
}
cout << "\n";
// We don't need to explicitly de-allocate vectors: they automatically
// delete their underlying array.
}
// The C++ standard vector is quite useful and efficient in practice: it is
// rarely ever necessary to use a basic array.
void test6() {
// Read an unknown number of strings from cin and add them to words. Then
// sort them in alphabetical order.
vector<string> words;
string s;
while (cin >> s) {
words.push_back(s);
}
sort(words.begin(), words.end());
for(string s : words) {
cout << s << "\n";
}
cout << "\n";
// No need to explicitly deallocate words: it automatically deletes its
// underlying array when words goes out of scope.
}
int main() {
// test1();
// test2();
// test3();
// test4();
// test5();
test6();
}