C++ LINQ-like iterator operations

c++, functional-programming, iterator, linq

Solution

I don't have concrete experience with LINQ, but the Boost.Iterator library seems to approach what you're referring to.

The idea is to have functions (IIUC, in LINQ, they take the form of extension methods, but that's not fundamental), taking an iterator and a function, combining them to create a new iterator.

LINQ "Where" maps to `make_filter_iterator`:

std::vector<int> vec = ...;
// An iterator skipping values less than "2":
boost::make_filter_iterator(_1 > 2, vec.begin())

LINQ "Select" maps to `make_transform_iterator`:

using namespace boost::lambda;
//An iterator over strings of length corresponding to the value
//of each element in "vec"
//For example, 2 yields "**", 3 "***" and so on.
boost::make_transform_iterator(construct<std::string>('*', _1), vec.begin())

And they can be composed:

//An iterator over strings of length corresponding to the value of each element
// in "vec", excluding those less than 2
std::vector<int> vec = ...;
boost::make_transform_iterator(construct<std::string>('*', _1), 
    boost::make_filter_iterator(_1 > 2, vec.begin())
)

However, there are a few annoying things with this:

- The type returned by `make_xxx_iterator(some_functor, some_other_iterator)` is `xxx_iterator<type_of_some_functor, type_of_some_iterator>`

- The type of a functor created using boost::bind, lambda, or phoenix quickly becomes unmanageably large and cumbersome to write.

That's why I avoided in the code above to assign the result of `make_xxx_iterator` to a variable. C++0x "auto" feature will be pretty welcome there.

But still, a C++ iterator can't live "alone": they have to come in pairs to be useful. So, even with "auto", it's still a mouthful:

auto begin = make_transform_iterator(construct<std::string>('*', _1), 
    make_filter_iterator(_1 > 2, vec.begin())
);
auto end = make_transform_iterator(construct<std::string>('*', _1), 
    make_filter_iterator(_1 > 2, vec.end())
);

Avoiding the use of lambda makes things verbose, but manageable:

struct MakeStringOf{
    MakeStringOf(char C) : m_C(C){}
    char m_C;

    std::string operator()(int i){return std::string(m_C, i);}
};

struct IsGreaterThan{
    IsGreaterThan(int I) : m_I(I){}
    int m_I;

    bool operator()(int i){return i > m_I;}
};

typedef boost::filter_iterator<
   IsGreaterThan, 
   std::vector<int>::iterator
> filtered;

typedef boost::transform_iterator<
   MakeStringOf, 
   filtered
> filtered_and_transformed;

filtered_and_transformed begin(
    MakeStringOf('*'), 
    filtered(IsGreaterThan(2), vec.begin())
);

filtered_and_transformed end(
    MakeStringOf('*'), 
    filtered(IsGreaterThan(2), vec.end())
);

The (not-yet)Boost.RangeEx library is promising in this respect, in that it allows to combine the two iterators in a single range. Something like:

auto filtered_and_transformed = make_transform_range(
    make_filter_range(vec, _1 > 2),
    construct<std::string>('*', _1)
);

Problem

Having been tainted by Linq, I'm reluctant to give it up. However, for some things I just need to use C++. The real strength of linq as a linq-consumer (i.e. to me) lies not in expression trees (which are complex to manipulate), but the ease with which I can mix and match various functions. Do the equivalents of `.Where`, `.Select` and `.SelectMany`, `.Skip` and `.Take` and `.Concat` exist for C++-style iterators? These would be extremely handy for all sorts of common code I write. I don't care about LINQ-specifics, the key issue here is to be able to express algorithms at a higher level, not for C++ code to look like C# 3.0. I'd like to be able to express "the result is formed by the concatenation first n elements of each sequence" and then reuse such an expression wherever a new sequence is required - without needed to manually (and greedily) instantiate intermediates.

Original source

Related problems