Student: Stanley

Programming Assignment

Assg 14: C++ Standard Template Library (STL) (Extra Credit Opportunity) COSC 2336 Fall 2019 Dates: Due: Sunday December 08, by Midnight Objectives ˆ Practice using an enterprise level set of data structures and algorithms provided by the STL. ˆ Connect what we learned about things like stacks, queues, lists, dictio-naries, etc. to their implementations and applications from the C++ STL. Description This assignment is a bit di erent than the previous assignments in the class, and is being given as an extra credit opportunity. The assignment is open ended. I have described 7 tasks or items you can perform, involving the C++ standard template library. I will give up to 5 points for each of the 7 tasks (for a total of up to 35 points), that will be considered extra credit, and applied to your programming assignment portion of the course grade to make up some points on past programs in the class. This assignment is open ended. I have not given you any starting code or tests/assertions to use for the assignment. To get credit for the assignment, you should submit a single le named "assg14-stl.cpp". The le should be compilable and runnable using the C++ IDE/compiler environment you and I have been using this semester for the class assignments. I would prefer that you create a separate function for each of the tasks you chose to submit work for, and that your main function simply calls each of the functions for the 1 task. Your functions should be documented and code formatted using the usual class style guidelines. You can make up some work for the functions to do, e.g. to pass them in a parameter and return a value, if you wish. However, it is also su cient to simply have void functions that take no parameters. You should, though, add some output and test assertions of your own to demonstrate your code working on the tasks using the STL containers and algorithms. Also if you do more than 1 task demonstrating a container, make sure you always use a di erent type to be stored in the container. For example, don't demonstrate all of your containers on values, use a variety like , or even better, create your own small structure or class and demonstrate a container of those user de ned types you created. You should use our textbook for reference on using the STL containers and algorithms. Another good online reference for the C++ STL is: cplusplus.com: http://www.cplusplus.com/reference/stl/ You may work on any of the following tasks for this extra credit oppor-tunity: 1. The STL divides up its containers into 4 categories. The simplest are the sequence containers, which are intended to store data and access it in a sequential manner. Vectors are like basic arrays in C, but they are dynamic and have the ability to resize themselves automatically when an element is inserted or deleted. Vectors really use C arrays for their implementation. Insertion can be done in O(1) time to the end, though if the vector becomes full it will take longer because the vector needs to be grown. Removing the last item is also constant time, but if you want to insert or remove from the beginning or middle it will take linear time, because of the need to shift the items. Create a vector of whatever type you like and demonstrate adding at least 5 items to the end of it. Demonstrate using some of its methods, like size(), empty(), max_size() and or others. Vectors have the operator[] overloaded on them so you can access them and index them like a normal array. Demonstrate this. Remove insert() and erase() an element from inside of the vector. Demonstrate using an iterator to access the items in a linear. 2. Another basic sequence container is the list container. Lists are ac-tually implemented as doubly linked lists. You can insert on either the head or tail of the list in constant time (using push_front() or push_back() respectively. Insertion and removal from the middle of 2 the list still requires you to do a O(n) linear search to nd the location where you want the item, but once located no shifting needs to be done since it is a linked list data structure, simply need to repoint pointers as needed to get or remove the item from the list. Create a list of whatever type you like and demonstrate adding at least 5 items to the beginning and end of it. Demonstrate using its methods like size(), empty(), etc. Demonstrate removing items from the beginning and/or end of the list, and inserting or removing an item in the middle. A list in the C++ STL is the only container that supports a sort() method directly. Demonstrate using this method to sort your list, then iterate over the list displaying the items. Because a list is doubly linked, it is possible to iterate over it in reverse order. Also demonstrate accessing the items in reverse order. 3. The stack and queue containers are what are called container adapters. They provide a stack and queue API/interface, but underneath they use one of the standard sequence containers. By default the stack and queue containers use a deque, which stands for a double-ended queue. A deque is similar to a list, it allows constant time access to add and remove items from the end of it. So since for a stack you always only add and remove items from the end, and for a queue you add items to the end and remove from the front, the deque is e cient for implementing both of these APIs. Demonstrate using either the stack or queue container adapter. For the stack, you should reimplement one of the 4 functions you did for assignment 10 on stacks, but using an STL stack container adapter instead of our hand created Stack class. For queue you can implement one of the following as a function: (a) Write a function that uses a queue and a stack to reverse the items on the queue. The queue passed in should be in reverse order when you return. Thus if you have items [1, 2, 3, 4, 5] on the queue, after returning from the function, the queue would be [5, 4, 3, 2, 1] (b) Write a function to reverse a queue, but instead of using a stack, make the function recursive and implicitly use the function call stack to perform the same reversal operation. (c) If you only have a queue, you can perform a kind of bubble sort to sort the items on the queue. Only using the queue push() 3 and pop() operations, you start by rst popping all items from the front and returning them to the back, but remembering the smallest item you see. Then you perform a pass again, except when you come to the minimum item you saw in the rst pass you don't push() it back, you instead wait until you are done with this pass and then push the minimum value on to the back. If you perform these 2 passes n times (the number of items in the queue), but each time you search for the minimum value that is larger than the minimum found in the previous round, at the end of n passes the queue is sorted. 4. The priority_queue is another container adapter that implements a priority queue like you did for assignment 11 on queues. However, the C++ STL priority_queue maintains a heap of the items, in order to support e cient constant time insertion and retrieval of the highest priority item from the queue (if you recall we talked about this brie y, but in assignment 11 you simply performed a linear search whenever you needed to dequeue an item, to nd the item with the largest value). We could of course replace your own implementation of the priority queue in assignment 11 with the STL version, but that is not the task here. Instead simply demonstrate creating an stl priority_queue con-tainer adapter. The way that the priority_queue handles determin-ing the order of items, is that you can pass in a function that will take 2 items of the container type T, and should compare them using less than ordering, so if you have comp(a, b) and a is less than b the function should return true, otherwise it should return false. However, if you don't give this function when you create the priority_queue , the container instead defaults to using the operator library can be used to sort a container of items that are implemented as random access storage (ba-sically they use something like an array, not a linked list). You can use sort() to sort vector and regular C arrays in memory (not list though list has its own sort() function). The sort() is guaranteed to be O(log2(n)), and is usually implemented using some version of quicksort like you implemented in your assignment. Demonstrate using sort() to sort both a regular C array of values, and a vector of values. Have at least 5 values in each, and iterate over them before and after calling the sort, to demonstrate the items are unsorted then sorted. Assignment Submission A MyLeoOnline submission folder has been created for this assignment. You should submit a single le named "assg14-stl.cpp". The le should be com-pilable and runnable as submitted, and each task you work on should be implemented in a separate function, and all functions called and/or tested from your main() function. You should attach and upload your completed "assg14-stl.cpp" source les to the submission folder to complete this assign- 6 ment. Please only submit the asked for source code les, I do not need your build projects, executables, project les, etc. Requirements and Grading Rubrics Program Execution, Output and Functional Requirements 1. Your program must compile, run and produce some sort of output to be graded. 0 if not satis ed. 2. I will give up to 5 pts. extra credit, added to your assignments score for the course, for each of the tasks. There are a maximum of 35 points of extra credit available in this assignment. Program Style Your programs must conform to the style and formatting guidelines given for this class. The following is a list of the guidelines that are required for the assignment to be submitted this week. 1. Most importantly, make sure you gure out how to set your indentation settings correctly. All programs must use 2 spaces for all indentation levels, and all indentation levels must be correctly indented. Also all tabs must be removed from les, and only 2 spaces used for indentation. 2. A function header must be present for member functions you de ne. You must give a short description of the function, and document all of the input parameters to the function, as well as the return value and data type of the function if it returns a value for the member functions, just like for regular functions. However, setter and getter methods do not require function headers. 3. You should have a document header for your class. The class header document should give a description of the class. Also you should doc-ument all private member variables that the class manages in the class document header. 4. Do not include any statements (such as system("pause") or inputting a key from the user to continue) that are meant to keep the terminal from going away. Do not include any code that is speci c to a single operating system, such as the system("pause") which is Microsoft Windows speci c. 7

Budget: $10.00

Due on: May 03, 2020 00:00

Posted: 5 months ago.

Answers (0)