582484 Algorithm Libraries
- wed 25.1.2006 10-12 | B119
- wed 25.1.2006 16-18 | B119
- Implement an iterator that iterates over a sequence that contains
all values of int in increasing order. This sequence does not
actually exist but the iterator behaves as it was there. An iterator
is iniatialized by giving the value it points to as an argument to the
constructor. For example, the sequence [-1,0,1,2] would be represent
as an iterator range with
[int_range_iterator(-1),int_range_iterator(3)). Implement enough
functionality to make it work with the find algorithm from the
lectures. Write a small test program to verify this.
- Write a class smooth_iterator that iterates over an array of
floats. The dereference operator (operator*) returns
the average of the pointed to value and its two immediate neighbours.
For the first and the last position, the average is over two
instead of over three. For example, [1.0,5.0,3.0,1.0] would turn
into [3.0,3.0,3.0,2.0] when seen through the smooth_iterator.
Implement enough functionality to make it work with the find
algorithm from the lectures.
- In the find algorithm given on the lectures, the type of third
argument is a template parameter T that is independent of the input
sequence. It could be of different type than the elements of the
- What happens if T is different? Describe the different
possibilities and give examples. Test the examples in actual
- The value type of the sequence (the type of the elements) can
be determined at compile time using iterator traits.
Then we could have the true value type as the
type of the third argument. Discuss the advantages and
disadvantages of this alternative
to the current one.
- Implement an algorithm count_equal that compares two
sequences and counts how many times they have an equal value in the
same position. For example, given the sequences [1,2,3,4] and
[2,2,3,3], the algorithm would return 2 (the middle two
positions). The algorithm should be as generic as possible.
- The algorithm takes two sequences as an input.
If each sequence is represented by a pair of iterators,
the algorithm has four arguments. Instead, the second
sequence could be represented by just the begin iterator.
The end is implicit if we assume that the two sequences
have the same length. Discuss the advantages and
disadvantages of the two alternatives.