COSC 2336 Data Structures & Algorithms Assignment: C++ Standard Template Library- University of Texas- Tyler
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
You may work on any of the following tasks:
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 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() 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<() to determine priority ordering, similar to what we did in our assignments.
Demonstrate creating a priority queue on a type you de ne yourself (like a Job class, or an Employee class). Your user de ned type can be simple, but make up some key of the class that de nes the priority. Either overload the operator<() operator on your user de ned class, or else implement a separate comp() function and pass that in when you construct your priority queue. Demonstrating push() items of your user de ned type onto the queue, and that they are then removed in priority order using top() and pop(). Demonstrate the size() and empty() member functions being used as well.
5. Associative containers implement dictionary or key/value pair API mappings in the C++ STL. The C++ STL library splits associate containers into ordered and unordered associative containers. The map associative container implements a basic mapping or dictionary API. A map is an example of an ordered associative container. The map is im- plemented using a binary search tree, so insertion, search and removal are all O(log2(n)) operations. A binary tree is used because order matters, and we want to be able to access the items in sorted order (using an inorder traversal) from the collection when we iterate over the items. So when you iterate over a map you will nd that the items come out of the map in sorted order. As with the priority_queue, you can pass an explicit comparison function to de ne ordering of the map, though it will default to using an overloaded operator<() if you don't provide this function.
Demonstrate creating a map associative container, that maps a key (not an integer, use a string or double or char something else) and adding at least 5 items to the map. Demonstrate using some of the member functions of the map like empty(), size(), etc. You can actually use the operator[] to access a value indexed by a particular key, e.g. the operator[] will perform the search for a key. But notice, in this case, you don't provide an integer index, but you provide a key of whatever type is used for keys in your map. Demonstrate using the operator[] to nd keys in your map. Since a map is ordered, when you iterate over the map the items will be accessed in sorted order. Demonstrate iterating over your map, and show that items come out in sorted order when you iterate the map.
6. The unordered_map also implements a dictionary or key/value con- tainer API. However, as the name implies, there is no concept of or- dering maintained on the items for an unordered_map. This is because an unordered_map uses hashing and a hash table, to maintain the as- sociation between key/value pairs. So time to insert, remove and nd items in an ~unorderedmap` is constant time O(1), compared to the O(log2(n)) time for these operations needed for the ordered map con- tainers in STL.
Demonstrate creating an unordered_map associative container, that maps a key (not an integer, use a string or double or char or some- thing else) and adding at least 5 items to the unordered_map. Demon- strate using some of the member functions of the unordered_map, like empty(), size(), max_size(), etc. You can actually use the operator[] to access a value indexed by a particular key, e.g. the operator[] will perform the search for a key. But notice, in this case, you don't provide an integer index, but you provide a key of whatever type is used for keys in your unordered_map. Demonstrate using the operator[] to nd keys in your unordered_map. Since a unordered_map is unordered, when you iterate over the map the items will not be in any particular order (because the iterator searches through the hash table, and because the hash function spreads out the keys essentially randomly, there is no inherent order to the collection). Demonstrate iterating your unordered_map, and show that the items come out in a random order.
7. Besides containers, there are also algorithms you can use in the STL library. These are functions you can call, usually passing in a STL con- tainer of some type to be operated on. For example there are functions to do search and binary search on containers, a partition function that basically performs the partitioning we did in our quick sort assignment, functions for heaps, and basic functions like nding min, max, etc.
There are also functions for performing sorts and partial sorts. The sort() function in the 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.
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.
Format your assignment according to the following formatting requirements:
1. The answer should be typed, double spaced, using Times New Roman font (size 12), with one-inch margins on all sides.
2. The response also includes a cover page containing the title of the assignment, the student's name, the course title, and the date. The cover page is not included in the required page length.
3. Also include a reference page. The Citations and references should follow APA format. The reference page is not included in the required page length.