An array is a group of variables. You reference the individual variables in the array using an index position. Arrays are extremely useful, and you will use arrays frequently as you design software solutions in your career position. The only problem with an array is that you cannot resize the array. Once you create the array, the size cannot change. For example:

string names[10];

The names array will have 10 positions (0 to 9). What happens if you add an 11th position? The application crashes with an "array out of bounds" error.

What if you need an array that can be resized? Better yet, wouldn't it be great if you could create a resizable array that automatically resized when it was full? The STL (Standard Template Library) has a resizable array that automatically resizes for you! The data structure is called a vector in C++ and Java. This data structure is called an ArrayList in other languages, including C# and Visual Basic.

The ArrayList (or vector) can use any type of data. Interesting! How is it possible to make a class that can use int data (whole numbers) and still be able to use string data (text)? If you template your class, your class will be able to use any data type.

Let's create a templated ArrayList class. This way, you will see how the classes in the STL are created. In addition, you will be able to understand the ArrayList structure better once you understand how the ArrayList structure is built. The ArrayList actually uses an array to store the data. Then, when you give it too much data, the ArrayList automatically creates a larger array and moves the data to the larger array. Arrays cannot be resized. As a result, the ArrayList must create a second array and move the data to the second array. This step takes a lot of processing power, but it also makes the ArrayList very flexible.

Create a C++ project, and call it Week 7Templated ArrayList.

Templated classes cannot cross files. Therefore, we have to create the templated ArrayList as a single header file.

Right-click on the Header Files folder in your Solution Explorer, and choose Add -> New Item.

Select "Header File (.h)", and then change name at the bottom of the dialog to ArrayList.h.

Add "#pragma once" at the top so that the ArrayList is only created one time in memory.

Put the tag "template " to tell C++ that we are creating a templated class.

Create the ArrayList class. Remember to put the semicolon at the end! When you finish, the class should look like this:

#pragma once template  class ArrayList { };

Step 2

Let's add our attributes to the ArrayList class. Remember, the attributes need to go in a private section so that we can protect the data. Data hiding is a very important concept in object-oriented programming.

Create a constant called DEFAULT_SIZE, and set it to 5. You can change the default size later to any value that you want.

Add a pointer so that we can put a dynamic array in the class. The data type for the pointer should be Tyes, just a capital letter T. The reason for this is that we put a template tag at the top of our code and stated that the data type will be class T. As a result, everywhere in the class when we need to state the data type, we simply put a T to tell C++ to use the data type that is given by the userthe templated data type.

Now, add two int variables so that we can keep track of the number of data items and the actual internal array size. The two variables can be called count and capacity.

When you finish, your attributes section should look like this.

private: // attributes const static int DEFAULT_SIZE = 5; // constant for the initial size T* list; // pointer to the array int count; // number of items in the list int capacity; // current size in memory

Step 3

Let's create the constructors and destructor. The first constructor should create a dynamic array that is set to the default size. Then, the capacity should be set to the default size because that is the current size of the internal array. The second constructor should create a dynamic array that is set to the given initial capacity. The second constructor should set the capacity to the given size because that is the current size of the internal array. In both cases, the count should be set to zero because the ArrayList does not have any data in it at this point.

Because we created a dynamic array using the new keyword, the array was created on the memory heap. If we do not destroy the array, the array will remain on the heap, and we will have a memory leak. In your destructor, check to see if the array is set to nullptr. If it is not, then you need to destroy the array and set the array pointer to nullptr. When you finish, your code should look like this.

public: // constructors ArrayList(void) { this->list = new T[DEFAULT_SIZE]; this->capacity = DEFAULT_SIZE; this->count = 0; } ArrayList( int initialCapacity ) { this->list = new T[initialCapacity]; this->capacity = initialCapacity; this->count = 0; } // destructor ~ArrayList(void) { // delete the array pointer if( this->list != nullptr ) { delete[] this->list; this->list = nullptr; } }

Step 4

There are some functions that are generally considered a required part of an ArrayList data structure. First, we need to have a method called isEmpty() that returns a boolean to tell us if the ArrayList is empty or not empty. You can determine if the ArrayList is empty by simply looking at the count variable. If the count is zero, then the ArrayList is empty.

Next, we need to get the data at the requested position. Remember, the data type in a templated class is T.

When you finish these two methods, your code should look like this.

