I have moved!

I've moved my blog
CLICK HERE

Friday, 22 May 2009

VC++16 has decltype in Beta 1 (so Linq to C++0x looks a little nicer)

This post has moved to my new(er) blog and can be found here: http://smellegantcode.wordpress.com/2009/05/22/vc16-has-decltype-in-beta-1-so-linq-to-c0x-looks-a-little-nicer/

A while ago I wrote up a little demo of using lambdas to implement convenient lazy list comprehension in C++0x, but at the time the VC++ compiler I was using lacked decltype, and I found a need for it.

I just tried out the Beta 1 that was released this week, and it has decltype, so here's the updated sample:

#include <iostream>
#include <vector>
#include <sstream>

// Some helpers for working with decltype 
// (maybe these are in std:: somewhere?)
template <class T>
T *make_ptr() { return (T *)0; }

template <class T>
const T &make_ref() { return *(make_ptr<T>()); }

// so you don't need to obtain boost::lexical_cast!
template <class T>
std::string to_string(const T &v)
{
    std::ostringstream s;
    s << v;
    return s.str();
}

// Unary function that always returns true
template <class T>
struct always_true
{
    bool operator() (const T &) const { return true; }
};

// Unary function that returns its argument
template <class T>
struct pass_thru
{
    T operator() (const T &e) const { return e; }
};

template <class TElemFrom, 
          class TElemTo, 
          class TIterFrom, 
          class TSelector,
          class TPredicate>
class filter
{
    TIterFrom from_;
    TIterFrom end_;
    const TSelector &selector_;
    const TPredicate &predicate_;

public:
    filter(TIterFrom from, TIterFrom end, 
             const TSelector &selector, 
             const TPredicate &predicate)
        : from_(from), end_(end), 
          selector_(selector), 
          predicate_(predicate) {}

    class const_iterator
    {
        TIterFrom from_;
        TIterFrom end_;
        const TSelector &selector_;
        const TPredicate &predicate_;

        void locate()
        {
            while (!done())
            {
                if (predicate_(*from_))
                    return;

                ++from_;
            }
        }

        bool done() const { return (from_ == end_); }

    public:
        const_iterator(TIterFrom from, TIterFrom end, 
                       const TSelector &selector,
                       const TPredicate &predicate)
            : from_(from), end_(end), 
              selector_(selector),
              predicate_(predicate) { locate(); }

        TElemTo operator*() const { return selector_(*from_); }

        const_iterator operator++()
        {
            ++from_;
            locate();
            return *this;
        }

        bool operator==(const const_iterator &other) const
            { return done() && other.done(); }

        bool operator!=(const const_iterator &other) const
            { return !done() || !other.done(); }
    };

    typedef TElemFrom value_type;

    const_iterator begin() const 
        { return const_iterator(from_, end_, selector_, predicate_); }

    const_iterator end() const 
        { return const_iterator(end_, end_, selector_, predicate_); }

    template <class TSelector>
    filter<TElemTo, 
             decltype(make_ref<TSelector>()(make_ref<TElemTo>())),
             const_iterator, 
             TSelector,
             always_true<TElemTo> >
        select(const TSelector &selector)
    {
        return filter<TElemTo, 
            decltype(make_ref<TSelector>()(make_ref<TElemTo>())), 
                      const_iterator, 
                      TSelector, 
                      always_true<TElemTo> >
                    (begin(), 
                     end(), 
                     selector, 
                     always_true<TElemTo>());
    }

    template <class TPredicate>
    filter<TElemTo, 
              TElemTo,
             const_iterator, 
             pass_thru<TElemTo>, 
             TPredicate> 
        where(const TPredicate &predicate)
    {
        return filter<TElemTo, 
                        TElemTo,
                        const_iterator, 
                        pass_thru<TElemTo>, 
                        TPredicate>
                    (begin(),
                     end(),
                     pass_thru<TElemTo>(), 
                     predicate);
    }
};

