[boost] Efficient tuple implementation

Subject: [boost] Efficient tuple implementation
From: Louis Dionne (ldionne.2_at_[hidden])
Date: 2014-06-06 22:18:47

Hi,

I recently discovered (or maybe not) a neat trick to implement a tuple-like
container. The technique has a couple of drawbacks which I will explain later.
For a real example, you can see my list implementation in Boost.Hana at [1].
Here's the idea:

    auto list = [](auto ...xs) {
        return [=](auto access) { return access(xs...); };
    };

    auto head = [](auto xs) {
        return xs([](auto first, auto ...rest) { return first; });
    };

    auto tail = [](auto xs) {
        return xs([](auto first, auto ...rest) { return list(rest...); });
    };

    auto length = [](auto xs) {
        return xs([](auto ...z) { return sizeof...(z); });
    };

    // etc...
    // then use it like

    auto three = length(list(1, '2', "3"));

The idea is to use the capture of the lambda as a fast compiler-generated
struct with the desired members. By passing a function to that lambda, we
get an access to the unpacked representation of those members and we can
then apply any fast algorithm on parameter packs.

Drawbacks
---------
1. The type of that tuple is completely opaque. Hence, it is harder to debug,
   but I'm working on other stuff that should make this a moot point.

2. Since lambdas can't be made constexpr, this tuple can't either. However,
   there was some discussion about proposing constexpr lambdas at C++Now
   and it looked like there was a lot of support for the idea, so this
   might change.

Benchmarks
----------
I ran a couple of benchmarks testing the compilation time and the results
are self explanatory. The benchmark suite is at [2].

## Create a tuple of n elements
The test code looks like:

    #include <boost/tuple/tuple.hpp>
    int main() {
        auto go = boost::make_tuple(1, ..., n);
    }

<a href="http://imgur.com/rKqmvk3"><img src="http://i.imgur.com/rKqmvk3.png"/></a>

## Access the last element of a tuple of n elements
The test code looks like:

    #include <boost/tuple/tuple.hpp>
    int main() {
        auto go = boost::make_tuple(1, ..., n);
        auto last = boost::get<n-1>(go);
    }

<a href="http://imgur.com/b4rWR4y"><img src="http://i.imgur.com/b4rWR4y.png"/></a>

Also, for those following the development of Boost.Hana, it is going
well and I am preparing for a followup in the near future. Stay tuned!

Regards,
Louis Dionne

[1]: http://github.com/ldionne/hana/blob/master/include/boost/hana/list.hpp
[2]: http://github.com/ldionne/benchcc/tree/master/benchmarks