Haskell, for example, has List Comprehension syntax which allows for expressing the above set as:
[x^2 | x <- [0..], x > 5]
C# supports LINQ, which borrows SQL notation to express the same idea. C++ does not have syntactic support for expressing set-builder notation but numerous attempts by library authors have tried to fill the gap. Take a look at this StackOverflow thread for links to projects emulating LINQ in C++. Others have noted that Boost.Range can already be used for this task. The following code expresses the aforementioned set (at least for a subset of natural numbers):
using namespace boost;
auto sq = counting_range(0, 1000)
| filtered([](int x) { return x > 5; })
| transformed([](int x) { return x*x; });
There is one place though, where Boost.Range approach falls short. Set-builder notation can be used with more than one variable:
In this case, a Cartesian product of the sets is taken and the elements of that product are "filtered" and "transformed". The Range library, however, does not provide a way to generate the Cartesian product. So let's look at what it would take to offer such functionality. This will give us a chance to not only experiment with Boost.Range but also play around with variadic templates.
Since we'll be making ample use of C++11's variadic templates, it's important to understand them. If you need a good primer, the best thing is to watch Andrei's Alexandrescu's Variadic Templates are Funadic (or at least the first 30 mins of it).
The Goal
Let's begin by looking at what we are after:std::vector<int> xx = { 1, 2, 3 };
std::vector<char> yy = { 'a', 'b', 'c' };
std::vector<double> zz = { 0.1, 0.2, 0.3 };
auto r = cartesian(xx, yy, zz)
| xfiltered([](int x, char y, double z) { return x > 1 && y < 'c'; })
| xtransformed([](int x, char y, double z) { return x + int(y) + z; });
cartesian() function takes any number of ranges and returns a range of std::tuple's. In the example above, cartesian(xx, yy, zz) returns a range of std::tuple<int&, char&, double&> and will have nine elements: (1, 'a', 0.1), (1, 'a', 0.2), (1, 'a', 0.3), (1, 'b', 0.1), and so on. xfiltered() and xtransformed() are analogous to filtered() and transformed() except that they allow the lambda to accept multiple arguments instead of a single tuple. Without them, the code would look like this:
auto r = cartesian(xx, yy, zz)
| filtered([](std::tuple<int&, char&, double&> x) { return std::get<0>(x) > 1 && std::get<1>(x) < 'c'; })
| transformed([](std::tuple<int&, char&, double&> x) { return std::get<0>(x) + int(std::get<1>(x)) + std::get<2>(x); });
Boost Ranges
Boost Ranges aim to raise the level of abstraction when dealing with sequences by providing a single object representing an interval. However, unlike ranges proposed by Alexandrescu in Iterators Must Go keynote, Boost Ranges are a leaky abstraction. They leak the underlying iterators by requiring the range to expose them via boost::begin(rng) and boost::end(rng). This requirement will force us to define a cartesian_iterator and demonstrate the downside of the leak. The principal advantage of leaking the iterators though is the ability to inter-operate with existing algorithms designed to work with iterators.
Getting Started
Before getting into the details of the cartesian_iterator that will do all of the heavy-lifting, let's look at the big picture:using namespace boost;
// To be filled in later
template <typename... Rs>
class cartesian_iterator;
// Boost.Range provides iterator_range class which constructs a range
// from a begin and end iterator pair
template <typename... Rs>
using cartesian_range = iterator_range<cartesian_iterator<Rs...>>;
// Our "public" function that takes any number of ranges and
// constructs a cartesian_range
template <typename... Rs>
typename cartesian_range<Rs...>::type cartesian(Rs&... rs) {
typedef cartesian_iterator<Rs...> iter_t;
return cartesian_range<Rs...>(iter_t(rs...), iter_t(rs..., 0));
}
The first step in defining the cartesian_iterator is to decide what will be its value_type. As I mentioned above, it will be the std::tuple of references to the types of the ranges. The code below defines a meta-function to extract the reference type of a range and then uses it to define the value_type of cartesian_iterator:
template <typename R>
struct range_reference {
typedef typename boost::range_iterator<R>::type iter;
typedef typename iter::reference type;
};
template <typename... Rs>
struct value_type {
typedef std::tuple<
typename range_reference<Rs>::type...
> type;
};
To ease the task of writing an iterator, we'll be using Boost.Iterators, in particular iterator_facade class. We just have to derive from it and implement 3 functions. Here's what the derivation looks like:
template <typename... Rs> class cartesian_iterator : public boost::iterator_facade< cartesian_iterator<Rs...>, // pass self per CRTP typename value_type<Rs...>::type, // value_type boost::forward_traversal_tag, // iterator category typename value_type<Rs...>::type // reference -- same as value_type! >
Note that the reference type will be std::tuple<...> and not std::tuple<...>&. The reason being is that when dereferencing, we'll return a temporary std::tuple<...> since the cartesian_range is not stored in memory per se. Obviously, returning a temporary from a function with a reference return type is a bad idea.
Next stop -- deciding what data members will be needed in the iterator. Consider what happens when asked to generate a cartesian_range over two ranges -- {1, 2} and {'a', 'b'}. We are going to use two iterators, one pointing into each sequence and emulating a nested for-loop. On each iteration we advance the iterator over the {'a', 'b'}. Once the iterator advances past 'b', we reset it back to the beginning to point to 'a' again and advance the iterator over {1, 2}.
The analysis leads us to conclude that we will (a) need a tuple of iterators into the underlying ranges and (b) a tuple of references to the underlying ranges for resetting the iterators back to the beginning and comparing with the range ends. This demonstrates a weakness of Boost Ranges: our iterator is forced to keep references to the underlying ranges. Since the cartesian_range has two iterators (begin and end), this approach wastes memory. If the a range was a primitive (as in Alexandrescu's ranges), we could save on the extra references. Back to the code -- data members, constructors and equality check:
The analysis leads us to conclude that we will (a) need a tuple of iterators into the underlying ranges and (b) a tuple of references to the underlying ranges for resetting the iterators back to the beginning and comparing with the range ends. This demonstrates a weakness of Boost Ranges: our iterator is forced to keep references to the underlying ranges. Since the cartesian_range has two iterators (begin and end), this approach wastes memory. If the a range was a primitive (as in Alexandrescu's ranges), we could save on the extra references. Back to the code -- data members, constructors and equality check:
std::tuple<typename boost::range_iterator<Rs>::type... > iters;
std::tuple<Rs&...> ranges;
cartesian_iterator() {}
// used to construct the begin iterator
cartesian_iterator(Rs&... rs) :
ranges(rs...), iters(boost::begin(rs)...) {}
// used to construct the end iterator
cartesian_iterator(Rs&... rs, int) :
ranges(rs...), iters(boost::end(rs)...) {}
// called by iterator_facade's impl of oprerator==
bool equal(cartesian_iterator const& other ) const {
return iters == other.iters;
}
With the easy parts are out of the way, let's tackle the iterator's increment functionality. Remember, we need to simulate the nested for loops but in a functional manner:
template <size_t N>
using const_int = std::integral_constant<size_t, N>;
// called by iterator_facade's impl of operator++
void increment() {
increment(const_int<sizeof...(Rs) - 1>());
}
// helpers
template <size_t N>
bool increment(const_int<N>) {
if( ++(std::get<N>(iters)) == boost::end(std::get<N>(ranges)) ) {
if( !increment(const_int<N-1>()) )
return false;
std::get<N>(iters) = boost::begin(std::get<N>(ranges));
}
return true;
}
// base case
bool increment(const_int<0>) {
return ++(std::get<0>(iters)) != boost::end(std::get<0>(ranges));
}
For any given iterator (starting with the last one), we increment it and if it reached the end, we recursively call ourselves to increment the previous iterator. If we are not at the very end, we reset the given iterator back to the beginning of the range.
Function application with a tuple
The last thing to do is to take care of the dereferencing. Before we proceed though, we need to sidestep and look at a problem that I think will often come up with variadics. I speak of calling a function with the arguments stored in a std::tuple. For example, if I have args of type std::tuple<int, char, double> and I want to call "void foo(int, char, double)" with args' elements. It's trivial to do so in this case -- foo(std::get<0>(args), std::get<1>(args), std::get<2>(args)) -- but less so generically with the number of arguments not fixed. This StackOverflow thread's accepted answer provides the best way of doing so.
The main idea is for a tuple of size N to generate a sequence of type seq<0, 1, 2, ..., N-1>. Then call a helper function that will capture the integral sequence in its parameter pack and expand it into many calls to std::get<>:
// the sequence type
template<size_t...>
struct seq { };
// meta-function to generate seq<0, 1, ..., N-1>
template<size_t N, size_t ...S>
struct gens : gens<N-1, N-1, S...> { };
template<size_t ...S>
struct gens<0, S...> {
typedef seq<S...> type;
};
// accepts a tuple and returns seq<0, 1, ..., N-1>
template <typename... Ts>
typename gens<sizeof...(Ts)>::type tuple_indices(std::tuple<Ts...> const&) {
return typename gens<sizeof...(Ts)>::type();
};
// helper that captures indices into a parameter pack and invokes f
template<typename F, typename Args, size_t ...Indices>
auto call_func(F&& f, Args&& args, seq<Indices...>) -> decltype(f(std::get<Indices>(args)...)) {
return f(std::get<Indices>(args)...);
}
// takes function f and tuple args and invokes f with args
template <typename F, typename Args>
auto invoke(F&& f, Args&& args) -> decltype(call_func(std::forward<F>(f), std::forward<Args>(args), tuple_indices(args))) {
return call_func(std::forward<F>(f), std::forward<Args>(args), tuple_indices(args));
}
I think this problem will come up so often that invoke() should become part of the Standard Library. But as you'll see in a moment, it is important to understand the technique, since invoke() will not always work for all problems of this type.
Back to Dereference
The dereference() function needs to construct a std::tuple out of the references returned by dereferencing each of the iterators. The problem here is subtly different from one solved by invoke() above. First, instead of a function (or callable), we are invoking a constructor (albeit this can by solved by using std::make_tuple). Second, our tuple does not contain values to be invoked with. Rather, each of those values (iters tuple contains iterators) needs to be dereferenced first. Fortunately, the technique still applies:
// invoked by iterator_facade's impl of operator*()
typename value_type<Rs...>::type dereference() const {
return dereference(tuple_indices(iters));
}
// helper
template <size_t... Indices>
typename value_type<Rs...>::type dereference(seq<Indices...>) const {
typedef typename value_type<Rs...>::type result_t;
return result_t(*std::get<Indices>(iters)...);
}
We have now implemented all the necessary bits for a Forward Iterator.
Defining Boost.Range Adaptors
All that is left is to define xfiltered and xtransformed adaptors. It's a pretty simple process described here. First, we define a polymorphic functor (expander) that will just call invoke() defined earlier. The rest of the code wraps the user passed function inside the expander and passes it on to filter and transform adaptors. Everything else is just boilerplate specified by the Boost.Range's documentation:
template <typename F>
struct expander {
F f;
template <typename... Args>
typename std::result_of<F(Args...)>::type operator()(std::tuple<Args...> tup) const {
return invoke(f, tup);
}
};
// --- xfiltered ---
template< class T >
struct xfilter_holder : boost::range_detail::holder<T> {
xfilter_holder( T r ) : boost::range_detail::holder<T>(r) { }
};
template< class InputRng, class Pred >
boost::filtered_range<expander<Pred>, const InputRng>
operator|( const InputRng& r, const xfilter_holder<Pred>& f ) {
return boost::filtered_range<expander<Pred>, const InputRng>( expander<Pred>{f.val}, r );
}
const boost::range_detail::forwarder<xfilter_holder> xfiltered = boost::range_detail::forwarder<xfilter_holder>();
// --- xtransformed---
template< class T >
struct xtransform_holder : boost::range_detail::holder<T> {
xtransform_holder( T r ) : boost::range_detail::holder<T>(r) { }
};
template< class InputRng, class F >
boost::transformed_range<expander<F>, const InputRng>
operator|( const InputRng& r, const xtransform_holder<F>& f ) {
return boost::transformed_range<expander<F>, const InputRng>( expander<F>{f.val}, r );
}
const boost::range_detail::forwarder<xtransform_holder> xtransformed = boost::range_detail::forwarder<xtransform_holder>();
Conclusion
Boost.Range provides useful blocks that can be put together to express set-builder notation of one variable. Defining a cartesian_range allows for generalizing the solution to any number of variables. We also saw that the leaky nature of Boost Ranges make it awkward to define some types of ranges/iterators. Variadic templates and std::tuple are great additions to C++ but the Standard Library could benefit from an invoke() function.
No comments:
Post a Comment