Basic Data Structures with C++

Table of Contents


1. Our first data structures: Smart Fixed-length Array

c4_u08_FixedLengthArray_arrays.png


In previous programming courses you've probably worked with arrays to store data. You've probably encountered out-of-bounds errors and had to deal with array indices, moving items around, and generally micro-managing your array's data as the program goes.

What we're going to do here is wrap our array - and everything we need to work with it - inside of a class, creating our first data structure: A slightly smarter fixed-length array.


1.0.1. Functionality for our data type

What kind of things do we want to do to a data structure? What is some functionality that others will need to store and retrieve data, without having to see inside the class? How do we keep the data stored?

Creating the array
For example, if we weren't storing our array inside a class, we might declare it in a program like this:
// Create an array + helper variables
const int ARR_SIZE = 100;
int totalItems = 0;
string data[ARR_SIZE];

With a fixed-length array, we have to keep track of the array size ARRAY_SIZE to ensure we don't go out-of-bounds in the array… valid indices will be 0 until ARRAY_SIZE - 1.

We are also keeping track of the totalItems in the array, because even though we have an array with some size, it could be useful to know that currently no data is stored in it. Then, when new data is added, we could increment totalItems by 1.

An empty array:

Value: "" "" "" "" ""
Index: 0 1 2 3 4

totalItems = 0

Adding onto the array
Adding on to the array would mean choosing an index to put new data. If we were wanting to fill the array from left-to-right, we would start at index 0, then 1, then 2, then 3, and so on. The totalItems variable begins at 0. Once the first item is added, it is then 1. Once a second item is added, it is then 2. Basically, the totalItems variable corresponds to the next index to store new data at
// Add new item
data[totalItems] = myNewData;
totalItems++;

One item added to the array:

Value: "Cats" "" "" "" ""
Index: 0 1 2 3 4

totalItems = 1

Removing items from the array
We may also want to remove an item at a specific index from the array. There's not really a way to "delete" an item from an array, but we can overwrite it, if we wanted to…
// Remove an item
int index;
cout << "Remove which index? ";
cin >> index;

data[index] = "";
totalItems--;

Array before removing item:

Value: "Cats" "Dogs" "Mice" "Birds" "Snakes" ""
Index: 0 1 2 3 4 5

Array after removing item:

Value: "Cats" "Dogs" "Mice" "" "Snakes" ""
Index: 0 1 2 3 4 5

We could design our array data structure this way, but to find a new place to add an item we'd have to use a for loop to look for an empty spot to use - this means every time we add a new item it would be less efficient.

Instead, we could design our arrays so that after a remove, we shift elements backwards to "overwrite" the empty spot. This also solves our issue with totalItems not aligning to the next-index-to-insert-at.

Filling in the empty gap:

Value: "Cats" "Dogs" "Mice" "Snakes" "" ""
Index: 0 1 2 3 4 5

totalItems = 4

Searching for an item