/// Determine if the ArrayList is empty bool isEmpty(void) { return count == 0; // array is empty if it has zero items } /// Get the item at the given position T get( int position ) { if( position < count ) return list[position]; else return NULL; }

Step 5

This section is the most important section of the ArrayList class. We need to create an add() method that allows a user to add data to the ArrayList. However, what happens if the user adds a data item when the count is equal to the capacity? In other words, what happens when the user adds too many data items? We need to create a bigger array. Then, we need to copy all of the current data items to the bigger array. Finally, we need to delete the small (original) array off the heap.

Create an add() method that accepts data of type T as a parameter.

In the method, check to see if the count is equal to the capacity.

If the count equals the capacity, that means that you do not have any extra slots to put the new data. So, create an array that is twice as big as the current array and call it temp.

Copy all the items from the current array to the new temp array.

Delete the current array (list).

Copy the temp pointer to our current array pointer (list).

In all cases, copy the data to the count position of our array.

Increment count so that we know how many items we currently have in our array.

When you finish the code, it should look something like this.

 /// Add an item to the ArrayList void add( T data ) { // if the array is full, double the size if( count == capacity ) { // create bigger array capacity = 2 * capacity; T* temp = new T[capacity]; // copy items from current array to bigger array for (int i = 0; i < count; i++) { temp[i] = list[i]; } // delete the current array delete[] list; // rename the bigger array to the current array name list = temp; } // add the data item to the array list[count] = data; // increment the count count++; }

Step 6

We need to add a removeAt() method. In this method, we need to copy all of the data down one slot to overwrite the position that the user wants deleted. As an example, if you have five items in your array, and you want to delete the second item, you copy the third item into the second item slot. Then, you copy the fourth item into the third item slot. Finally, you copy the fifth item into the fourth slot. Then, you decrement your count because you have one item less.

We also need to add a getCount() method and a getCapacity() method because the user will want to know this information. When you finish, your code should look something like this.

 /// Remove item at the given position void removeAt( int position ) { // replace every item from that position on with the next item for (int i = position; i < count - 1; i++) // notice "count - 1" to copy last item to next to last position { list[i] = list[i + 1]; } // decrease the item count count--; } /// Get the count of items in the ArrayList int getCount(void) { return count; } /// Get the ArrayList current capacity int getCapacity() { return capacity; }

Step 7

Let's test our ArrayList class! Add a Source.cpp to your project.

Create a main method for your application.

In the main method, check for memory leaks.

Create an ArrayList that uses int data items like this: ArrayList intList;

Notice that you put the data type in arrow brackets:

Add six numbers. Remember, our default size is five. Using a for loop, show the data items. Then, show the count and the capacity.

Does the ArrayList work with other data types as well? Let's find out! Create an ArrayList that holds string data items like this: ArrayList strList;

Add four names. Then, using a for loop, show the data items. Then, show the count and capacity.

How do you check your application to see if you have a memory leak?

Run your program. Then, open the Output window (View -> Output).

Now, put two slashes in the destructor for the ArrayList for this line: // delete[] this->list;

Run your program again, and look at the Output window after your run it. Look at the memory leaks! You can see a line that states "Detected memory leaks!" Then, you will see "Dumping objects ->", and a lot of objects are then dumped off the memory heap. What a mess!

Uncomment the line (remove the slashes) in the ArrayList class so that the array is properly deleted again.

When you finish everything, the code in your Source.cpp should look something like this.

#include  #include  #include  #include "ArrayList.h" using namespace std; /// Entry point to the application int main(void) { // check for memory leaks #if defined(DEBUG) | defined(_DEBUG) _CrtSetDbgFlag( _CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF ); #endif // create an int ArrayList ArrayList intList; intList.add(27); intList.add(13); intList.add(42); intList.add(31); intList.add(22); intList.add(19); for (int i = 0; i < intList.getCount(); i++) { cout << intList.get(i) << ", "; } cout << " " << endl; cout << "Count: " << intList.getCount() << endl; cout << "Capacity: " << intList.getCapacity() << endl; cout << " " << endl; // create a string ArrayList ArrayList strList; strList.add("Brendan"); strList.add("Maria"); strList.add("Ivan"); strList.add("Nathan"); // display list data for (int i = 0; i < strList.getCount(); i++) { cout << strList.get(i) << ", "; } cout << " " << endl; cout << "Count: " << strList.getCount() << endl; cout << "Capacity: " << strList.getCapacity() << endl; // pause cout << " Press any key to continue..."; cin.sync(); _getch(); return 0; }