CS 14 - Lab 7
CS 14
Homepage
The Standard Template Library - STL
STL is a template based library of generic C++ data structures and algorithms
that work together in an efficient and flexible fashion.
I can guarentee that STL will be your best friend throughout your
C++ programming career so please take a lot of time to become aquainted with
it. This lab will help you do that through 3 short exercises (you will be
writing 3 seperate programs but to make things quick, you may
write all of your code in the main function using 1 file and no makefile).
In this lab
you will learn about sequence containers, container adapters, and
iterators.
There is a fantastic reference for STL available online
here. You may want
to refer to this while working on your lab assignment.
Sequence Containers
Containers are objects that store other objects. You will be looking at the
vector, deque, and list containers. The declaration of a container
defines the type of object it will hold (much like the declarations
you have done previously for your own template classes).
Containers store user defined objects as data members. For example, you may
declare a lists like this:
list<int> intList.
list<Node> nodeList.
list<anyClass> anyList.
You choose the
appropriate sequence container based on what your program will be doing. You
will be looking at 3 sequence containers:
- vector<T> is a standard array that can change size transparently as
needed (any increase in size is added to the end of the vector).
Internally, it is a contiguous array of elements and you can
perform all operations on vectors that you would normally perform on
an array ([] accessing). Unlike traditional arrays,
vectors are good because their size can grow
transparently, however the size may only grow from the end. Because of this
vectors are good for any LIFO type application
- deque<T> is a queue data structure that efficiently inserts and removes
objects from either end. Like vectors, the elements are stored in
contiguous locations in memory. Unlike vectors that can only grow
efficiently when inserting at the end, a deque can efficiently expand from
the beginning
and the end. The deque may also be accessed through the [] operator
as with the vector container. Deques are good for any FIFO type
application.
- list<T> is a doubly linked list and is exactly like the lists we have
been studying in class.
The list can grow from any location by pointer manipulation except you
don't have to do the pointer manipulation. You
can't access elements in the list using the [] operator.
This will give you a graphical representation of how
the different containers are layed out in memory
When choosing a container, you must predict what types of operations you will
be doing and analyze the cost of each container. Here
is a table showing the costs of various operations for each container type.
Based on what you learned about the memory layout of each container type,
take some time to understand the costs in this table and why each operation
has the specified cost for each different container. If you don't understand,
make sure to ask your TA to explain because you will be quizzed on this
when you check out.
Every container type has many functions predefined for your use. For example,
the following declares a list of ints and inserts 2 numbers and removes them
(the function names are quite self explanatory):
list<int> a;
a.push_back(1);
a.push_front(5);
a.pop_front();
a.pop_back();
Iterators
When manipulating the contents of containers, you will find yourself heavily
dependent on iterators. Iterators fulfill the same role in your program
as pointers, and whereas they are not exactly the same as pointers, you may
use the concept of a pointer as an easier way to grasp the concept of
an iterator. Like pointers, they are defined in terms of what they do.
For instance a pointer to an item of type T is declared as "T* ptr"
and an iterator to a container is declared as
"container<T>::iterator i."
Like pointers, iterators are dereferenced using the * operator. Iterators are
used to get back the data that you have inserted into the list.
for (list<int>::iterator i = a.begin(); i != a.end(); ++i)
cout << *i << endl;
You can also insert and erase elements using iterators:
a.insert ( a.begin ( ), 6 );
a.erase ( a.begin ( ) );
Both the begin() and end() functions return an iterator. Begin() returns an
iterator to the first element in the list and end() returns an iterator that
is 1 location past the last element in the list. You WILL want to memorize
this.
Container Adaptors
Container adaptors are simply classes that act as a wrapper around another
class. Container adaptors are classes that encapsulate an existing container,
and provide a new user interface. You will look at the queue and stack
container adaptors. For instance, stacks and queues both have push
and pop functions that operate differently depending on whether or not you
are using a stack or queue. For that reason, the push and pop operators
are not included as functions for containers. However, a container adaptor
can define these functions for you. When declaring a container adaptor, you
may choose any container as you like for the internal representation. (Notice
the different and precise syntax of the following)
- Declaring a stack container adaptor using a vector container:
stack< int, vector<int> > a;
- Declaring a stack container adaptor using a list container:
stack< int, list<int> > a;
- Declaring a queue container adaptor using a vector container:
queue< int, vector<int> > a;
- Declaring a queue container adaptor using a list container:
queue< int, list<int> > a;
Now consider the following code. The push and pops will work
correctly based on the container adaptor. Other container adaptor
specific functions are implemented as well.
stack< char, list<char> > s;
queue< char, list<char> > q;
s.push(a);
s.push(b);
s.top(); // gets reference to b
s.pop(); // pops b
q.push(a);
q.push(b);
q.front(); // gets reference to a
q.back(); // gets reference to b
q.pop(); // pops a
For the most efficient program possible, you must choose your container
wisely depending on what your program operations will be.
First Lab Program - 3.5 points
Write a program using the STL list (remember to #include <list>). Call
your file "part1.cc" Your
program should read in integers from the standard input (using cin) until
the user presses Ctrl+D (to signify EOF). Store each value at the end of the
list. (If you don't know how to read until EOF, read
this.
Next, insert two more values to the list. Insert the value 10 at the head
of the list and insert the value -1 at the end of the list
Print the list
Pop the 10 and the -1 off the front and the back of the list.
Print the list again
Demo your program.
Second Lab Program - 2 points
Redo part on using a vector instead of a list (remember to #include
<vector>). Name your file "part2.cc"
Demo your program
Third Lab Program - Recognizing Palindromes - 2 points
A palindrome is a string of characters that reads the same from left to
right as it does from right to left. For example, noon and racecar are
palindromes. You should know by now that you can use a stack to
reverse the order of a occurances and you can use a queue to
preserve the order of occurances. With this you can use both
a stack and a queue to determine whether a word is a palindrome or not.
Write a program to determine whether or not a word is a palindrome. Name your
file "part3.cc" Your program will read in 1 word from the standard input
(using cin) and output whether or not it is a palindrome. You must read
in a string but remember that a string is an STL class and you may use
the [] operator to access each character. You will
use the queue and stack container adaptors to analyze the word.
Make sure to choose an ideal
container for your queue and stack. You will receive 1.5 points for
correctly determining whether or not a word is a palindrome. You
will receive .5 points for choosing the correct containers and being able
to explain why you used those containers. Insert a comment into
your code near your stack and queue declarations explaining your
container choice (we don't want you saying this answer out loud or else
you will give the answer away to others). To receive these points,
you MUST have the comment
For 1 point extra credit, make your program determine if a line of words
with spaces
is a palindrome (for example, "Race carrot or race car" is a palindrome.
To get this 1 point, your palindrome tester must be case insensitive.
Point Breakdown For Lab Assignment
You must demo all programs in lab. The TA will look at the output of each
program and also
look at your code for correctness when checking out. Remember, to
receive credit for this lab, you MUST turn the code in online even if
you have already demoed in lab If you do not turn in your code online,
you will lose points for your lab. All code must be turned in online for
archival purposes.
Remeber to compile your code using the flags "-g -Wall -W -Werror -pedantic".
- 2 points - Attendance - Lab attendance will be 20% of the grade for each
lab. You will receive 1 point when the lab begins and 1 point when the lab
ends. Attendance will be taken during the first and last 5 minutes of the
lab period
- 3.5 points - First lab program - STL list
- 2 points - Second lab program - STL vector
- 2 points - Third lab program - Palindromes
- 1.5 points - Correctly determining if a word is a palindrome
- .5 points - Choosing the best container for the container adaptors
and being able to explain why
- .5 points - Quiz question over the runtime costs for various operations
for each container type listed here.
- +1 point extra credit - Palindrome tester is case insensitive and works
for an entire line of words with spaces.