Another thing a user of this data structure might want to do is search for an item - is this thing stored in the array? If so, what is the index? If the array is unsorted (we're not going to do sorting yet), then really the only way to search for the item is to start at the beginning and keep searching until the end.

If we find a match, we return that index number.

If we get to the end of the loop and nothing has been returned, that means it isn't in the array so we would have to return something to symbolize "it's not in the array" – such as returning -1, or perhaps throwing an exception.

Populated array:

Value: "Cats" "Dogs" "Mice" "Birds" "Snakes" ""
Index: 0 1 2 3 4 5

totalItems = 5

Searching through the array would look like this:

// Search for an item
string findme;
cout << "Find what? ";
getline( cin, findme );

int foundIndex;

for ( int i = 0; i < totalItems; i++ )
{
    if ( data[i] == findme )
    {
        foundIndex = i;   // Found it
        break;
    }
}

// Did not find it
foundIndex = -1;

Once we implement this structure within a class, we will turn this into a function that returns data - this is just an example as if we were writing a program in main().

Retrieving an item at some index
Besides adding, removing, and searching for items, users will want to retrieve the data located at some index. This would be a simple return once we're writing our class, but generally accessing \textit{item at index} looks like:
// Display element at index
int index;
cout << "Which index? ";
cin >> index;
cout << data[index] << endl;
Visualizing the array
Another feature could be to display all elements of the array, which might look something like this:
// Display all items
for ( int i = 0; i < totalItems; i++ )
{
    cout << i << ". " << data[i] << endl;
 }

1.0.2. Predicting errors and exceptions

Invalid indices
When working with arrays one of the most common errors encountered are out-of-bounds errors: When we have an index that is less than 0, or equal to or greater than the size of the array…
// Out of bounds!
cout << data[-1]        << endl;    // error!
cout << data[ARR_SIZE]  << endl;    // error!

Additionally, if the user tries to access an index \(\geq\) totalItems then they would retrieve data that is invalid, though this wouldn't crash the program if it is still less than ARR_SIZE.

Array is full
With the fixed-length array, we could also run out of space, and we would have to design a way to deal with it. For example, if totalItems was equal to ARR_SIZE, then we are out of space and doing this would also cause an out-of-bounds error.
data[totalItems] = "Ferrets";       // error if full!
totalItems++;

As part of designing our data structure, we need to make sure we account for reasonable scenarios that would cause the program to crash and guard against logic errors. This would all be part of how we implement the functionality.


1.0.3. Creating a class to wrap the array

For our wrapper class we will need the array and array size / item count integers as part of the private member variables. The public functions would include the "interface" of what the user will want to do with the array, and we could also add private/protected helper functions.

Class declaration:

template <typename T>
class SmartFixedArray
{
public:
    SmartFixedArray();

    void PushBack( T newItem );
    void PushFront( T newItem );
    void PushAt( T newItem, size_t index );

    void PopBack();
    void PopFront();
    void PopAt( size_t index );

    T GetBack() const;
    T GetFront() const;
    T GetAt( size_t index ) const;

    size_t Search( T item ) const;
    void Display() const;
    size_t Size() const;
    bool IsEmpty() const;
    bool IsFull() const;

private:
    const size_t ARRAY_SIZE;
    T m_array[100];
    size_t m_itemCount;

    void ShiftLeft( size_t index );
    void ShiftRight( size_t index );
    bool IsValidIndex( size_t index );
  };

UML Diagram:

SmartFixedArray<TYPE>  
+ SmartFixedArray()  
   
+ PushFront( newData : TYPE ) : void
+ PushBack( newData : TYPE ) : void
+ PushAtIndex( index : size_t, newData : TYPE ) : void
   
+ PopFront() : void
+ PopBack() : void
+ PopAtIndex( index : size_t ) : void
   
+ GetFront() : TYPE&
+ GetBack() : TYPE&
+ GetAtIndex( index : size_t ) : TYPE&
   
+ Search( item : TYPE ) : size_t
+ Clear() : void
+ IsEmpty() : bool
+ IsFull() : bool
+ Size() : int
   
- ShiftLeft( index : size_t ) : void
- ShiftRight( index : size_t ) : void
- IsValidIndex( index : size_t ) : bool
- m_array : TYPE[100]
- m_itemCount : size_t
- ARRAY_SIZE : const size_t

The public-facing functions include the Push functions (add new items), Pop functions (remove items), Get functions, Search, and some helpers to give information about the structure such as whether it's empty or full or how many items the structure is currently storing.

The private-facing functions here are internal helpers: ShiftLeft and ShiftRight help with removal and inserting, and IsInvalidIndex can be used to implement the logic for how to detect an invalid index once, and then reused across any functions that take in an index as a parameter.

For this example data structure, we are hard-coding the array size to 100 elements. It is unlikely that anyone would use this data structure for anything, but I wanted to start off with a basic fixed-length array. Next, we will move to a dynamic array, which will be more useful.

With this class structure set up, lets look into how to actually implement the functionality.


1.0.4. Constructor - Preparing the array to be used

When the constructor is called, we need to set the value of ARRAY_SIZE as part of the initializer list since it is a const member and needs to be initialized right away. Otherwise, we can initialize m_itemCount to 0 as well, since are creating an empty array.

template <typename T>
SmartFixedArray<T>::SmartFixedArray()
    : ARRAY_SIZE( 100 )
{
    m_itemCount = 0;
}

1.0.5. Helper functions

The helper functions here are easier to implement, and we will be using them in the main interface functions.

size_t Size() const
  • This function returns the value from m_itemCount - the current amount of items in the array.

bool IsEmpty() const
  • Returns true if the array is empty and false if not. The array is empty if m_itemCount is 0.

bool IsFull() const
  • Returns true if the array is full and false if not. The array is full if m_itemCount is equal to ARRAY_SIZE.

bool IsValidIndex( size_t index )
  • Returns true if the index is valid and false otherwise.
  • Valid index: The index is valid if 0index and index < m_itemCount.
  • Invalid index: The index is invalid if index < 0 or indexm_itemCount.

void ShiftRight( size_t index )
  • Error checks:
    • If the array is full, then throw an exception.
    • If the index is invalid, then throw an exception.
  • Functionality:
    • Iterate over the array, starting at the index of the first empty space at the end (m_itemCount). Moving backwards, copy each item over from the previous index. Loop until hitting the index.

void ShiftLeft( size_t index )
  • Error checks:
    • If the index is invalid, then throw an exception.
  • Functionality:
    • Iterate over the array, starting at the index given and going until the last element. Copy each neighbor from the right to the current index until we get to the end.

void Display() const
  • Iterates over all the elements of the array displaying each item and its index.

size_t Search( T item ) const
  • Iterates over all the elements of the array searching for the item.
  • If a match is found, it returns the index of that element.
  • Otherwise, if it finishes looping over the array and has not yet returned, it means that nothing was found. Return -1 in this case, or throw an exception (this is a design decision).

1.0.6. Push - adding items to the array

We have three different Push functions in order to add an item to different parts of the array, which will each require slightly different logic:

void PushBack( T newItem )
  • Error checks:
    • If the array is full, then throw an exception.
  • Functionality: Add a new item to the end of the list of elements…

Array before PushBack( "Ferrets" ): (totalItems = 4)

Value: "Cats" "Dogs" "Mice" "Birds" "" ""
Index: 0 1 2 3 4 5

Array after PushBack( "Ferrets" ): (totalItems = 5) adds "Ferrets" to position 4

Value: "Cats" "Dogs" "Mice" "Birds" "Ferrets" ""
Index: 0 1 2 3 4 5

void PushFront( T newItem )
  • Error checks:
    • If the array is full, then throw an exception.
  • Functionality: Add a new item to the beginning of the list of elements. This requires shifting everything forward to make space for the new item…

Array before PushFront( "Ferrets" ): (totalItems = 4)

Value: "Cats" "Dogs" "Mice" "Birds" "" ""
Index: 0 1 2 3 4 5

Array after PushFront( "Ferrets" ): (totalItems = 5) adds "Ferrets" to position 0

Value: "Ferrets" "Cats" "Dogs" "Mice" "Birds" ""
Index: 0 1 2 3 4 5

void PushAt( size_t index, T newItem )
  • Error checks:
    • If the array is full, then throw an exception.
    • If the index is invalid, then throw an exception.
  • DRY (Don't Repeat Yourself) checks:
    • If the insert index is 0, then pass newItem to the PushFront function instead.
    • If the insert index is m_itemCount, then pass newItem to the PushBack function instead.
  • Functionality: Add a new item to the index given. This requires shifting everything forward to make space for the new item…

Array before PushAt( 2, "Ferrets" ): (totalItems = 4)

Value: "Cats" "Dogs" "Mice" "Birds" "" ""
Index: 0 1 2 3 4 5

Array after PushAt( 2, "Ferrets" ): (totalItems = 5) adds "Ferrets" to position 2

Value: "Cats" "Dogs" "Ferrets" "Mice" "Birds" ""
Index: 0 1 2 3 4 5

Additional design considerations

The PushFront and PushAt functions require shifting other elements over, so I've added a helper function called ShiftRight so that we don't write the same functionality in both of these functions.

Additionally, for each of these functions we will need to check to see if the array is full prior to adding any new items or shifting things. Implementing a IsFull function can help with this as well.


1.0.7. Pop - removing items from the array

void PopFront()
  • Error checks:
    • If array is empty, you could choose to ignore (return early) or throw an exception.
  • Functionality: Decrement m_itemCount.

Array before PopFront(): (totalItems = 5)

Value: "Cats" "Dogs" "Ferrets" "Mice" "Birds" ""
Index: 0 1 2 3 4 5

Array after PopFront(): (totalItems = 4) removes "Cats"

Value: "Dogs" "Ferrets" "Mice" "Birds" "" ""
Index: 0 1 2 3 4 5

void PopBack()
  • Error checks:
    • If array is empty, you could choose to ignore (return early) or throw an exception.
  • Functionality: Call ShiftLeft at position 0 then decrement the m_itemCount.

Array before PopBack(): (totalItems = 5)

Value: "Cats" "Dogs" "Ferrets" "Mice" "Birds" ""
Index: 0 1 2 3 4 5

Array after PopBack(): (totalItems = 4) removes "Birds"

Value: "Cats" "Dogs" "Ferrets" "Mice" "" ""
Index: 0 1 2 3 4 5

void PopAt( sizet index )
  • Error checks:
    • If array is empty, you could choose to ignore (return early) or throw an exception.
    • If the index is invalid, throw an exception.
  • DRY (Don't Repeat Yourself) checks:
    • If the index is 0, then call PopFront() instead.
    • If the index is m_itemCount-1, then call PopBack() instead.
  • Functionality: Call ShiftLeft at index, then decrement the m_itemCount.

Array before PopAt( 2 ): (totalItems = 5)

Value: "Cats" "Dogs" "Ferrets" "Mice" "Birds" ""
Index: 0 1 2 3 4 5

Array after PopAt( 2 ): (totalItems = 4) removes "Ferrets"

Value: "Cats" "Dogs" "Mice" "Birds" "" ""
Index: 0 1 2 3 4 5

1.0.8. Get - getting items in the array

T& GetFront()
  • Error checks:
    • If array is empty, throw exception (can't retrieve anything!)
  • Functionality: Return the item in the array at index 0.

GetFront(): (m_itemCount = 4) returns "Cats"

Value: "Cats" "Dogs" "Mice" "Birds" "" ""
Index: 0 1 2 3 4 5
T& GetBack()
  • Error checks:
    • If array is empty, throw exception (can't retrieve anything!)
  • Functionality: Return the item in the array at index m_itemCount-1.

GetBack(): (m_itemCount = 4) returns "Birds"

Value: "Cats" "Dogs" "Mice" "Birds" "" ""
Index: 0 1 2 3 4 5
T& GetAt( size_t index )
  • Error checks:
    • If array is empty, throw exception (can't retrieve anything!)
    • If index is invalid, throw an exception.
  • Functionality: Return the item in the array at the index given.

GetAt( 2 ): (m_itemCount = 4) returns "Mice"

Value: "Cats" "Dogs" "Mice" "Birds" "" ""
Index: 0 1 2 3 4 5

1.0.9. SmartDynamicArray starter code

Note: Since this is a templated class, the class declaration and the function definitions need to all be in the .h file!

SmartFixedArray.h:

#ifndef _SMART_FIXED_ARRAY_HPP
#define _SMART_FIXED_ARRAY_HPP

/* CLASS DECLARATION --- --------------------------------------------------------------------------- */
template <typename T>
//! A data structure that wraps a fixed array
class SmartFixedArray
{
public:
  //! Sets up the SmartFixedArray.
  SmartFixedArray();
  //! Cleans up the SmartFixedArray.
  ~SmartFixedArray();

  //! Insert an item to the END of the array.
  void PushBack( T newItem );
  //! Insert an item to the BEGINNING of the array.
  void PushFront( T newItem );
  //! Insert an item at some index in the array.
  void PushAt( size_t index, T newItem );

  //! Remove the LAST item in the array.
  void PopBack();
  //! Remove the FRONT item in the array. Shift everything to the left.
  void PopFront();
  //! Remove an item in the middle of the array. Close up the gap.
  void PopAt( size_t index );

  //! Get the LAST item in the array.
  T& GetBack();
  //! Get the FIRST item in the array.
  T& GetFront();
  //! Get an item in the array at some index.
  T& GetAt( int index );

  //! Search for an item by its value, return the index of its position.
  size_t Search( T item ) const;
  //! Returns the amount of items currently stored in the array.
  size_t Size() const;
  //! Check if the array is currently empty.
  bool IsEmpty() const;
  //! Check if the array is currently full.
  bool IsFull() const;
  //! Clear the data.
  void Clear();

private:
  //! The pointer used for the dynamic array
  T m_array[100];
  //! The current size of the array
  const size_t ARRAY_SIZE;
  //! The current amount of items inserted into the array
  size_t m_itemCount;

  //! Move all items past the given index to the left.
  void ShiftLeft( size_t index );
  //! Move all items past the given index to the right.
  void ShiftRight( size_t index );
};

/* FUNCTION DEFINITIONS  --------------------------------------------------------------------------- */

/** Clear out the array to get ready to use it. */
template <typename T>
SmartFixedArray<T>::SmartFixedArray()
  : ARRAY_SIZE( 100 )
{
  Clear();
}

/** Clean up the SmartFixedArray by calling the Clear function. */
template <typename T>
SmartFixedArray<T>::~SmartFixedArray()
{
  Clear();
}

/**
   This function will reset the m_itemCount to 0.
*/
template <typename T>
void SmartFixedArray<T>::Clear()
{
  // TODO: Implement me!
}

#endif
/**
   Return the value of m_itemCount;
*/
template <typename T>
int SmartFixedArray<T>::Size() const
{
  // TODO: Implement me!
}

/**
   The array is full if m_itemCount is the same value as ARRAY_SIZE.

   @return     true if the array is full, false otherwise.
*/
template <typename T>
bool SmartFixedArray<T>::IsFull() const
{
  // TODO: Implement me!
}

/**
   Check if the array is currently empty.
   The array is empty if the m_itemCount is set to 0.

   @return     true if empty, false otherwise.
*/
template <typename T>
bool SmartFixedArray<T>::IsEmpty() const
{
  // TODO: Implement me!
}

/**
   ERROR CHECK:
   - If the index is invalid, throw an exception.

   READY TO SHIFT:
   Use a for loop, use a counter variable (like i),
   - INITIALIZATION:   Starting at the index passed in
   - CONDITION:        Continue looping while i is less than the index of the last element of the array.
   - UPDATE:           Increment your i counter by 1 each time.

   Within the array, set the element at position i to the value of the element at position i-1.

   @param      index       The index where items will be shifted left from.
*/
template <typename T>
void SmartFixedArray<T>::ShiftLeft( size_t index )
{
  // TODO: Implement me!
}

/**
   ERROR CHECK:
   - If the index is invalid, throw an exception.

   PREP CHECK:
   1. If adding one item to the list (m_itemCount+1) is equal to the m_arraySize, then throw a StructureFullException.

   READY TO SHIFT:
   Use a for loop, use a counter variable (like i),
   - INITIALIZATION:   Starting at the first empty spot in the array.
   - CONDITION:        Continue looping while i is greater than the index passed in we will keep looping.
   - UPDATE:           Decrement i by 1 each time.

   Within the array, set the element at position i to the value of the element at position i+1.

   @param      index       The index where items will be shifted right from.
*/
template <typename T>
void SmartFixedArray<T>::ShiftRight( size_t index )
{
  // TODO: Implement me!
}

/**
   PREP CHECKS - do these before inserting the data to make sure the array is in a valid state:
   - Check if the array is full with the IsFull() function. If it is full, throw a StructureFullException.

   READY TO INSERT:
   1. Put the newItem into the array at the first empty position available.
   2. Increment the m_itemCount by 1.

   @param      newItem         The new item to store at the end of the array.
*/
template <typename T>
void SmartFixedArray<T>::PushBack( T newItem )
{
  // TODO: Implement me!
}

/**
   PREP CHECKS - do these before inserting the data to make sure the array is in a valid state:
   - Check if the array is full with the IsFull() function. If it is full, throw a StructureFullException.
   - Check if the array is not empty using the IsEmpty() function. If it is NOT empty, then call ShiftRight() with index 0 to make space for the new item.

   READY TO INSERT:
   1. Put the newItem into the array at the first index of the array.
   2. Increment the m_itemCount by 1.

   @param      newItem         The new item to store at the beginning of the array.
*/
template <typename T>
void SmartFixedArray<T>::PushFront( T newItem )
{
  // TODO: Implement me!
}

/**
   DRY CHECK - Don't Repeat Yourself:
   1. If index is 0, you can call PushFront() with the newItem instead.
   2. If index is m_itemCount, you can call PushBack() with the newItem istead.

   PREP CHECKS - do these before inserting the data to make sure the array is in a valid state:
   - Check if the array is full with the IsFull() function. If it is full, throw a StructureFullException.

   READY TO INSERT:
   1. Call ShiftRight() on the index to make space for this newItem.
   2. Put the newItem into the array at the first index of the array.
   3. Increment the m_itemCount by 1.

   @param      newItem         The new item to store at the beginning of the array.
   @param      index           Index location in the array - where to put the newItem.
*/
template <typename T>
void SmartFixedArray<T>::PushAt( size_t index, T newItem )
{
  // TODO: Implement me!
}

/**
   ERROR CHECK:
   1. If the array is currently empty, then throw a StructureEmptyException exception - we cannot remove an item from an empty array!

   READY TO REMOVE:
   When we're just removing the last item of the array, we only need to decrement m_itemCount by 1.
   This is known as a "Lazy Deletion"; we're not explicitly removing the item, but it will be replaced later on.
*/
template <typename T>
void SmartFixedArray<T>::PopBack()
{
  // TODO: Implement me!
}

/**
   ERROR CHECK:
   1. If the array is currently empty, then throw a StructureEmptyException exception - we cannot remove an item from an empty array!

   READY TO REMOVE:
   1. Call ShiftLeft() on index 0; this will replace the item at index 0 with its neighbor to the right (and everything else will be shifted, too.)
   2. Decrement the m_itemCount by 1.
*/
template <typename T>
void SmartFixedArray<T>::PopFront()
{
  // TODO: Implement me!
}

/**
   ERROR CHECK:
   1. If the array is currently empty, then throw a StructureEmptyException exception - we cannot remove an item from an empty array!
   2. If the index is invalid, throw a InvalidIndexException.

   READY TO REMOVE:
   1. Call ShiftLeft() with the index passed in; this will overwrite the item we're removing, and also shift everything after it to the left.
   2. Decrement the m_itemCount by 1.

   @param      index       The index of the element to remove.
*/
template <typename T>
void SmartFixedArray<T>::PopAt( size_t index )
{
  // TODO: Implement me!
}

/**
   ERROR CHECK:
   1. If the array is empty, then we can't return anything; throw a StructureEmptyException.

   READY TO GET:
   Return the last element stored in the array.
*/
template <typename T>
T& SmartFixedArray<T>::GetBack()
{
  // TODO: Implement me!
}

/**
   ERROR CHECK:
   1. If the array is empty, then we can't return anything; throw a StructureEmptyException.

   READY TO GET:
   Return the first element stored in the array.
*/
template <typename T>
T& SmartFixedArray<T>::GetFront()
{
  // TODO: Implement me!
}

/**
   ERROR CHECK:
   1. If the array is empty, then we can't return anything; throw a StructureEmptyException.
   2. If the index is out of range, throw a InvalidIndexException.

   READY TO GET:
   Return the element at this index.

   @param      index       The index of the element to return.
*/
template <typename T>
T& SmartFixedArray<T>::GetAt( size_t index )
{
  // TODO: Implement me!
}

/**
   Use a for loop to check each element of the array. Within the loop,
   if a match is found, return i. (Don't do an "else" case here.)

   Outside of the for loop, we have searched the entire array and the
   item hasn't been found. In this case, throw a ItemNotFoundException.
*/
template <typename T>
size_t SmartFixedArray<T>::Search( T item ) const
{
  // TODO: Implement me!
}


#endif

Author: Rachel Wil Sha Singh

Created: 2023-09-27 Wed 13:51

Validate