Home > Uncategorized > Linq to C++ (or something much better)

Linq to C++ (or something much better)

A really long time ago (26th Jan 2009 to be exact), I got excited about lambdas in C++0x, and the idea of bringing a Linq-like lazily-evaluated sequence filtering system to C++. I wrote a blog post about this idea partly as a pedagogical exercise in explaining the parallels/divergences in how an iteratable sequence is represented in C++ and C#.

Whenever I’m asked if this would make sense as a real library, I’ve replied that in the real world it would make much more sense to build on the stuff in Boost, especially the range library.

And guess what? At that very moment someone was already working on it (only with a far more elegant, extensible interface), and the following month a set of extensions to range were put up for review, and were accepted… then a long time passed (they’re very careful) until summer of 2010, when finally the new features were released in Boost 1.43.

I only discovered this just now. People still seem to be finding that old blog post, so it only seems proper to get up-to-date. My first stab looked like this:

#include <boost/range/algorithm/for_each.hpp>
#include <boost/range/adaptor/filtered.hpp>
#include <boost/range/adaptor/transformed.hpp>

#include <boost/lexical_cast.hpp>

#include <vector>
#include <iostream>
#include <string>

int main()
{
	using namespace boost::adaptors;

	std::vector<int> numbers;
	numbers.push_back(0);
	numbers.push_back(-1);
	numbers.push_back(4);
	numbers.push_back(-3);
	numbers.push_back(5);
	numbers.push_back(8);
	numbers.push_back(-2);
	
	auto quoted_positives = numbers 
		| filtered([] (int n) { return n >= 0; })
		| transformed([] (int x) { 
                    return "\"" + boost::lexical_cast<std::string>(x) + "\""; 
                  });

	boost::for_each(quoted_positives, [] (std::string n) { 
            std::cout << n << std::endl; 
        });
	return 0;
}

