CS 14 - Lab

Advanced STL - Associative Containers and Algorithms

In this lab, you will be learning about a few advanced STL topics including associative containers and algorithms. You will do some short exercises to help introduce you to these topics. For this lab you will be working independently. You may want to look at the STL reference guide for more information.

Associative Containers - Maps

The sequential containers you have used thus far (list, vector, and deque) are very useful but they provide you with code that you could easily reproduce in a few hours. However, associative containers provide implementations for data types that you could not so easily duplicate in a few hours of coding. Associative containers (aka associative arrays) store items based on keys. In a compiler, a symbol table can be used to store memory addresses of variables and functions within the code. If you were to write a compiler and you used an associative array for your symbol table, you can easily accesses the memory addresses using syntax such as this:

This is a very intuitive way to code, but C++ does not have built in support for associative arrays (some languages such as Perl have built in support for associative arrays). Luckily, with STL, associative arrays are very simple to use and you can use anything that you want as the index: built-in types, user-defined structures, classes, etc. Associative containers are implemented as red-black trees for efficiency.

Today you will be learning about the map associative container. The map container comes in the form of map<Key, T, Compare> where Key is the key you will use to do lookups, T is the data to store at that location, and Compare is a function object that compares two key values. For maps using built-in types for keys, you can use the less< > function object template:

map<string, string, less<string> > stringMap; If the key values are user defined types, you will need to overload operator <().

Part 1 - Learning Maps

For part 1 of your assignment, you will be doing a very simple program involving maps and the number of days in each month. Key will be the month name and T will be the number of days in that month (see above for the syntax used to declare a map). Use the following procedure to complete part 1:

1. Create a file called part1.cc. Make sure to include the map header file
2. Declare a map that uses the month as the Key (a string) and stores the number of days (int) as the data (see above for similar syntax for declaring a map). Call the map months
3. Insert all of the months into your map. For example, your first line will be: months["january"] = 31; Continue with the rest of the months (you may need to search online if you don't know the number of days in each month off hand). Assume a non-leap year (February has 28 days)
4. Print out all of the items in the map. You can iterate through the map exactly like you did for a list in lab5. However, maps are slightly different. The iterator has two fields: first and second. First refers to the current key and second refers to the data. So to print out the month name and assuming your iterator is called it, you can type cout << (*it).first and to print out the number of days, you can type cout << (*it).second. Print out the information in the form "There are X days in the month of Y" with one month on each line
5. Now adjust your map for leap year (February now has 29 days) and print out information again.
6. The output of your program should look similar to this.

Algorithms

STL also provides you with various templatized algorithms that are very simple to use. Algorithms are simply templatized functions. There are many types of algorithms but I will only cover 2: sort and accumulate.

sort - The sorting algorithm allows you to sort any type of data structure whether it is a built in type of a user defined type. Sort works by using the < operator for the objects being sorted. If you are sorting built-in types the < operator is already defined for you. If you are sorting user defined types, you will need to overload the < for the type. Sort can be used in two different ways:

If you have an object defined such as: list<int> intList, you can sort the list by calling: intList.sort ( ). You can call sort this way since a list is an STL type and sorting is an extremely common thing to do, sort has been implemented as a member function
Sort can also be used like this: sort ( begin, end ). For instance, if you have an array: int arr[SIZE], you can easily sort your array by using: sort ( arr, arr + SIZE ).

accumulate - Accumulate repeatedly applies a function to each member of the input sequence and returns the result. For instance, if you want to add up all of the values in an integer array, you can use accumulate to do this. However, accumulate is flexible so that you can specify what function you want to apply to each member of the input (for instance you could muliply all of them together). Accumulating is such a common operation, that many computer architectures have accumulation registers (you will learn more about this in cs61 and cs161). The STL accumulate comes in 2 different offerings:

accumulate ( first, last, init ), where first is the first item in the input sequence, last is one past the last item in the input sequence (like intList.end ( ) or arr+SIZE ), and init is the intial value to start accumulating with (0 for doing addition accumulation and 1 for doing multiplication accumulation).
accumulate ( first, last, init, binary_op ). First, last, and init are the same as those described above. Binary_op is the operation you want to apply to all of items in the input sequence and includes many predefined operations such as plus, minus, multiplies, divides, etc.

Part 2 - Learning algorithms

For part 2 of your lab, you will use the sort and the accumulate algorithms. You will create a list of integers and an array of integers and apply these algorithms to both. Use the following procedure to complete part2:

1. Create a file called part2.cc. Be sure to include the algorithm and numeric header files for sort and accumulate. Also include cstdlib so you can generate random numbers.
2. Create an SLT list of integers and an array of integers of size 10
3. Fill the list and the array with the same random numbers between 0 and 19. Seed with time (0). If you need more information about random numbers and seeding, you may look here.
4. First operate with the list. Print out the random numbers in the list.
5. Sort the numbers in the list using the sorting algorithm as described above
6. Print out the sorted numbers.
7. Use the accumulate alogoritm to compute the sum of all of the numbers in the list and the product of all of the numbers in the list and print the sum and product out. For the sum, use the first accumulate method discussed above. For the product, use the second accumulate method discussed above and use the Binary_op of: multiplies<int >()
8. Repeat the above procedure for the array of numbers.
9. Run your program multiple times to see how the random numbers change and the sum and product changes. If you have not seeded your random function correctly, you will always get the same values on each run. If this is the case, return to step 3 to fix your random seed. (Sometimes the product will come out as a negative number. This is not an error. The number was too large and an overflow occured causing the value to be negative.
10. Your output should look similar to this.

Point Breakdown For Lab Assignment

You will be working alone for this lab. The lab will be due 1 hour after the end of your lab section NEXT WEEK. I am giving you an extra week so that you can get help from the TA if you need it. You may demo your program in lab NEXT WEEK or it will be graded from your electronic submission. Please show the output from part1 and part2 to the TA. The TA will also look at your code for correctness when checking out. Remember, to receive credit for this lab, you MUST turn the code in online. If you do not turn in your code online, you will lose points for your lab. All code must be turned in online for archival purposes.

Remeber to compile your code using the flags "-g -Wall -W -Werror -pedantic". For this lab you do not have to use a makefile since you are creating 2 standalone programs each in a single file.

2 points - Attendance is, as always, worth 20% of your lab grade.
4 points - Correct output and implementation for part1 (we will check your code to make sure you used the map correctly and as specified).
4 points - Correct output and implementation for part2 (we will check your code to make sure you used the sort and accumulate functions as specified).
Deductions -

-1 point - If both partners turn in the code. There should only one turnin per group
-1 point - if your program seg faults at any point during execution.
-1 point - program does not compile with the standard flags: -Wall -Werror -W -pedantic
-.5 points - Did not use constants for SIZE and RANGE in part2.
-.5 points - Did not seed random with time(0). The TA will run part2 muliple times to make sure that the random numbers do indeed change
-5 points - Turned into the wrong lab section.
-1 point - No name on work turned in
-5 points - Code not turned in at all. This deduction also applies to turnins that do not contain a the partners name (only the name that is not on the turnin will have 5 points deducted. The person that actually turned the code in will only have 1 point deducted if their name is not on the turnin).
-5 points - If your currently assigned partner is in lab and you do not work together.

+ 1 point extra credit - For part 2, choose another algorithm from the STL reference guide and apply the algorithm to both the list of ints and the array of ints. If you check out in lab, you can show this to the TA. If you turn the code in electronically, include a readme file explaining which algorithm you used