CSE 4208: Studio 19

Associative Containers


Today's lecture and studio focus on associative containers, including how how different associative containers organize the elements within them, how insertion and erasure of their elements work, and how the operators defined over the types they contain affect those topics. You will also use different container member functions and standard library algorithms to operate over the elements in a container.


Please complete the following required exercises. I encourage you to please work in groups of 2 or 3 people on each studio (and the groups are allowed to change from studio to studio) though if you would prefer to complete any studio by yourself that is also allowed.

As you work through these exercises, please record your answers, and when you finish them please log into Canvas, select this course in this semester, and then upload a .txt file containing your answers on the Canvas page for this studio assignment. Only one submission per team, please, and if you need to re-submit it the person who originally submitted the studio should please be the one to do that.

Make sure that the name of each person who worked on these exercises is listed in the first answer, and make sure you number each of your responses so it is easy to match your responses with each exercise.


Required Exercises

  1. As the answer to the first exercise, list the names of the people who worked together on this studio.
  2. First, ssh into shell.cec.wustl.edu using your WUSTL Key id and password and then use qlogin to log into one of the Linux Lab machines and then confirm that the version of g++ there is correct (as you did in Studio 0). Then cd into your directory for this course this semester, create a new subdirectory for this studio, and cd into it.

    Copy over the CMakeLists.txt from one of your previous studios into your directory for this studio, and as you work on this studio update it so that it builds an executable binary file named studio19 from the source and header files you develop.

    Add a new source file and in it define a main function that (1) declares a container of type set<string> (for a set of C++ style strings), and then (2) uses the copy algorithm with pointers to the beginning and just past the end of argv and an inserter, to transfer all the C-style strings that were passed to the main function (including the program name) into the set container, and then (3) uses the copy algorithm again, with the set container's begin() and end() member functions and an ostream_iterator, to print out all the strings in the set to cout.

    Compile your program and run it with different command line arguments (including some trials where the same argument is passed more than once on the command line) and as the answer to this exercise please (1) explain whether or not the container enforced uniqueness of the keys in the container and (2) show output from your program that supports that conclusion.

  3. Repeat the previous exercise for a container of type set<char*> (hint: don't forget to update the types of your iterators etc. as needed). As the answer to this exercise please describe any differences you observed compared to the previous exercise, and if there were differences in the output please explain why you think they occurred (hint: think about what operator might be used for the comparison, and how it is defined over char*).

  4. Add a new header and source file to your directory for this studio, and in them declare and define a function that takes two references to const C++ style strings and returns a bool that is true if and only if the first is greater than the second. In your main function declare a set container to hold C++ style strings and order them according to the function you wrote. Hints: using decltype as is shown in the example in section 11.2.2 of the LLM text book can help with this, and don't forget to pass the function into the constructor for the set container itself as is also shown in that example.

    Again use the copy algorithm with pointers to the beginning and just past the end of argv and an inserter, to transfer all the C-style strings that were passed to the main function (including the program name) into that set container, and then use the copy algorithm again, with that set container's begin() and end() member functions and an ostream_iterator, to print out all the strings in the set to cout.

    Compile and run your program and run it with command lines that include the same strings multiple times and arrange the strings in different orders. As the answer to this exercise (1) show the code you wrote for it and (2) the output your program produced for one run that illustrates how the keys are being ordered in that set.

  5. Repeat the previous exercise using a multiset container of string elements that is ordered according to the comparison function you wrote in the previous exercise. Compile your program and run it as in the previous exercie, and as the answer to this exercise please describe any differences you observed compared to the previous exercise, and if there were differences please explain why you think they occurred.

  6. In your main function, copy the command line arguments into another container, of type multiset<string> (leaving off the comparison function from the previous exercise), and then use a string that was inserted into the container multiple times and the container's equal_range member function to obtain iterators bounding all occurrences of that same string in the container. Use those iterators with the copy algorithm and an ostream_iterator to print out all the equivalent strings.

    Compile and run your program, and as the answer to this exercise please show (1) the code you wrote to do that and (2) the output that it produced.

  7. Starting with the code from the previous exercise, after printing out the equal range, please try the following: (1) call the container's erase member function using the first iterator returned from equal_range, and (2) change the call to erase to use both iterators returned by equal_range.

    For both of those variations, compile and run your program with inputs that will put the same string multiple times into the container, and as the answer to this exercise (1) explain any differences you saw between the two variations, and (2) show output that supports your explanation.

Things to Turn In:

For this studio, please turn in the following: