SequenceView - a utility to advance(STL)
In the C++ standard library, a sequence is defined by a start iterator and an end iterator that "points behind the last element". Algorithms terminate when the traversing iterator equals the end iterator. In SequenceView a sequence is instead defined by a "view" that contains a start iterator and an end predicate. Such an end predicate is a weaker and consequently more general end condition than comparing two iterators.
Views
A minimal view has three member functions:
class MyMinimalView
{
// ...
public:
iterator current();
void increment();
bool done() const;
};
The current() member function returns the current
position of the view. The increment() function is
analogous to an iterator's operator++(), and
done() tells whether the end of the sequence has been
reached. With this view we could implement a for_each()
algorithm as:
template<class View, class Function>
Function
for_each(View view,
Function f)
{
while (!view.done())
{
f(*view.current());
view.increment();
}
return f;
}
The done() function is the main difference from how the
STL represents sequences. There are very few restrictions on how
done() must be implemented. We could for example make it
return true only if *current() is greater than some
value. Alternatively, we could make it return true only
current() equals another iterator. In that case it would
be equivalent to the two-iterator sequence representation. Here's
what it might look like:
class TwoIteratorView
{
// ...
public:
TwoIteratorView(iterator in_first,
iterator in_last)
:
m_current(in_first)
m_last(in_last)
{
}
bool
done() const
{
return current() == m_last;
}
// ...
private:
iterator m_current;
iterator m_last;
};
Dereferencers
In the example above we obtained the view's current value as*current(). The assumption that *current()
is the value we want is not always flexible enough. One way to
increase flexibility would be to require that views have a special
member function that returned the value. The loop in the
for_each() algorithm would then be:
template<class View, class Function>
Function
for_each(View view,
Function f)
{
while (!view.done())
{
f(view.value());
view.increment();
}
return f;
}
The approach would work, but risks bloating views with dereferencing
code. Another solution is to separate dereferencing into another
object, a "dereferencer". Our for_each() would become:
template<class View, class Dereferencer, class Function>
Function
for_each(View view,
Dereferencer dereferencer,
Function f)
{
while (!view.done())
{
f(dereferencer.dereference(view));
view.increment();
}
return f;
}
With this approach we obtain a good separation between traversal and
the values we operate on. How the dereferencer obtains the value from
the view is of no concern to the algorithm. The dereferencer may for
instance multiply the value of *current() by 2, it may
require that the view have a member function called value(), it may
return the average of several values around current(), or
it may even return a higher order view.
However, a separate dereferencer as implemented here puts an intolerable burden on the users of the algorithm. We simply cannot require that the users provide a whole extra class unless they need the extra functionality. That's why SequenceView introduces the concept of a "materializer".
Materializers
A materializer is basically a class that contains both a view and a dereferencer. This may sound like we're adding even more complex machinery, but it will actually make it easier to use algorithms.
SequenceView provides utilities to write algorithms that work on both views and materializers. If the algorithm is called with a view, it will use a default dereferencer. If the algorithm is called with a materializer, it will extract the view and the dereferencer from the materializer. The
for_each() function we would write
with SequenceView is:
template<class Seq, class Function>
inline
Function
for_each(Seq seq, // seq is either a view or a materializer.
Function function)
{
typename SeqInfo<Seq>::View& view = SeqInfo<Seq>::view(seq);
typename SeqInfo<Seq>::Dereferencer& dereferencer = SeqInfo<Seq>::dereferencer(seq);
while (!view.done())
{
function(dereferencer.dereference(view));
view.increment();
}
return function;
}
and we could call the function in both the following ways:
for_each(myView,
f);
for_each(Materializer(myView,
myDereferencer),
f);
In the last call, Materializer is a utility function that creates a
materializer from a view and a dereferencer.
Using the C++ standard library algorithms
SequenceView provides a view/materializer based interface to the C++ standard library algorithms so that it's not necessary to rewrite the whole library. SequenceView also provides utility functions to ease the interaction with the standard library. For example we could callfor_each() on a vector with:
// Get the utility function SequenceView::View().
#include <sequenceview/ViewCalls.hh>
// ...
using namespace SequenceView;
std::vector<int> myVector(10, 1);
// Wave those pesky iterators goodbye...
for_each(View(myVector),
f);
This code is as efficient as if you used two iterators. But in other
cases, using views with the standard library may incur a small
performance penalty compared to what you would get if you wrote the
algorithm specially for views. The penalty is typically a comparison
of two bools per iteration.
Examples of use
Here's an overview over the examples that are included in the package:- CustomFunctionExample illustrates how to write your own algorithms that work on views.
- TimeExample features a sequence that terminates after a given time has elapsed.
- StdFunctionExample illustrates how to use standard C++ library functions with views.
- BubbleSortExample uses
for_each()to perform a bubble sort. This is an example of higher order views. - GoFExample illustrates how a GoF style iterator running over a C style linked list can be used with the C++ standard library.
- WindowExample features a higher order view that uses an average of two-dimensional data as its value.
- SystematicExample provides systematic tests of views, dereferencers and materializers.