template <class TCollFrom>
filter<typename TCollFrom::value_type, 
         typename TCollFrom::value_type,
         typename TCollFrom::const_iterator, 
         pass_thru<typename TCollFrom::value_type>,
         always_true<typename TCollFrom::value_type> >
    from(const TCollFrom &from)
{
    return filter<typename TCollFrom::value_type, 
                    typename TCollFrom::value_type, 
                    typename TCollFrom::const_iterator, 
                    pass_thru<typename TCollFrom::value_type>, 
                    always_true<typename TCollFrom::value_type> >
                (from.begin(), 
                 from.end(), 
                 pass_thru<typename TCollFrom::value_type>(), 
                 always_true<typename TCollFrom::value_type>());
}

int main(int argc, char* argv[])
{
    std::vector<int> vecInts;
    vecInts.push_back(5);
    vecInts.push_back(2);
    vecInts.push_back(9);

    auto filtered = from(vecInts)
        .where([] (int n) { return n > 3; })
        .select([] (int n) { return "\"" + to_string(n) + "\""; });

    for (auto i = filtered.begin(); i != filtered.end(); ++i)
        std::cout << *i << std::endl;

    return 0;
}

The main function is the pay-off, of course. I have a vector of ints, and I wrap it something that ends up stored in a variable called filtered, which I can then iterate through. The filtering (discarding anything not greater than 3) and transforming (int to quoted string) of the items happens on-the-fly during that iteration.

(And to clarify, this is different from the last time I posted it because select no longer requires any type parameters to be explicitly given - thanks to decltype).

4 comments:

williamwsmithiii said...

Time to start the opensource project?

Daniel Earwicker said...

Thanks, but I'm not sure there's a need:

http://www.boost.org/doc/libs/1_39_0/libs/iterator/doc/index.html

That boost library is essentially the same idea, first implemented nearly a decade ago by the god-like David Abrahams. "transform_iterator" does the same thing as "select", "filter_iterator" the same as "where".

What makes my little example look nicer is (a) lambdas, which could just as easily be used with boost interator adaptors, and (b) the fact that I wrap containers (pairs of iterators or "ranges") instead of individual iterators, which is less flexible but much more readable.

But there is also this:

http://www.boost.org/doc/libs/1_39_0/libs/range/doc/utility_class.html#iter_range

Which captures the idea of a pair of iterators. So combine boost range and boost iterator adaptors, and you have a much more solid foundation for all this stuff. I was just using the raw language features and the more traditional concepts of the std library to demonstrate lambdas and communicate these ideas in .NET terms.

Maybe if I get some time I'll post a rewrite built on top of those boost libraries. Also I think it would be more "C++" to use an operator overload >> to show the iterators working like a pipe (similar to the way this is all done in F# as well).

Eelco said...

Hi Daniel,

First of all, thanks a lot for this great example; I am programming in both C++ and C# at the time, and I find I sorely miss LINQ, or even halfway decent support for lazy collection manipulation in C++.

However, for reasons that are beyond my template-fu, your example code does not compile under MSVS2010 professional. To be specific, the error I get is:

"IntelliSense: no instance of function template "filter::select [with TElemFrom=int, TElemTo=int, TIterFrom=filter>>, pass_thru, always_true>::const_iterator, TSelector=pass_thru, TPredicate=lambda []bool (int n)->bool]" matches the argument list"

The filter function works perfectly fine, however.


Secondly, id have to respectfully disagree with the notion that this code does not fill a useful niche; after wrestling with the rather convoluted boost implementation for a day, I discovered its doesnt accept C++0x lambdas. Great; goodbye improved elegance. I might as well go back to handcrafting my loops then.

Your implementation seems a lot simpler; exactly what 99% of people will be looking for 99% of the time. Too bad I cant get it to work though :(.

Daniel Earwicker said...

@Eelco - it compiles fine, try building and running it. That error is a bug in the Intellisense engine (which uses a different compiler).