Problem 0: Review old programming assignments, lectures, and readings. Use Piazza to suggest a question you feel is missing from this collection of practice problems.

Problem : Write a program called RouteDistance that reads a database of airport locations from a file specified on the command line and then calculates the total length of a route given on the command line. For example,

./RouteDistance -f airports.txt BWI AUS DSM SEA HAN DEL SVO LHR BWI

Solution: route_distance.cpp

Problem : Write the header and implementation of a Poll class Poll has the following public methods and constructor:

• Poll(int n) which creates a poll with $n$ option, each with a vote count initialized to 0;
• void addVote(int opt), which adds one vote for the given option in the given poll, or does nothing if the option is invalid (not in the range $0, \ldots n-1$ where $n$ was the value given when the poll was created);
• int getLeader(), which returns the index of the option currently with the most votes, with ties broken in favor of lower index; and
• Poll merge(Poll other), which, as long as the this poll and the other one have the same number of options, creates a new poll where each option's vote total is the sum of its totals in the two polls.

Problem : Add the appropriate const qualifiers to the methods and their parameters in Poll.

Problem : Overload the << operator to output the current vote counts in a Poll in a format like [1, 2, 3, 4].

Problem : Overload the += and + operators so that, for Polls p1 and p2 and an int i, p1 += i has the same effect as p.addVote(i) and p1 + p2 has the same effect as p1.merge(p2).

Problem : Write Poll so it uses a dynamically allocated array and write the copy constructor, move constructor, assignment operator, move assignment operator, and destructor.

Solution: poll.h poll.cpp

Problem : The NIVector class is a simple non-invalidating vector – if you get a reference to an element using at then that reference is never invalidated no matter how many elements you add to the vector. It accomplishes this by maintaining a vector of chunks of data where each chunk is a vector of a fixed size. When a chunk is full it simply adds a new chunk. Change NIVector so it is a template. What is the implicit interface that the element type must implement?

Code: nivector.h nivector.cpp nivector_test.cpp

Problem : Add a (non-const) iterator to NIVector. The iterator can be an object that contains a reference to the vector it is iterating through and the current index in that vector. Implement the *, !=, and ++ operators for your iterator and add begin and end to NIVector.

Solution: nivector.h nivector.cpp nivector_test.cpp

Problem : Add a template function fold_l to CIVector. The fold_l method takes two iterators i and j, an initial value z, and a function f that takes something of the same type as the initial value, something of the same type as the vector elements, and returns something of the same type as the initial value and returns f(...f(f(f(z, *i), *(i + 1)), *(i + 2)), ..., *(j-1)). Make your template work with with both functions, function objects, and lambdas. For example, if vec is a vector of ints, and add returns the sum of its two int parameters, then

fold_l(vec.begin(), vec.end(), 0, add)

fold_l(vec.begin(), vec.end(), 0, [] (int x, int y) { return x + y; })

Problem : Show how to use fold_l to compute the concatenation of all the strings in a vector of strings.

Solution: foldl.cpp