please check the pdf file attached below.
Assg
1
4
: C++ Standard Template Library (STL)
(Extra Credit Opportunity)
COSC
2
3
3
6
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
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
http://www.cplusplus.com/reference/stl/
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<() 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
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 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
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 �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
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