As you can see, the key is the use of operator| to make a piping syntax, so that we can naturally read from left to right (you may have seen the same approach used in F#). So I start with a vector of plain integers called numbers, I then pipe that through the filtered adaptor so as to get just the positives (corresponding to Where in Linq), and finally through the transformed adaptor to turn each positive into a quoted string (corresponding to map in most functional frameworks and to Select in Linq).

Except… it doesn’t work.

The problem is that boost is not yet entirely C++11 lambda-friendly. It’s unfortunate that the boost documentation (and other online information) is peppered with the word lambda signifying something else, so I may just be missing something. But the gist of the problem appears to be that transformed wants a functor with a member type called result_type. So you are supposed to write something like this:

struct quote
{
    typedef std::string result_type;

    std::string operator()(int x) const 
    {
        return "\"" + boost::lexical_cast<std::string>(x) + "\""; 
    }
};

C++11 lambdas don’t have that result_type inside them, so they don’t directly fit. It goes without saying that we don’t like this, because the whole point of lambdas is to avoid writing a separate class somewhere else.

It is surely possible to extend boost’s function_traits so that they can reflect on lambdas. In the past they have not been written to work on general functors because a functor can have multiple overloads of operator(), so you are required to manually pick one of those members before you ask questions. But this position is no longer sensible (if indeed it ever was). The majority of functors will now be lambdas, with a single overload of operator(), and it is (as we can see from this example) perfectly reasonable to want to know the return type of that single overload. A lambda is an alternative to a plain function, and whatever is useful for a function will be useful for a lambda.

But in the meantime, it is interesting to see how many hoops we have to jump through to make the above sample code work as expected.

If you read my last update on this sordid subject you’ll know that I don’t want to have to state the type of something that can be inferred, so I’m not going to be satisfied by a wrapper template that just adds a manually specified result_type member to my lambda. Ugh! It must be inferred automatically.

Fortunately this is just a matter of using a few simple steps in metaprogramming. Firstly, a template designed to match a member function:

template <class T>
struct mem_fun_traits { };

Of course in this general form it will match anything. But we’ll only bother to specialise it for one case: a pointer to a const member function that accepts one argument:

template <class R, class C, class A>
struct mem_fun_traits<R (C::*)(A) const> 
{
    typedef R result_type;
    typedef A argument_type;
};

So if you pass mem_fun_traits the type of a pointer to the operator() within a lambda, you know what it accepts and returns. But how do you get that type argument? With decltype that’s easy-peasy:

template<typename T>
struct functor_member {
    typedef decltype(&T::operator()) type;
};

Armed with these tools, we can write a traits class for our simple one-argument, single-overload functors (and hence, by an extraordinary coincidence, also for C++11 lambdas):

template <class F>
struct functor_traits
{
    typedef typename functor_member<F>::type member_t;
    typedef mem_fun_traits<member_t> traits;

    typedef typename traits::result_type result_type;
    typedef typename traits::argument_type argument_type;
};

This is the thing that should be integrated into boost’s function_traits, to make lambdas work as true replacements for functions. I’m sure someone’s working on it.

In the event that this doesn’t happen, we can shoehorn it together anyway by making a function template that adds type metadata to any single-argument functor:

template <class F>
class functor_with_traits_t
{
    F f;

public:
    functor_with_traits_t(F f_) : f(f_) {}

    typedef typename functor_traits<F>::result_type result_type;
    typedef typename functor_traits<F>::argument_type argument_type;

    result_type operator()(argument_type a) const { return f(a); }
};

template <class F>
inline functor_with_traits_t<F> functor_with_traits(F f) { return functor_with_traits_t<F>(f); }

So if you have a plain old lambda like this:

auto l = [] (int x) { 
    return "\"" + boost::lexical_cast<std::string>(x) + "\""; 
};

You can “fix” it to have type metadata like so:

auto l2 = functor_with_traits(l);

This makes it compatible with boost’s transformed! Although manually putting in that wrapper each time is pretty tedious. We can work around that by defining our own adapter (let’s call it selected in slavish imitation of Linq) that just plugs together functor_with_traits and transformed. Sounds simple, though as always the difficulty is in figuring out the types:

template <class F>
inline um... selected(F f)
{
    return boost::adaptors::transformed(functor_with_traits(f)); 
}

The um... is “whatever type we’re returning”. Wouldn’t it be nice if we could put auto there? Well, we almost can: decltype to the rescue as usual:

decltype(
    boost::adaptors::transformed(
        functor_with_traits(make_ref<F>())
    )
)

That is: give me the type that would be returned if I called transformed, passing it the result of a call to functor_with_traits, passing it an F. Of course we can’t assume that F can be default constructed, hence the use of that funny make_ref function that always comes in handy with decltype.

So our completed adaptor is:

template <class F>
decltype(
    boost::adaptors::transformed(
        functor_with_traits(make_ref<F>())
    )
)
selected(F f)
{
    return boost::adaptors::transformed(functor_with_traits(f)); 
}

We can use selected in place of transformed and everything is hunky dory. Full example:

#include <boost/range/algorithm/for_each.hpp>
#include <boost/range/adaptor/filtered.hpp>
#include <boost/range/adaptor/transformed.hpp>

#include <boost/lexical_cast.hpp>

#include <vector>
#include <iostream>
#include <string>

template <class T>
T *make_ptr() { return (T *)0; }

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

template <class T>
struct mem_fun_traits { };

template <class R, class C, class A>
struct mem_fun_traits<R (C::*)(A) const> 
{
  typedef R result_type;
  typedef A argument_type;
};

template<typename T>
struct functor_member {
    typedef decltype(&T::operator()) type;
};

template <class F>
struct functor_traits
{
	typedef typename functor_member<F>::type member_t;
	typedef mem_fun_traits<member_t> traits;

	typedef typename traits::result_type result_type;
	typedef typename traits::argument_type argument_type;
};

template <class F>
class functor_with_traits_t
{
	F f;

public:
	functor_with_traits_t(F f_) : f(f_) {}

	typedef typename functor_traits<F>::result_type result_type;
	typedef typename functor_traits<F>::argument_type argument_type;

	result_type operator()(argument_type a) const { return f(a); }
};

template <class F>
functor_with_traits_t<F> functor_with_traits(F f) { return functor_with_traits_t<F>(f); }

template <class F>
decltype(boost::adaptors::transformed(functor_with_traits(make_ref<F>()))) selected(F f)
{
	return boost::adaptors::transformed(functor_with_traits(f)); 
}

int main()
{
	using namespace boost::adaptors;

	std::vector<int> numbers;
	numbers.push_back(0);
	numbers.push_back(-1);
	numbers.push_back(4);
	numbers.push_back(-3);
	numbers.push_back(5);
	numbers.push_back(8);
	numbers.push_back(-2);
	
	auto quoted_positives = numbers 
		| filtered([] (int n) { return n >= 0; })
		| selected([] (int x) { 
                    return "\"" + 
                      boost::lexical_cast<std::string>(x) +
                      "\"";
                  });

	boost::for_each(quoted_positives, [] (std::string n) {
            std::cout << n << std::endl; 
        });
	return 0;
}

(Tested on MSVC++ 16.00.40219.01 and GNU G++ 4.5.3.)

Advertisements
Categories: Uncategorized Tags: , , , ,
  1. MPelletier
    December 6, 2011 at 2:42 pm

    Hey, I’m glad I found this blog! I was wondering this morning if anyone had ever attempted a C++ LINQ. I wanted to ask you, what do you use to make your code blocks look like that? I’ve looked around and can’t find something decent.

    • MPelletier
      December 7, 2011 at 3:13 pm

      And yes, our themes are too alike. I was looking for a different one. Don’t worry, I’m not a copycat! đŸ™‚ But I would like to know how you prettify your code like this. Thanks.

  2. heksesang
    March 30, 2012 at 7:45 pm

    template
    decltype(boost::adaptors::transformed(functor_with_traits(*(F*)0))) selected(F f)
    {
    return boost::adaptors::transformed(functor_with_traits(f));
    };

    If you change the method on line 59-63 to this, you don’t need the make_ptr and make_ref methods.

  3. A. Programmer
    June 19, 2012 at 1:13 pm

    Hey, thanks for your insights! I was wondering, what’s the license for the code in this post? Can I use it in my project?

  4. Lynn
    October 26, 2012 at 8:50 pm

    You don’t need to create an adapter if you define
    #define BOOST_RESULT_OF_USE_DECLTYPE

  5. chris
    May 5, 2016 at 9:07 am

    FYI you can also do std::bind(l)

  1. October 31, 2011 at 1:06 pm
  2. October 31, 2011 at 1:08 pm
  3. March 30, 2012 at 10:17 am

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: