CS 235/250 Unit 07 Exercise: The Standard Template Library

For this exercise we are going to be introduced to some of the common STL data structures we have available to us. While these structures are already implemented for us here, in a data structures class you will learn to make your own, so it is good to see how these structures work ahead of time.

Goals

• Work with traditional arrays
• Work with the STL array structure
• Work with the STL vector structure
• Work with the STL list structure
• Work with the STL map structure
• Work with the STL stack structure
• Work wiht the STL queue structure

Setup

Make sure to download the starter code here: https://gitlab.com/moosadee/courses/-/tree/main/wip_exercises/starter_code/c3_u07_StandardTemplateLibrary?ref_type=heads Files included are:

• array.cpp
• list.cpp
• main.cpp
• map.cpp
• queue.cpp
• stack.cpp
• vector.cpp

About traditional arrays:

Traditional arrays come in this form:

DATATYPE NAME[SIZE];

A downside of this array type is that you usually have to have two helper variables: A const to store the size of the array, and an item count to keep track of how many spaces have been used in the array.

const int ARR_SIZE = 5;
int itemCount = 0;
string wordArray[ARR_SIZE];

When working with arrays we also have to be careful to not allow access to invalid indices – such as negative numbers or an index >= the size of the array. These could cause the program to crash.

void TraditionalArrayProgram()

****************************************
CURRENT ARRAY:
wordArray[0] = Cat
wordArray[1] = Dog
wordArray[2] = Mouse
wordArray[3] = Rat
wordArray[4] = Pidgeon

Total items in array: 5/5
Enter a WORD to add to array or STOP to stop: Cheese

!!!!!!!!!!!!!!!!!!!!!!!!!!
!! ERROR! Array is full !!
!!!!!!!!!!!!!!!!!!!!!!!!!!

1. VARIABLES: Start off by declaring the following items:

• ARR_SIZE, a const int with a value of 5.
• item_count, an integer with a value of 0.
• word_array, an array of strings, of size ARR_SIZE.

2. PROGRAM LOOP: Then we will create a basic program loop:

bool done = false;
while ( !done )
{
  // add code
}

3. ARRAY CONTENTS: Within the program loop, display the index and value of each element of the array so far. Use a basic for loop to iterate from [0, ARR_SIZE).

4. ADD TO ARRAY: After the for loop to display the array’s contents, ask the user to enter a WORD to add to the array, or type “STOP” to stop. Get the user’s input and store it in a string variable.

If input is “STOP” then you can use done = true; to end the loop.

5. CHECK IF ARRAY IS FULL: If the itemCount is less than the ARR_SIZE, then the array is NOT FULL and you can add the next item into the array.

Otherwise, display an error message that the array is full.

Enter a WORD to add to array or STOP to stop: g

!!!!!!!!!!!!!!!!!!!!!!!!!!
!! ERROR! Array is full !!
!!!!!!!!!!!!!!!!!!!!!!!!!!

About STL array

STL Array has been available since the 2011 version of C++ (C++11). Instead of declaring the array like the traditional array, it is a templated structure and we specify the data type of the array elements and the size as part of that declaration. Array object declarations come in this form:

array<DATATYPE,SIZE> NAME;

Now we don’t have to track the array size anymore, but we still may want an item count to keep track of how many items have actually been stored in the array.

int item_count = 0;
array<string,5> word_array;

To access the array’s size, we use its size function:

cout << wordArray.size();

To access the array’s size, we use its size function:

void ArrayObjectProgram()

****************************************
CURRENT ARRAY:
wordArray[0] = Pizza
wordArray[1] = Burrito
wordArray[2] = BibimBap
wordArray[3] = Biriyani
wordArray[4] = Shawarma

Total items in array: 5/5
Enter a WORD to add to array or STOP to stop: Tacos

!!!!!!!!!!!!!!!!!!!!!!!!!!
!! ERROR! Array is full !!
!!!!!!!!!!!!!!!!!!!!!!!!!!

About STL vector

The STL Vector is essentially a dynamic array that has been implemented for us already. We can use its functionality to store data in an array structure without having to worry about pointers, resizing, etc. Vectors are declared like this:

vector<DATATYPE> NAME;

To add an item to the vector we need to use its push_back function:

VECTORNAME.push_back( VALUE );

To get the amount of items stored in the vector we use its size function:

cout << VECTORNAME.size();

void VectorProgram()

****************************************
CURRENT VECTOR:
wordVector[0] = CS134
wordVector[1] = CS200
wordVector[2] = CS210
wordVector[3] = CS211
wordVector[4] = CS235
wordVector[5] = CS250
wordVector[6] = ASL120

Total items in array: 7
Enter a WORD to add to the vector or STOP to stop: STOP

About STL list

The STL List is similar to the STL Vector in that they store data in a linear manner (0, 1, 2, 3, …). However, a list is implemented as a series of linked nodes. With our STL List, we don’t have to worry about implementation, but note that we can only access the front or back of the list directly. Lists are declared like this:

list<DATATYPE> NAME;

To add an item to the vector we need to use its push_back function:

LISTNAME.push_back( VALUE );

or its push_front function:

LISTNAME.push_front( VALUE );

To get the amount of items stored in the vector we use its size function:

cout << LISTNAME.size();

We can view the contents of a list by using a range-based for loop:

for (auto& item : itemList)
{
  cout << item << endl;
}

void ListProgram()

****************************************
CURRENT LIST:
shark
aardvark
cat
squirrel

Total items in list: 4
Enter a WORD to add to the list or STOP to stop:

About STL map

A map is also commonly known as a dictionary or hash table. Maps are similar to arrays, except that instead of needing an index from 0 to arraySize-1, we instead can have any data type as a key – as a unique identifier for some data. Then, within the “element” of the array, we can have another data type to represent the data itself.

Think of your student ID: You have some unique student ID #, which would be a key. Looking up the key might give information like “name”, “major”, “class list”, etc. as the value (which would generally be represented by some class).

We declare a map like this:

map<KEYTYPE, VALUETYPE> MAPNAME;

We can assign a key-value to the map like this:

MAPNAME[KEY] = VALUE;

And we can iterate through all the key-value pairs with a range-based for loop:

for (auto& item : MAPNAME)
{
  cout << "\n\n KEY:   " << item.first;
  cout << "\n   VALUE: " << item.second;
}

We can access elements at a certain key with MAPNAME[KEY] as well, but if you want excpetion handling support, use the .at() function instead. Using catch( ... ) will catch all exception types.

try
{
  cout << MAPNAME.at( KEY );
}
catch( ... )
{
  cout << "Error";
}

void MapProgram()

ALL ITEMS IN MAP:
KEY: 1068 VALUE: Kaz Brekker
KEY: 1538 VALUE: Jesper Fahey
KEY: 5732 VALUE: Inej Ghafa
KEY: 8857 VALUE: Nina Zenik

Enter a student ID: 5732
That student is Inej Ghafa

For this program do the following:

1. DECLARE A MAP: Declare a MAP named “students” with integer keys and string values. Initialize the map with the following data:

2. DISPLAY ALL KEY-VAULE PAIRS: Display all items (key AND value) in the map using a for loop.

3. ASK THE USER TO ENTER AN ID: Have them enter an integer id.

4. TRY: Access the student at that ID within a try { } block. Display the student at that ID.

5. CATCH: If an exception is caught, just display an error message.

About STL stack

The Stack data structure is a type of first-in last-out or last-in first-out structure. Stacks (and queues, which follow) are restricted-access data types – when you work with a stack, you can ONLY interface with its “top”. Everything else is buried below, and only can be accessed once you remove all the layers on top. It’s like a can of pringles.

Declaring a stack takes this form:

stack<DATATYPE> STACKNAME;

Items can be added to the top with push:

STACKNAME.push( VALUE );

We can read the top-most item with top:

cout << STACKNAME.top();

Items can be removed from the top with pop:

STACKNAME.pop();

We can see how many items are in the stack with size:

cout << STACKNAME.size();

void StackProgram()

FINAL STACK FORM:
1.       f
2.       a
3.       c
4.       e

In this program create a stack of strings. Also declare a string for command and a string for input. Display the commands the user can use to manipulate the stack:

COMMANDS: 
PUSH word			-- Add "word" to the top of the stack
POP					  -- Remove the item at the top
STOP					-- End the program and view the stack

1. PROGRAM LOOP: Create a program loop with a while loop.

2. DISPLAY STACK SIZE AND TOP ITEM: Display the current stack size. If the stack size is greater than 0, then also display the item at the top of the stack.

3. ASK USER FOR COMMAND:

• If they enter “STOP”, then leave the program loop.
• If they enter “PUSH”, then get more user input into the input variable. Afterwards, push the input item into the stack.
• If they enter “POP” and if the stack size is greater than 0, then use the stack’s pop() function to remove the top-most item.

4. DISPLAY FINAL STACK FORM: After the program while loop, display all the items in the stack like this:

cout << endl << "FINAL STACK FORM:" << endl;
int counter = 1;
while (itemStack.size() > 0)
{
    cout << counter << ". \t" 
    << itemStack.top() << endl;
    itemStack.pop();
    counter++;
}

About STL queue

A Queue is also a restricted-access data structure. With a queue, you can only add new items to the back, and you can only access and remove items from the front. This gives us a queue, or a “line” like what you would stand in at a grocery store – first person in the line gets to check out first. (First in first out - FIFO)

Declaring a queue takes this form:

queue<DATATYPE> QUEUENAME;

Items can be added to the top with push:

QUEUENAME.push( VALUE );

We can read the front-most item with front:

cout << QUEUENAME.front();

Items can be removed from the front with pop:

QUEUENAME.pop();

We can see how many items are in the queue with size:

cout << QUEUENAME.size();

void QueueProgram()

FINAL QUEUE FORM:
1.       e
2.       c
3.       a
4.       f

In this program create a stack of strings. Also declare a string for command and a string for input. Display the commands the user can use to manipulate the queue:

COMMANDS: 
PUSH word			-- Add "word" to the back of the queue
POP					  -- Remove the item at the front
STOP					-- End the program and view the queue

1. PROGRAM LOOP: Create a program loop with a while loop.

2. DISPLAY STACK SIZE AND TOP ITEM: Display the current queue size. If the queue size is greater than 0, then also display the item at the front of the queue.

3. ASK USER FOR COMMAND:

• If they enter “STOP”, then leave the program loop.
• If they enter “PUSH”, then get more user input into the input variable. Afterwards, push the input item into the queue.
• If they enter “POP” and if the stack size is greater than 0, then use the queue’s pop() function to remove the front-most item.

4. DISPLAY FINAL QUEUE FORM: After the program while loop, display all the items in the queue like this:

cout << endl << "FINAL QUEUE FORM:" << endl;
int counter = 1;
while (itemQueue.size() > 0)
{
    cout << counter << ". \t" << itemQueue.front() << endl;
    itemQueue.pop();
    counter++;
}

Make sure to add, commit, and push your work to your u07ex branch. Afterwards, go to the GitLab repository page and create a Merge Request. The URL of the merge request is what you will turn in on Canvas.