582484 Algorithm Libraries

Exercise 2

• wed 1.2.2006 10-12 | B119
• wed 1.2.2006 16-18 | B119

1. Turn int_range_iterator from last week's exercises into fully STL compatible random access iterator. See, SGI STL documentation or the standard for details.

2. The adjacent_find algorithm given on the lectures (and the one in STL) requires forward iterators, because it violates the single-pass property of input iterators.

   1. Write a version that works for input iterators by storing values into a local variable temporarily.
   2. The new algorithm is more generic in the sense that it works with input iterators and can be applied to, for example, input streams. At the same time, it is less generic in other ways. Which ways?

3. Write an algorithm that reverses the order of words in a text (but the words themselves are not reversed). A word is any string (even empty one) between space characters. The signature is

   template <class BidirectionalIterator, class T,
             class OutputIterator>
   void
   reverse_word_order(BidirectionalIterator begin, BidirectionalIterator end,
                      OutputIterator result, const T& separator);
   

   The separator is a generalization of the space character. For example:

   string str("Are these   words?");
   reverse_word_order(str.begin(), str.end(),
                      ostream_iterator<char>(cout, ""), ' ');
   // outputs "words?   these Are"
   

   Use find and copy algorithms, and the reverse_iterator adaptor as tools in your implementation.

4. Write an algorithm mid_point that gets an iterator range as an argument and returns an iterator to the middle of the range. To be precise, given [begin,end) it returns mid such that [begin,mid) has the same size or is one smaller than [mid,end). The algorithm should work with forward, bidirectional and random access iterators. For random access iterators, it should execute in constant time.

5. Study the topic of your programming project and ask questions.