pre-lab Videos
Here are links to the videos. The quality is poor but I think they are still instructional. Please let me know if you need more help. Part one Part two
Standard Template Library (STL)
The C++ Standard Template Library (STL) provides several container classes. A container is an object that holds other objects (or variables of fundamental types). A list of containers provided in the STL can be found here. Knowing which container class to use is an important skill. Choosing the right container can greatly simplify your code.
For each container covered in this lab, I have provided links to its web page. Make sure you go through each container's public member functions to get a feel for each container. Focus on the following: How to create the container: look at each containers constructors, it's okay if you don't understand all of it. The example code should give you enough to use the container. How to insert element(s) into the container. How to remove element(s) from the container.
vector
A vector is essentially an array that grows dynamically to make room for new elements.
The elements in a vector can be accessed just like an array. It also stores its size.
To use the vector class, you need to include <vector> and use the
std namespace. A container can only contain variables of a single type.
To create a vector of integers called vec we use the following line of
code.
vector<int> vec;
To cerate a vector of strings we use.
vector<string> vec;
In general, to create a vector of elements of type T, we use.
vector<T> vec;
The following classes are created analogously to the vector class. Just change
the name vector to the appropriate class. i.e. Include the appropriate calls and
use the std namespace.
Vectors are ideal when you need random (non-sequential) access to the elements.
Adding an element (push_back) to the end of vector is also efficient.
Adding an element to any other position is less efficient because it involves shifting
elements of the vector.
Exercise
Write a program that reads the contents of a text file as strings. It should then print
the content of the file as a table with two columns. The first column should be the first
half of all strings in the file. If the number of strings is odd, the first column should
have one more string than the second column.
Using a vector (push_back), you don't need to know the
number of elements in the file or manage the memory. As long as you don't run out of
memory, the vector class handles the memory allocation.
What is the difference between the [] operator and the at function?
stack
A stack is a container where elements are removed (pop) in the opposite
order in which they were inserted (push) i.e. the last element inserted is
the first element removed. Stacks are ideal when you need
to reverse the order of items or operations. In fact, we can uses a stack to transform
recursive code to iterative code. Logically, a stack has a single end where elements
are inserted and removed.
Exercise
Write a program that reads a text file, then it prints all the characters in the file in the reverse order. Isn't it nice to not worry about memory, unlike with arrays? Also notice that we aren't explicitly using dynamic memory. All that is handled under the hood by the container classes. Later we will see how this is done. Using professionally designed classes should help you design class that are also easy to use.
queue
A queue is a container where elements are removed (pop) in the order in
which they were inserted (push) i.e. The first element inserted is the
first element removed. Queues are ideal when you want to preserve
the order in which elements are added. Logically, a queue has two ends, one for insertion
the other for deletion.
list
A list is container that can handle insertion and deletion at any position efficiently, provided we have a "pointer" to that position. This is unlike vectors for which these operations are inefficient. To add an element to the middle of a vector requires moving half of the elements of the vector. Lists can also be more space efficient than vector, in a vector it is possible to have about half of its space unused. With a list, you don't get random access, you have to go through elements sequentially. The first element of a list is called the head of the list, the last element is the tail.
set
A set is a container that doesn't allow for duplicates. They are ideal when you only need information on the presence of an object rather than the number of times it occurs. You can use a set to easily count the number of distinct words in a file.
Exercise
Create the function num_distinct_chars(string). The function should take a string
and return the number of distinct characters in the string. Use a set to implement this function.
Imagine if you didn't use a set, how much more complicated do you think the function would be?
Make as second version of the function that doesn't use a set.
map
Like the set container, a map is named after its mathematical equivalent. A map is a container that contains key-value pairs. Every key is associated with a unique value. For example, a map that maps characters to integers is declared by the following line.
map<char, int> my_map;
my_map['a'] = 5;
my_map['x'] = 24;
my_map has size two with the key-value pairs ('a', 5) and ('x', 24). Given a key k and a map M,
we access the value associated with k by M[k] . A map can be thought of as a generalization
of an array. An array uses only nonnegative integers to index its content, but a map can use any type that is comparable
(i.e. any type we can compare with the less than operator). When accessing the value of a key that isn't present in the map, the value
returned is default value of the type of the mapped values. For example, In the code above, the value type is int, so it's default
value is 0. This means that my_map['z'] would return 0, this is because 'z' wasn't in my_map.
After the execution of my_map['z'], the pair ('z', 0) will now be in my_map.
Exercise
Write a program that takes a text file with only English words. Your program should output each word in the file
followed by the number of times each word occurs. Your program should be case insensitive. Use a map with keys of type string
and values of type int.
Test your program on the following poem (Lord Randall by Martin Carthy).
Where have ye been all the day my own dear darling boy Where have ye been all the day my own dear comfort and joy I have been to my stepmother make my bed mummy do Make my bed mummy do What did she give you for your supper I got fish and I got broth Where did she get the fish that she give you Hedges sought and ditches caught What did you do with your fish bones I gave them to my greyhound Tell me what did your greyhound do There he swelled and there he died I fear that she does you deadly wrong She took me in but she did me slay What will you leave to your mother I will leave you me house and land What will you leave your stepmother my own dear darling boy What will you leave your stepmother my own dear comfort and joy Bind her with rope and there let her hang with the halter that hangs on the tree For poisoning of me
Create another version that counts the number of times each letter is used. It should also be case insensitive.