Program Notes
You can pass an initializer_list object by value or by reference, as shown by sum() and average(). The object itself is small, typically two pointers (one to the beginning and one past end) or a pointer to the beginning and an integer representing the size, so the choice is not a major performance issue. (The STL passes them by value.)
The function argument can be a list literal, like {2,3,4}, or it can be a list variable, like dl.
The iterator types for initializer_list are const, so you can’t change the values in a list:
*dl.begin() = 2011.6; // not allowed
But, as Listing 16.22 shows, you can attach a list variable to a different list:
dl = {16.0, 25.0, 36.0, 40.0, 64.0}; // allowed
However, the intended use of the initializer_list class is to pass a list of values to a constructor or some other function.
Summary
C++ includes a powerful set of libraries that provide solutions to many common programming problems and the tools to simplify many more problems. The string class provides a convenient means to handle strings as objects as well as automatic memory management and a host of methods and functions for working with strings. For example, these methods and functions allow you to concatenate strings, insert one string into another, reverse a string, search a string for characters or substrings, and perform input and output operations.
Smart pointer templates such as auto_ptr and C++11’s shared_ptr and unique_ptr make it easier to manage memory allocated by new. If you use one of these smart pointers instead of a regular pointer to hold the address returned by new, you don’t have to remember to use the delete operator later. When the smart pointer object expires, its destructor calls the delete operator automatically.
The STL is a collection of container class templates, iterator class templates, function object templates, and algorithm function templates that feature a unified design based on generic programming principles. The algorithms use templates to make them generic in terms of type of stored object and an iterator interface to make them generic in terms of the type of container. Iterators are generalizations of pointers.
The STL uses the term concept to denote a set of requirements. For example, the concept of forward iterators includes the requirements that a forward iterator object can be dereferenced for reading and writing and that it can be incremented. Actual implementations of the concept are said to model the concept. For example, the forward iterator concept could be modeled by an ordinary pointer or by an object designed to navigate a linked list. Concepts based on other concepts are termed refinements. For example, the bidirectional iterator is a refinement of the forward iterator concept.
Container classes, such as vector and set, are models of container concepts, such as containers, sequences, and associative containers. The STL defines several container class templates: vector, deque, list, set, multiset, map, multimap, and bitset. It also defines the adapter class templates queue, priority_queue, and stack; these classes adapt an underlying container class to give it the characteristic interface suggested by the adapter class template name. Thus, stack, although based, by default, on vector, allows insertion and removal only at the top of the stack. C++11 adds forward_list, unordered_set, unordered_multiset, unordered_map, and unordered_multimap.
Some algorithms are expressed as container class methods, but the bulk are expressed as general, nonmember functions. This is made possible by using iterators as the interface between containers and algorithms. One advantage to this approach is that there needs to be just one for_each() or copy() function, and so on, instead of a separate version for each container. A second advantage is that STL algorithms can be used with non-STL containers, such as ordinary arrays, string objects, array objects, and any classes you design consistent with the STL iterator and container idiom.
Both containers and algorithms are characterized by the type of iterator they provide or need. You should check that a container features an iterator concept that supports the algorithm’s needs. For example, the for_each() algorithm uses an input iterator, whose minimal requirements are met by all the STL container class types. But sort() requires random access iterators, which not all container classes support. A container class may offer a specialized method as an option if it doesn’t meet the requirements for a particular algorithm. For example, the list class has a sort() method that is based on bidirectional iterators, so it can use that method instead of the general function.
The STL also provides function objects, or functors, that are classes for which the () operator is overloaded—that is, for which the operator()() method is defined. Objects of such classes can be invoked by using function notation but can carry additional information. Adaptable functors, for example, have typedef statements that identify the argument types and the return value type for the functor. This information can be used by other components, such as function adapters.
By representing common container types and providing a variety of common operations implemented with efficient algorithms, all done in a generic manner, the STL provides an excellent source of reusable code. You may be able to solve a programming problem directly with the STL tools, or you may be able to use them as building blocks to construct the solution you need.
The complex and valarray template classes support numeric operations for complex numbers and arrays.
Chapter Review
1. Consider the following class declaration:
class RQ1
{
private:
char * st; // points to C-style string
public:
RQ1() { st = new char [1]; strcpy(st,""); }
RQ1(const char * s)
{st = new char [strlen(s) + 1]; strcpy(st, s); }
RQ1(const RQ1 & rq)
{st = new char [strlen(rq.st) + 1]; strcpy(st, rq.st); }
~RQ1() {delete [] st};
RQ & operator=(const RQ & rq);
// more stuff
};
Convert this to a declaration that uses a string object instead. What methods no longer need explicit definitions?
2. Name at least two advantages string objects have over C-style strings in terms of ease-of-use.
3. Write a function that takes a reference to a string object as an argument and that converts the string object to all uppercase.
4. Which of the following are not examples of correct usage (conceptually or syntactically) of auto_ptr? (Assume that the needed header files have been included.)
auto_ptr<int> pia(new int[20]);
auto_ptr<string> (new string);
int rigue = 7;
auto_ptr<int>pr(&rigue);
auto_ptr dbl (new double);
5. If you could make the mechanical equivalent of a stack that held golf clubs instead of numbers, why would it (conceptually) be a bad golf bag?
6. Why would a set container be a poor choice for storing a hole-by-hole record of your golf scores?
7. Because a pointer is an iterator, why didn’t the STL designers simply use pointers instead of iterators?
8. Why didn’t the STL designers simply define a base iterator class, use inheritance to derive classes for the other iterator types, and express the algorithms in terms of those iterator classes?
9. Give at least three examples of convenience advantages that a vector object has over an ordinary array.
10. If Listing 16.9 were implemented with list instead of vector, what parts of the program would become invalid? Could the invalid part be fixed easily? If so, how?
11. Consider the TooBig functor in Listing 16.15. What does the following code do, and what values get assigned to bo?
bool bo = TooBig<int>(10)(15);
Programming Exercises
1. A palindrome is a string that is the same backward as it is forward. For example, “tot” and “otto” are rather short palindromes. Write a program that lets a user enter a string and that passes to a bool function a reference to the string. The function should return true if the string is a palindrome and false otherwise. At this point, don’t worry about complications such as capitalization, spaces, and punctuation. That is, this simple version should reject “Otto” and “Madam, I’m Adam.” Feel free to scan the list of string methods in Appendix F for methods to simplify the task.
2. Do the same problem as given in Programming Exercise 1 but do worry about complications such as capitalization, spaces, and punctuation. That is, “Madam, I’m Adam” should test as a palindrome. For example, the testing function could reduce the string to “madamimadam” and then test whether the reverse is the same. Don’t forget the useful cctype library. You might find an STL function or two useful although not necessary.
3. Redo Listing 16.3 so that it gets it words from a file. One approach is to use a vector<string> object instead of an array of string. Then you can use push_back() to copy how ever many words are in your data file into the vector<string> object and use the size() member to determine the length of the word list. Because the program should read one word at a time from the file, you should use the >> operator rather than getline(). The file itself should contain words separated by spaces, tabs, or new lines.
4. Write a function with an old-style interface that has this prototype:
int reduce(long ar[], int n);
The actual arguments should be the name of an array and the number of elements in the array. The function should sort an array, remove duplicate values, and return a value equal to the number of elements in the reduced array. Write the function using STL functions. (If you decide to use the general unique() function, note that it returns the end of the resulting range.) Test the function in a short program.
5. Do the same problem as described in Programming Exercise 4, except make it a template function:
template <class T>
int reduce(T ar[], int n);
Test the function in a short program, using both a long instantiation and a string instantiation.
6. Redo the example shown in Listing 12.12, using the STL queue template class instead of the Queue class described in Chapter 12.
7. A common game is the lottery card. The card has numbered spots of which a certain number are selected at random. Write a Lotto() function that takes two arguments. The first should be the number of spots on a lottery card, and the second should be the number of spots selected at random. The function should return a vector<int> object that contains, in sorted order, the numbers selected at random. For example, you could use the function as follows:
vector<int> winners;
winners = Lotto(51,6);
This would assign to winners a vector that contains six numbers selected randomly from the range 1 through 51. Note that simply using rand() doesn’t quite do the job because it may produce duplicate values. Suggestion: Have the function create a vector that contains all the possible values, use random_shuffle(), and then use the beginning of the shuffled vector to obtain the values. Also write a short program that lets you test the function.
8. Mat and Pat want to invite their friends to a party. They ask you to write a program that does the following:
• Allows Mat to enter a list of his friends’ names. The names are stored in a container and then displayed in sorted order.
• Allows Pat to enter a list of her friends’ names. The names are stored in a second container and then displayed in sorted order.
• Creates a third container that merges the two lists, eliminates duplicates, and displays the contents of this container.
9. Compared to an array, a linked list features easier addition and removal of elements but is slower to sort. This raises a possibility: Perhaps it might be faster to copy a list to an array, sort the array, and copy the sorted result back to the list than to simply use the list algorithm for sorting. (But it also could use more memory.) Test the speed hypothesis with the following approach:
a. Create a large vector<int> object vi0, using rand() to provide initial values.
b. Create a second vector<int> object vi and a list<int> object li of the same size as the original and initialize them to values in the original vector.
c. Time how long the program takes to sort vi using the STL sort() algorithm, then time how long it takes to sort li using the list sort() method.
d. Reset li to the unsorted contents of vi0. Time the combined operation of copying li to vi, sorting vi, and copying the result back to li.
To time these operations, you can use clock() from the ctime library. As in Listing 5.14, you can use this statement to start the first timing:
clock_t start = clock();
Then use the following at the end of the operation to get the elapsed time:
clock_t end = clock();
cout << (double)(end - start)/CLOCKS_PER_SEC;
This is by no means a definitive test because the results will depend on a variety of factors, including available memory, whether multiprocessing is going on, and the size of the array or list. (One would expect the relative efficiency advantage of the array over the list to increase with the number of elements being sorted.) Also if you have a choice between a default build and a release build, use the release build for the measurement. With today’s speedy computers, you probably will need to use as large an array as possible to get meaningful readings. You might try, for example, 100,000 elements, 1,000,000 elements, and 10,000,000 elements.
10. Modify Listing 16.9 (vect3.cpp) as follows:
a. Add a price member to the Review structure.
b. Instead of using a vector of Review objects to hold the input, use a vector of shared_ptr<Review> objects. Remember that a shared_ptr has to be initialized with a pointer returned by new.
c. Follow the input stage with a loop that allows the user the following options for displaying books: in original order, in alphabetical order, in order of increasing ratings, in order of decreasing ratings, in order of increasing price, in order of decreasing price, and quitting.
Here’s one possible approach. After getting the initial input, create another vector of shared_ptrs initialized to the original array. Define an operator<() function that compares pointed-to structures and use it to sort the second vector so that the shared_ptrs are in the order of the book names stored in the pointed-to objects. Repeat the process to get vectors of shared_ptrs sorted by rating and by price. Note that rbegin() and rend() save you the trouble of also creating vectors of reversed order.