You must answer question 1 and then choose four more out of the following six questions.
Each one is worth 20 points. Each answer should be no less than 2 pages long.
1. Iterators and the STL
As we saw, an iterator is a smart pointer that is used to traverse (“iterate”) through a collection like a
vector, deque, list, etc. We also saw that we can create containers of our own and define iterators for
them and give them the required potency.
In the STL iterators are the bridge that connects the containers to the algorithms (see
https://www.youtube.com/watch?v=2olsGf6JIkU for an excellent overview).
Give an overview of the structure of the STL and show how iterators are classified by the types of
operations they provide and how they are used in the STL to connect containers and algorithms.
We used templates when we generalized the Safearray class. But they are much more powerful than
that. See here for a nice introduction to templates and their use.
And then look at the material from
a. List and explain the various kinds of template specialization and what problems they were
introduced to solve.
b. Templates and template specialization are used extensively in metaprogramming. See
Base on the source above, explain the idea of metaprogramming and compile-time calculation,
and how templates and template specialization are used in their implementation. Illustrate this
using as examples: compile-time computation of factorial, (naive) square root calculation and
3. C++ Smart pointers
C++ provides 3 smart pointers. Two of these are the shared_ptr and its companion the weak_ptr. See:
stdweak_ptr/ and https://www.youtube.com/watch?v=xGDLkt-
a. In lecture we saw Meyer’s implementation of shared pointers. However, C++ shared pointers,
while using reference counts, are implemented differently. Explain how C++ implements its
b. Give a (non-trivial) example using the C++ shared_ptr.
c. Are there any situations that the C++ shared pointer can handle that Meyer’s cant? Explain.
d. What is a weak_ptr and what problem with shared pointers was it introduced to solve? Give
an example of the problem, and show how using a weak_ptr solves the problem.
4. Traits and policies
When we looked at how the STL algorithms worked we saw that they make assumptions about
the iterators passed to the algorithms. The in the slist class the type information was embedded
in the class definition. In practice this is not always possible, for example,
an array is a container that does not provide the information required. This where traits come in
the material is found on the class website in the STL material abd in the section on templates.
Explain in detail, using examples, what trait classes are and how they are used.
What are policies, give examples and explain how they are used in C++
5. Cache friendly code
If we are unaware of how our program interacts with underlying hardware, especially memory, we can
write programs that look like they are efficient but really run slowly in practice. Watch the following
video and explain the issues involved in writing efficient, hardware aware code,
We started the semester with an analysis and critique of an ancient String implementation. Strings are
still a very big deal. Watch this video
Explain in detail the problem it addresses and the various approaches to solving it.