Understanding Data Structures: A Practical Approach with Examples in C++
Before we talk about Dynamically Sized Arrays (Vectors as they are called in C++) We have to talk about Arrays, or Statically Sized Arrays. Arrays are a very simply data structure that stores information in a single contiguous block of memory. Arrays are very fast to access and change due to how it’s stored in memory. Arrays have a fixed size, and the Array in a dynamic Array also has a fixed size. Later we will see how we duplicate arrays in a dynamic array to make it function as if the array can be resized.
Every array is a pointer and they index via memory offsetting.
For example
int arr[5] = { 10, 20, 30, 40, 50 };
int numbie = arr[3];Would be accessing the memory address at arr[0] + 3 * sizeof(int)
So every time we index into an array it’s one addition operation that is being performed, so the size of the array won’t change the amount of time it takes to access the elements of that array.
You can define arrays both statically or dynamically
float numbies[10]; //Created at compile time on the stack
float* numbies = new float[10]; //created at runtime on the heap
int numbieOfValues = 10;
float numbies[numbieOfValues]; //compiler error
float* numbies = new float[numbieOfValues]; //functioning codeNow the hard part about using an array that is fixed size like this, is that we don’t always know how big our container needs to be. Sometimes the size is based on user or file input, and sometimes the size may need to change throughout the life of the application. For this case we use a dynamically sized array (vector)
A vector deep down at it’s guts is just an array that’s being recreated at different sizes with the new set of values, every time we add a value to it.
To better understand the std::vector class and when to use it, This guide will walk you through building a simplified version of this data type, at the end we will touch on the class itself and how to implement the existing data type.
We will call our data type the FlexArray since it’s a flexible array that can “change size.” This is going to be a templated class so we can use it with any data type we wish. First we’ll look at the data members of the class.
Type* mArray; //this is the inner array
unsigned int mSize; //the current size of the array
unsigned int mCap; //the current number of indices availableNow we’ll break down the functionality of this class. it should contain the following functions
- Default Constructor: Should define an empty FlexArray. Initializes the data members of the class, and if a value is passed in it should create an empty array of that size.
- Destructor: Deletes all dynamically allocated memory making use of the clear function. For Managing memory and obeying the rule of 3.
- Copy constructor: Perform Deep copies on dynamically allocated memory.
- Assignment operator: Perform Deep copies on dynamically allocated memory.
- operator[]: For accessing elements of the FlexArray.
- accessors for size and capacity: simple get functions to get the integers representing the current size and capacity of the FlexArray. These will simply return the appropriate data member
- Front: Access the front element of the FlexArray.
- Back: Access the back element of the FlexArray.
- Empty: Checks whether the container is empty.
- Clear: Helper function to empty the FlexArray and delete all dynamically allocated memory. Sets all data members back to their defaults
- Push: the equivalent of pushback in the vector. Adds an item to the end of the FlexArray.
- Pop: remove the last element of the FlexArray.
- Reserve: reserve more memory if needed, this Function will be used frequently when adding data to the FlexArray.
Now go ahead and try to build this class. If you struggle on any part for longer than 15–30 minutes, go ahead and come back and look at my examples included below
First I’ll include individual documentation for each function
- Default Constructor: Should define an empty FlexArray. Initializes the data members of the class, and if a value is passed in it should create an empty array of that size.
FlexArray(size_t startingCap = 0) {
if (startingCap == 0) {
mArray = nullptr;
mSize = 0; //Default
mCapacity = 0;
}
else {
mArray = new Type[startingCap]; //Capacity param passed in
mCapacity = startingCap;;
mSize = 0; //size is set to 0 because nothing is in the DynArray yet
}
}- Destructor: Deletes all dynamically allocated memory making use of the clear function. For Managing memory and obeying the rule of 3.
~FlexArray() {
Clear();
}- Copy constructor: Perform Deep copies on dynamically allocated memory. This CAN be performed using the assignment operator. For simplicity I have opted not to do that, but if you wish to try to make use of the assignment operator in this function that is perfectly acceptable method as well.
FlexArray(const FlexArray& copy) {
if (this == ©) { //self assignment check
return;
}
else {
mSize = copy.Size();
mCapacity = copy.Capacity();
Type* newArray = new Type[mCapacity];
if (mSize <= mCapacity) { //deep copy array
for (int i = 0; i < mSize; i++) {
newArray[i] = copy.mArray[i];
}
}
else {
for (int i = 0; i < mCapacity; i++) {
newArray[i] = copy.mArray[i];
}
}
mArray = newArray;
}
}- Assignment operator: Perform Deep copies on dynamically allocated memory.
FlexArray& operator=(const FlexArray& copy) {
if (this == ©) {
return *this;
}
else {
Clear();
mSize = copy.Size();
mCapacity = copy.Capacity();
Type* newArray = new Type[mCapacity]; //deep copy array
if (mSize <= mCapacity) {
for (int i = 0; i < mSize; i++) {
newArray[i] = copy.mArray[i];
}
}
else {
for (int i = 0; i < mCapacity; i++) {
newArray[i] = copy.mArray[i];
}
}
delete[] mArray;
mArray = newArray;
return *this;
}
}- operator[]: For accessing elements of the FlexArray.
Type& operator[](size_t index) {
return mArray[index];
}- Clear: Helper function to empty the FlexArray and delete all dynamically allocated memory. Sets all data members back to their defaults.
void Clear() {
delete[] mArray;
mArray = nullptr;
mSize = 0;
mCapacity = 0;
} - accessors for size and capacity: simple get functions to get the integers representing the current size and capacity of the FlexArray. These will simply return the appropriate data member
size_t Size() const {
return mSize;
}
size_t Capacity() const {
return mCapacity;
}- Front: Access the front element of the FlexArray.
Type Front() const {
try //Try catch statement to check if the array is empty
{
if (mSize <= 0) {
throw std::invalid_argument("ARRAY EMPTY");
}
else {
return mArray[0];
}
}
catch (std::invalid_argument& e)
{
std::cout << "The Array is empty cannot access front!";
}
}- Back: Access the back element of the FlexArray.
Type Rear() const {
try //Try catch statement to check if the array is empty
{
if (mSize <= 0) {
throw std::invalid_argument("ARRAY EMPTY");
}
else {
return mArray[(mSize - 1)];
}
}
catch (std::invalid_argument& e)
{
std::cout << "The Array is empty cannot access front!";
}
}- Empty: Checks whether the container is empty.
bool Empty() const {
if (mArray == nullptr || mSize == 0) {
return true;
}
else {
return false;
}
}- Push: the equivalent of pushback in the vector. Adds an item to the end of the FlexArray.
void Push(const Type& data) {
if (mSize >= mCapacity) { //if we don't have enough cap reserve more
Reserve();
}
mArray[mSize] = data; //since arr indexes start at 0 you can load data into arr[Size]
mSize++; //increment size
}- Pop: remove the last element of the FlexArray.
void Pop() {
if (!Empty()) {
Rear().~Type(); //destroy last element
--mSize; // decrement size
}
}- Reserve: reserve more memory if needed, this Function will be used frequently when adding data to the FlexArray.
void Reserve(size_t newCapacity = 0) {
if (newCapacity == 0) {
if (mCapacity <= 0) { //if mCap is empty set to 1
mCapacity = 1;
}
else {
mCapacity *= 2; //double by default
}
}
else {
if (newCapacity > mCapacity) { //user defined cap
mCapacity = newCapacity;
}
else {
}
}
Type* newArray = new Type[mCapacity]; //new arr
if (mSize <= newCapacity) {
for (int i = 0; i < mSize; i++) { //conditional checks to copy Arr properly
newArray[i] = mArray[i];
}
}
else {
for (int i = 0; i < mCapacity; i++) {
newArray[i] = mArray[i];
}
}
delete[] mArray; //delete old arr and assign it to point to new arr
mArray = newArray;
}Here is the full header file in case that is easier for you to go over.
#include <stdexcept>
#include <iostream>
#pragma once
// Our implementation of a vector (simplified)
template<typename Type>
class FlexArray
{
Type* mArray = reinterpret_cast<Type*>(-1);
size_t mSize = -1;
size_t mCapacity = -1;
public:
FlexArray(size_t startingCap = 0) {
if (startingCap == 0) {
mArray = nullptr;
mSize = 0; //Default
mCapacity = 0;
}
else {
mArray = new Type[startingCap]; //Capacity param passed in
mCapacity = startingCap;;
mSize = 0; //size is set to 0 because nothing is in the DynArray yet
}
}
~FlexArray() {
Clear();
}
FlexArray(const FlexArray& copy) {
if (this == ©) { //self assignment check
return;
}
else {
mSize = copy.Size();
mCapacity = copy.Capacity();
Type* newArray = new Type[mCapacity];
if (mSize <= mCapacity) { //deep copy array
for (int i = 0; i < mSize; i++) {
newArray[i] = copy.mArray[i];
}
}
else {
for (int i = 0; i < mCapacity; i++) {
newArray[i] = copy.mArray[i];
}
}
mArray = newArray;
}
}
FlexArray& operator=(const FlexArray& copy) {
if (this == ©) {
return *this;
}
else {
Clear();
mSize = copy.Size();
mCapacity = copy.Capacity();
Type* newArray = new Type[mCapacity]; //deep copy array
if (mSize <= mCapacity) {
for (int i = 0; i < mSize; i++) {
newArray[i] = copy.mArray[i];
}
}
else {
for (int i = 0; i < mCapacity; i++) {
newArray[i] = copy.mArray[i];
}
}
delete[] mArray;
mArray = newArray;
return *this;
}
}
void Clear() {
delete[] mArray;
mArray = nullptr;
mSize = 0;
mCapacity = 0;
}
Type& operator[](size_t index) {
return mArray[index];
}
size_t Size() const {
return mSize;
}
size_t Capacity() const {
return mCapacity;
}
Type Front() const {
try //Try catch statement to check if the array is empty
{
if (mSize <= 0) {
throw std::invalid_argument("ARRAY EMPTY");
}
else {
return mArray[0];
}
}
catch (std::invalid_argument& e)
{
std::cout << "The Array is empty cannot access front!";
}
}
Type Rear() const {
try //Try catch statement to check if the array is empty
{
if (mSize <= 0) {
throw std::invalid_argument("ARRAY EMPTY");
}
else {
return mArray[(mSize - 1)];
}
}
catch (std::invalid_argument& e)
{
std::cout << "The Array is empty cannot access front!";
}
}
void Push(const Type& data) {
if (mSize >= mCapacity) { //if we don't have enough cap reserve more
Reserve();
}
mArray[mSize] = data; //since arr indexes start at 0 you can load data into arr[Size]
mSize++; //increment size
}
bool Empty() const {
if (mArray == nullptr || mSize == 0) {
return true;
}
else {
return false;
}
}
void Pop() {
if (!Empty()) {
Rear().~Type(); //destroy last element
--mSize; // decrement size
}
}
void Reserve(size_t newCapacity = 0) {
if (newCapacity == 0) {
if (mCapacity <= 0) { //if mCap is empty set to 1
mCapacity = 1;
}
else {
mCapacity *= 2; //double by default
}
}
else {
if (newCapacity > mCapacity) { //user defined cap
mCapacity = newCapacity;
}
else {
}
}
Type* newArray = new Type[mCapacity]; //new arr
if (mSize <= newCapacity) {
for (int i = 0; i < mSize; i++) { //conditional checks to copy Arr properly
newArray[i] = mArray[i];
}
}
else {
for (int i = 0; i < mCapacity; i++) {
newArray[i] = mArray[i];
}
}
delete[] mArray; //delete old arr and assign it to point to new arr
mArray = newArray;
}
};Now I’m going to touch on some of the std::vector functionality, via some exercises to help us better understand how to use this data type. I want to talk a little bit first about WHEN to use this data structure however.
In my opinion the vector is a good structure to use when predictable growth is expected. Vectors and other forms of dynamic arrays excel in any scenario where the number of elements grow steadily and predictably. This is because of their ability to resize themselves when introducing new elements to the structure. For example in a video game a list of enemies, items, or players may be kept inside a vector since this could change in size during gameplay.
Vectors also have the advantage of efficient random access. You can access elements with great efficiency using a vector since it is stored in contiguous memory, and just uses the offset. (as was discussed earlier when talking about the inner array of the vector.) Lets say you have a large list of customer orders that needs to be processed and sorted by date. You could store the orders in their own order class and create a vector of orders to sort them by date.
Vectors are fantastic for manipulating data, and playing as a buffer in data processing. When processing data from a file, a vector can be used as a temporary buffer to store and manipulate the data easily. Such as filtering out unwanted lines, or possibly transforming the data. Now lets get into some exercises we can do to practice our vector magic.
Copy this into a file and get started. This is your To Do list.
#include <iostream>
#include <vector>
static void printVectorOfNumbies(std::vector<int> numbies) {
for (int i = 0; i < numbies.size(); i++) {
std::cout << numbies[i] << '\t';
}
std::cout << "\n\n";
}
int main(){
//TODO: Create vector of ints
//TODO: Add numbers to the vector of ints
//TODO: Pop numbers off the END of the vector
//TODO: access the front value of the vector and print it to the console.
//TODO: access the back value of the vector and print it to the console.
//TODO: check whether the vector is empty or not and print a message to the console to reflect that
}Answers are included below!
#include <iostream>
#include <vector>
static void printVectorOfNumbies(std::vector<int> numbies) {
for (int i = 0; i < numbies.size(); i++) {
std::cout << numbies[i] << '\t';
}
std::cout << "\n\n";
}
int main() {
//TODO: Create vector of ints
std::vector<int> numbies = {};
//TODO: Add numbers to the vector of ints
for (int i = 0; i < 10; i++) {
numbies.push_back((i + 1));
}
printVectorOfNumbies(numbies);
//TODO: Pop numbers off the END of the vector
numbies.pop_back();
printVectorOfNumbies(numbies);
//TODO: access the front value of the vector and print it to the console.
std::cout << "Front Value: " << numbies.front() << '\t';
//TODO: access the back value of the vector and print it to the console.
std::cout << "Back Value: " << numbies.back() << "\n\n";
//TODO: check whether the vector is empty or not and print a message to the console to reflect that
if (numbies.empty()) {
std::cout << "This vector is empty\n\n";
}
else {
std::cout << "This vector is not empty\n\n";
}
}Well that’s all for now folks. You now should have a fairly solid understanding of vectors and how and when to use them! Go forth and create something awesome with this knowledge you gained here today.