29. There was a baby boom, resulting in a 10% population increase in every town. Update your town data using transform( ), rewrite your data back out to file.
30. Find the towns with the highest and lowest population. Temporarily implement operator< for your town object for this exercise. Also try implementing a function that returns true if its first parameter is less than its second. Use it as a predicate to call the algorithm you use.
31. Find all the towns within the altitudes 2500-3500 feet inclusive. Implement equality operators for the Town class as needed.
32. We need to place an airport in a certain altitude, but location is not a problem. Organize your list of towns so that there are no duplicate (duplicate meaning that no two altitudes are within the same 100 ft range. Such classes would include [100, 199), [200, 199), etc. altitudes. Sort this list in ascending order in at least two different ways using the function objects in <functional>. Do the same for descending order. Implement relational operators for Town as needed.
33. Generate an arbitrary number of random numbers in a stack-based array. Use max_element( ) to find the largest number in array. Swap it with the number at the end of your array. Find the next largest number and place it in the array in the position before the previous number. Continue doing this until all elements have been moved. When the algorithm is complete, you will have a sorted array. (This is a "selection sort".)
34. Write a program that will take phone numbers from a file (that also contains names and other suitable information) and change the numbers that begin with 222 to 863. Be sure to save the old numbers. The file format is be as follows:
222 8945
756 3920
222 8432
etc.
35. Write a program that given a last name will find everyone with that last name with his or her corresponding phone number. Use the algorithms that deal with ranges (lower_bound, upper_bound, equal_range, etc.). Sort with the last name acting as a primary key and the first name acting as a secondary key. Assume that you will read the names and numbers from a file where the format will be as follows. (Be sure to order them so that the last names are ordered, and the first names are ordered within the last names.):
John Doe 345 9483
Nick Bonham 349 2930
Jane Doe 283 2819
36. Given a file with data similar to the following, pull all the state acronyms from the file and put them in a separate file. (Note that you can’t depend on the line number for the type of data. The data is on random lines.)
ALABAMA
AL
AK
ALASKA
ARIZONA
AZ
ARKANSAS
AR
CA
CALIFORNIA
CO
COLORADO
etc.
When complete, you should have a file with all the state acronyms which are:
AL AK AZ AR CA CO CT DE FL GA HI ID IL IN IA KS KY LA ME MD MA MI MN MS MO MT NE NV NH NJ NM NY NC ND OH OK OR PA RI SC SD TN TX UT VT VA WA WV WI WY
37. Make an Employee class with two data members: hours and hourlyPay. Employee shall also have a calcSalary( ) function which returns the pay for that employee. Generate random hourly pay and hours for an arbitrary amount of employees. Keep a vector<Employee*>. Find out how much money the company is going to spend for this pay period.
38. Race sort( ), partial_sort( ), and nth_element( ) against each other and find out if it’s really worth the time saved to use one of the weaker sorts if they’re all that’s needed.
7: Generic containers
Container classes are the solution to a specific kind of code reuse problem. They are building blocks used to create object-oriented programs—they make the internals of a program much easier to construct.
A container class describes an object that holds other objects. Container classes are so important that they were considered fundamental to early object-oriented languages. In Smalltalk, for example, programmers think of the language as the program translator together with the class library, and a critical part of that library is the container classes. So it became natural that C++ compiler vendors also include a container class library. You’ll note that the vector was so useful that it was introduced in its simplest form early in Volume 1 of this book.
Like many other early C++ libraries, early container class libraries followed Smalltalk’s object-based hierarchy, which worked well for Smalltalk, but turned out to be awkward and difficult to use in C++. Another approach was required.
The C++ approach to containers is based, of course, on templates. The containers in the standard C++ library represent a broad range of data structures designed to work well with the standard algorithms and to meet common software development needs.
Containers and iterators
If you don’t know how many objects you’re going to need to solve a particular problem, or how long they will last, you also don’t know ahead of time how to store those objects. How can you know how much space to create? You don’t until run time.
The solution to most problems in object-oriented design seems simple: you create another type of object. For the storage problem, the new type of object holds other objects or pointers to objects. This new type of object, which is typically referred to in C++ as a container (also called a collection in some languages), expands itself whenever necessary to accommodate everything you place inside it. You don’t need to know ahead of time how many objects you’re going to place in a container; you just create a container object and let it take care of the details.
Fortunately, a good object-oriented programming language comes with a set of containers. In C++, it’s the Standard Template Library. In some libraries, a generic container is considered good enough for all needs, and in others (C++ in particular) the library has different types of containers for different needs: a vector for consistent access to all elements, and a linked list for consistent insertion at all positions, and many more, so you can choose the particular type that fits your needs.
All containers have some way to put things in and get things out. The way you place something into a container is fairly obvious. There’s a function called "push" or "add" or a similar name. Fetching things out of a container is not always as apparent; if an entity is array-like, such as a vector, you might be able to use an indexing operator or function. But in many situations this doesn’t make sense. Also, a single-selection function is restrictive. What if you want to manipulate or compare a group of elements in the container?.