This lab will walk you through some exercises using Sets and Maps. As usual, we ask that you work with a partner or a team. If you end up solo, please raise your hand and we'll pair you with someone else (or make a three-person team if necessary). You are welcome to change partners throughout the semester!
Task 1.0: preliminaries
Download dictionary.txt, which contains a large body of strings we'll use for testing.
Next, download lab07a.cpp. Go ahead and create a new project in CLion as usual, and upload the starter code and dictionary.txt to it. The dictionary.txt should be in your cmake-build-debug folder.
Task 1.1: figure out what is going on
Read through the lab07a.cpp code provided. Much of the code is stuff you have seen before or practiced in a previous lab - opening a file, reading in its contents, or adding items to a vector. Some of it may be less familiar, but the comments should help.
In brief, the code is doing the following:
TEST_SIZE) to use as a test collectionPay close attention to the timing code, as you will need this again, and it is generally useful to have for your own performance optimization of your code in the future. If you want to see how long an operation will take coded one way versus another, wrap some timing code around it and find out. The only catch is, computers are so fast that you won't get very helpful numbers unless you perform the operation many times - which is what the TEST_SIZE parameter in our program is for.
The clock() function is the critical piece of the timing code. It returns a value of type clock_t, which is a number counting the "ticks" of some architecture/operating system-dependent clock since the start of the program. You get the clock value at the start of what you want to time, then again at the end, and subtract to get the number of clock ticks. For human eyes, it is generally helpful to convert to standard seconds - you do this by dividing by CLOCKS_PER_SEC. CLOCKS_PER_SEC and the clock() function are both provided in the <ctime> library.
Run the starter code:
Calibrate the TEST_SIZE constant at the top of lab07a.cpp. You want the code to take long enough to see that something is actually happening, but you don't want to spend all your time waiting. If the timed part of the program is in the 5 - 15 seconds range, that's about what you want. Adjust TEST_SIZE downward to reduce the time, adjust it upwards to increase the time (recompile each time).
Task 1.2: time using a vector as if it were a set
In the lecture on Sets and Maps, we described the Set as an ADT having three principal operations: adding, removing, and testing for containment. For the first part of our experiment today, we are going to see how well a vector does at one critical operation: testing for containment. The provided code does just that, by filling a vector with (unique) words and repeatedly looking for the word in the vector.
The way you look for a string in an arbitrary vector of strings is: start at the beginning, comparing words as you go - as soon as you find the word, stop and return true. If you get to the end without finding the word, return false. There are 127,141 words in dictionary.txt, but looking through them one at a time is still very fast - which is why we have to test using so many words! The provided code uses the <algorithm> library function find() to search the vector in the fashion described, but you could just as well loop on the size of the vector with an index, or even do a range-based for loop (although find() is generally faster).
Run the provided code three times to collect three different timings; they shouldn't vary by much. Record the timings for entry into Canvas!
Task 1.3: time using a set as a set
Rewrite the provided code to now perform the same tests using a set instead of a vector - you should also remove the call to find() function and instead use the count() or find() methods of set to test for the existence of a value in the set (the find() function we used for vectors works for sets, but doesn't take advantage of the set's ability to do fast lookups). Make sure you leave TEST_SIZE unchanged, so you can compare fairly against your vector tests. Record timings for three trials using the set.
Task 1.4: understanding the performance difference
How was the set so much faster at looking up values? Investigate the complexities of searching in sets vs vectors, and write a short reasoning in Canvas. Now, try testing the speeds with an std::unordered_set and compare performance.
For further exploration and extra credit, choose one or more of the questions below, and provide a paragraph or so answering the question in Canvas.
For part 2, you are going to first get comfortable with using a map. Maps are extraordinarily useful data structures for their capability of having key/value pairs to represent useful information. For this part, simply read the source code (lab07b.cpp) and try to understand what is going on. Import this as a separate project into CLion so that you can properly run the program.
Now that you have the restaurant simulator running, play around with it! Type in
Burger
Fries
Sandwich
quit
and see what kind of output you get! You should get the output of $9. What's really important in this part is understanding some of the basic functions of a map. Take a close look at how we are "putting" items to the list and how we are "getting" items from the list. Test to see if you can add another item to the menu:
Apple 2
Where did the apple item appear in the menu? Take note of ordering in maps as well. You can also compare the ordering using std::unordered_map and check out the order of the items in the menu. Also notice, that if you would like to traverse through a map, we want to use