Table of Contents

array.png

1. Introduction

First we're going to start off by building a "Smart" fixed-length array, taking a traditional C-style array:

int myArray[100];

and wrapping it within a class, so that we can create functions and helper variables to provide a nice interface for a user, so they don't have to worry about the specifics of how the array is implemented, they just know that they can add, remove, and access their data. (In this context the "user" would be another programmer using your data structure.)

With the Smart Fixed-Length Array, we'll work through the steps together. Then, for a little more challenge, you'll work on a Smart Dynamic Array, which uses pointers to allow "resizing" of the array. There will be a lot of functionality in common between these two "Smart" Arrays, but also some differences.

2. Smart fixed array structure

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. With our traditional array wrapped inside of a class, we can look out for these error states and how to manage our array, and do it within the functions - the "programmer-user" doesn't have to think about how it's implemented.

So, what will our array actually do?

2.1. SmartFixedArray - Functionality

Pretend you're licensing out a special Data Structures library that other developers use. Our "programmer-user" is going to want to do some basic tasks:

  • Store data (PUSH)
  • Access data (GET)
  • Discard data (POP)

There could also be other features like Search. We'll be implementing these features and seeing how the implementations are different for each of our different types of data structures.

So how do we achieve this core functionality?

2.1.1. Creating the array:

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.

~

Our empty array (totalItems = 0):

index 0 1 2 3 4 5
value "" "" "" "" "" ""

2.1.2. 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 corresponds to the next index to store new data at…

// Add new item
data[totalItems] = myNewData;
totalItems++;

~

One item added (totalItems = 1):

index 0 1 2 3 4 5
value "Cats" "" "" "" "" ""

2.1.3. 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--;

But if we did it this way we would create an array with gaps in it. Additionally now totalItems doesn't align to the next index to insert at. While we could design our SmartArray this way (I have this type of array as the base for our eventual HashTable data structure), but the design we're going for here, we don't want gaps in the array and we're filling it up from left-to-right.

Before removing an item (totalItems = 6):

index 0 1 2 3 4 5
value "Cats" "Dogs" "Mice" "Birds" "Snakes" ""

After removing an item (totalItems = 5):

index 0 1 2 3 4 5
value "Cats" "Dogs" "Mice" "" "Snakes" ""

If we designed our array to allow gaps, we would then have to add code to find a new available 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 because of the "search" operation.

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.

After removing an item with a "Shift Left" (totalItems = 5):

index 0 1 2 3 4 5
value "Cats" "Dogs" "Mice" "Snakes" "" ""

Here, we've shifted everything after index 3 (where we removed "Birds" from) and shifted everything backwards by 1, so now "Snakes" is at position 3 instead of 4.

2.1.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 to let the user know where in the array that data was found.

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 as the index (negative numbers are invalid indices), or perhaps throwing an exception.

Populated array (totalItems = 5):

index 0 1 2 3 4 5
value "Cats" "Dogs" "Mice" "Birds" "Snakes ""

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().

2.1.5. 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 item at index looks like:

// Display element at index
int index;
cout << "Which index? ";
cin >> index;
cout << data[index] << endl;

2.1.6. 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;
}

2.2. SmartFixedArray - Predicting errors/exceptions

2.2.1. 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.

2.2.2. 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.

2.3. SmartFixedArray - 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.

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

The class declaration could look like this:

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

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

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

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

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

private:
  const int m_arraySize;
  T m_array[100];
  int m_itemCount;

  void ShiftLeft( int index );
  void ShiftRight( int index );
};

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.

2.3.1. Constructor - Preparing the array to be used

array_constructor.png

When the constructor is called, we need to set the value of m_arraySize 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()
    : m_arraySize( 100 )
{
  m_itemCount = 0;
}

2.3.2. int Size() const

array_size.png

This function returns the value from m_itemCount - the current amount of items in the array.

2.3.3. bool IsEmpty() const

array_empty.png

Returns true if the array is empty and false if not. The array is empty if m_itemCount is 0.

2.3.4. bool IsFull() const

array_full.png

Returns true if the array is full and false if not. The array is full if m_itemCount is equal to m_arraySize.

