Can someone solve?

This assignment is a bit different 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 file 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 sufficient 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 different 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 defined 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 opportunity:

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 actually 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 find 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 re-point 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 efficient for implementing both of these APIs. Demonstrate using either the stack or queue container adapter. For the stack, you should re implement 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 first 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 first 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 efficient constant time insertion and retrieval of the highest priority item from the queue (if you recall we talked about this briefly, but in assignment 11 you simply performed a linear search whenever you needed to dequeue an item, to find 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 container adapter. The way that the priority_queue handles determining 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 define yourself (like a Job class, or an Employee class). Your user defined type can be simple, but make up some key of the class that defines the priority. Either overload the operator<() operator on your user defined class, or else implement a separate comp() function and pass that in when you construct your priority queue. Demonstrating push() items of your user defined 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 4 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 implemented 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 in order traversal) from the collection when we iterate over the items. So when you iterate over a map you will find that the items come out of the map in sorted order. As with the priority_queue, you can pass an explicit comparison function to define 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 find 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 container API. However, as the name implies, there is no concept of ordering maintained on the items for an unordered_map. This is because an unordered_map uses hashing and a hash table, to maintain the association between key/value pairs. So time to insert, remove and find items in an ~unordered map` is constant time O(1), compared to the O(log2 (n)) time for these operations needed for the ordered map containers in STL. Demonstrate creating an unordered_map associative container, that maps a key (not an integer, use a string or double or char or something else) and adding at least 5 items to the unordered_map. Demonstrate using some of the member functions of the unordered_map, like empty(), size(), max_size(), etc. You can actually use the 5 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 find 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 container 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 finding 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 (basically 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.