Answers to Self-Test Exercises

1. 1. v.begin() returns an iterator located at the first element of v. v.end() returns a value that serves as a sentinel value at the end of all the elements of v.

2. 2. *p is the dereferencing operator applied to p. *p is a reference to the element at location p.

3. 3.

   vector<int>::iterator p;
   for (p = v.begin(), p++; p != v.end(); p++)
       cout << *p << " ";

4. 4.D C C

5. 5.B C

6. 6. Either would work.

7. 7. A major difference is that a vector container has random access iterators whereas a list has only bidirectional iterators.

8. 8. All except slist.

9. 9. vector and deque.

10. 10. They all can have mutable iterators.

11. 11. The stack template adapter class has no iterators.

12. 12. The queue template adapter class has no iterators.

13. 13. No value is returned; pop is a void function.

14. 14. mymap will contain two entries. One is a mapping from 5 to "c++" and the other is a mapping from 4 to the default string, which is blank.

15. 15. Yes they can be of any type, although there is only one type for each set object. The type parameter in the template class is the type of elements stored.

16. 16. If 'A' is in s, then s.find('A') returns an iterator located at the element 'A'. If 'A' is not in s, then s.find('A') returns s.end().

17. 17. Just note that aN + b ≤ (a + b)N, as long as 1 ≤ N.

18. 18. This is mathematics, not C++, so = will mean equals not assignment.

    First note that log_a N = (log_a b)(log_b N).

    To see this first identity, just note that if you raise a to the power log_a N, you get N, and if you raise a to the power (log_a b)(log_b N), you also get N.

    If you set c = (log_a b), you get log_a N = c(log_b N).

19. 19. The programs should run exactly the same.

20. 20.

    #include <iostream>
    #include <vector>
    #include <algorithm>
    using std::cout;
    using std::vector;
    using std::search;
    …
    vector<int> target;
    target.push_back(42);
    target.push_back(43);
    vector<int>::const_iterator result = search(v.begin(), v.end(),
                            target.begin(), target.end());
    if (result != v.end())
        cout << "Found 42, 43.\n";
    else     cout << "42, 43 not there.\n";

21. 21. No, you must have random access iterators, and the list template class has only bidirectional iterators.

22. 22. Yes, a random access iterator is also a forward iterator.

23. 23. The set_union template function requires that the containers keep their elements in sorted order to allow the function template to be implemented in a more efficient way.