2.3.5. void Display() const

array_display.png

Iterates over all the elements of the array displaying each item.

void SmartFixedArray<T>::Display() const
{
  for ( int i = 0; i < m_itemCount; i++ )
  {
    cout << i << ". " << m_array[i] << endl;
  }
}

2.3.6. int Search( T item ) const

array_search.png

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).

int SmartFixedArray<T>::Search( T item ) const {
  for ( int i = 0; i < m_itemCount; i++ ) {
    if ( m_array[i] == item ) {
      return i;
    }
  }
  throw runtime_error( "Could not find item!" );
}

2.3.7. void ShiftRight( int index )

array_shiftright.png

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. Moving backwards, copy each item over from the previous index. Loop until hitting the index.
void SmartFixedArray<T>::ShiftRight(int index) {
    if ( index < 0 || index >= m_itemCount ) {
        throw out_of_range( "Index is out of bounds!" );
    }
    else if ( IsFull() ) {
        throw length_error( "Array is full!" );
    }

    for ( int i = m_itemCount; i > index; i-- ) {
        m_array[i] = m_array[i-1];
    }
}

2.3.8. void ShiftLeft( int index )

array_shiftleft.png

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 SmartFixedArray<T>::ShiftLeft(int index) {
{
  if ( index < 0 || index >= m_itemCount ) {
    throw out_of_range( "Index is out of bounds!" );
  }

  for ( int i = index; i < m_itemCount-1; i++ ) {
    m_array[i] = m_array[i+1];
  }
}

(Continued…)

2.3.9. void PushBack( T newItem )

array_pushback.png

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. PushBack adds a new item to the end of the list of elements.

Functionality:

  1. ERROR CHECK:
    1. Use the IsFull() function to check if the array is full… if it is, then throw an exception, because we can't resize this type of array!
  2. All good to go:
    1. The m_itemCount is also the index of the next available space in the array… Add the newItem to the m_array at the index m_itemCount.
    2. Increment m_itemCount by 1.

BEFORE:

index 0 1 2 3 4 5
value "Cats" "Dogs" "Mice" "Birds" "" ""

m_itemCount is 4.

AFTER:

index 0 1 2 3 4 5
value "Cats" "Dogs" "Mice" "Birds" "Ferrets" ""

m_itemCount is now 5.

2.3.10. void PushFront( T newItem )

array_pushback.png

PushFront adds a new item to the beginning of the list of elements. This requires shifting everything forward to make space for the new item…

Functionality:

  1. ERROR CHECK:
    1. Use the IsFull() function to check if the array is full… if it is, then throw an exception, because we can't resize this type of array!
  2. All good to go:
    1. The front of the array is always index 0. To make space for our new item, we need to call ShiftRight( 0 ) to scoot everything over by 1 space.
    2. Add the newItem to the m_array at the index 0.
    3. Increment m_itemCount by 1.

BEFORE:

index 0 1 2 3 4 5
value "Cats" "Dogs" "Mice" "Birds" "" ""

m_itemCount is 4.

MAKE ROOM by calling ShiftRight(0)

index 0 1 2 3 4 5
value "" "Cats" "Dogs" "Mice" "Birds" ""

m_itemCount is now 5.

AFTER:

index 0 1 2 3 4 5
value "Ferrets" "Cats" "Dogs" "Mice" "Birds" ""

2.3.11. void PushAt( T newItem, int index )

array_pushat.png

PushAt adds a new item to the index given. This requires shifting everything forward to make space for the new item…

Functionality:

  1. ERROR CHECKS:
    1. Use the IsFull() function to check if the array is full… if it is, then throw an exception, because we can't resize this type of array!
    2. If index is out of bounds (less than 0 or greater than m_itemCount!) then throw an exception - can't add at an invalid index!
  2. DRY (Don't Repeat Yourself) checks:
    1. If the index is 0, call PushFront(newItem) instead.
    2. If the index is m_itemCount, call PushBack(newItem) instead.
  3. ELSE:
    1. The index for our new item has been passed in. To make space for our new item, we need to call ShiftRight(index) to scoot everything over by 1 space.
    2. Add the newItem to the m_array at the index index.
    3. Increment m_itemCount by 1.

BEFORE:

index 0 1 2 3 4 5
value "Cats" "Dogs" "Mice" "Birds" "" ""

m_itemCount is 4.

MAKE ROOM by calling ShiftRight( 2 )

index 0 1 2 3 4 5
value "Cats" "Dogs" "" "Mice" "Birds" ""

AFTER PushAt("Ferrets", 2)

index 0 1 2 3 4 5
value "Cats" "Dogs" "Ferrets" "Mice" "Birds" ""

m_itemCount is now 5.

2.3.12. T GetBack() const

array_getback.png

The Get functions just return data from the array. The "Back" of the array will be at m_itemCount-1 (the last valid index), the "Front" of the array is at 0. Note that with the Get functions, we need to check IsEmpty() first - if the array is empty, we can't retrieve any data!

Functionality:

  1. ERROR CHECK:
    1. Use the IsEmpty() function to check if the array is empty… if it is, then throw an exception, because we can't retrieve from an empty array!
  2. All good to go:
    1. Return the item from m_array at the index m_itemCount-1.

2.3.13. T GetFront() const

array_getfront.png

Functionality:

  1. ERROR CHECK:
    1. Use the IsEmpty() function to check if the array is empty… if it is, then throw an exception, because we can't retrieve from an empty array!
  2. All good to go:
    1. Return the item from m_array at the index 0.

2.3.14. T GetAt( int index ) const

array_getat.png

Functionality:

  1. ERROR CHECK:
    1. Use the IsEmpty() function to check if the array is empty… if it is, then throw an exception, because we can't retrieve from an empty array!
    2. If index is out of bounds (less than 0 or greater than or equal to m_itemCount!) then throw an exception - can't retrieve from an invalid index!
  2. All good to go:
    1. Return the item from m_array at the index index.

2.3.15. void PopBack()

array_popback.png

Functionality:

  1. ERROR CHECK:
    1. Use the IsEmpty() function to check if the array is empty… if it is, then throw an exception, because we can't remove data from an empty array!
  2. All good to go:
    1. Just decrement m_itemCount by 1. (Next time something is added, it will overwrite this location!)

BEFORE:

index 0 1 2 3 4 5
value "Cats" "Dogs" "Ferrets" "Mice" "Birds" ""

m_itemCount is 5.

AFTER PopBack()

index 0 1 2 3 4 5
value "Cats" "Dogs" "Ferrets" "Mice" "" ""

m_itemCount is now 4.

2.3.16. void PopFront()

array_popfront.png

Functionality:

  1. ERROR CHECK:
    1. Use the IsEmpty() function to check if the array is empty… if it is, then throw an exception, because we can't remove data from an empty array!
  2. All good to go:
    1. Call ShiftLeft(0), which will essentially "erase" the item by overwriting it.
    2. Decrement m_itemCount by 1.

BEFORE:

index 0 1 2 3 4 5
value "Cats" "Dogs" "Ferrets" "Mice" "Birds" ""

m_itemCount is 5.

AFTER PopFront()

index 0 1 2 3 4 5
value "Dogs" "Ferrets" "Mice" "Birds" "" ""

m_itemCount is now 4.

(Continued…)

2.3.17. void PopAt( int index )

array_popat.png

Functionality:

  1. ERROR CHECK:
    1. Use the IsEmpty() function to check if the array is empty… if it is, then throw an exception, because we can't remove data from an empty array!
    2. If index is out of bounds (less than 0 or greater than or equal to m_itemCount!) then throw an exception - can't remove data from an invalid index!
  2. All good to go:
    1. Call ShiftLeft(index), which will essentially "erase" the item by overwriting it.
    2. Decrement m_itemCount by 1.

BEFORE:

index 0 1 2 3 4 5
value "Cats" "Dogs" "Ferrets" "Mice" "Birds" ""

m_itemCount is 5.

AFTER PopAt(2) and ShiftLeft(2)

index 0 1 2 3 4 5
value "Cats" "Dogs" "Mice" "Birds" "" ""

m_itemCount is now 4.

Author: RachelWil

Created: 2026-10-14 Wed 11:13

Validate