Re: [boost] Reimplementation of the MPL for C++11

on Sat Oct 19 2013, pfultz2 wrote:

...

But knowing the forward-only nature of parameter packs, I wonder how you can implement a random-access sequence like vector without (a) instantiating O(N) templates, like tuple, or (b) using the preprocessor and living with arbitrary limits.

The O(N) instantiation would happen at creation of the vector, not at lookup. Something like this:

template struct vector_base;

template struct vector_base : vector_base { using vector_base::item_; static T item_(long_<N>); };

template<long N> struct vector_base<N> { static void item_(); };

template struct vector : vector_base<0, Ts...> { };

Then we have O(1) lookup using decltype:

template struct at { typedef decltype(Vector::item_(Index())) type; };

I haven't tested this code yet, but the Boost.MPL works in a similiar way for compilers that suppor typeof. Of course generating the `item_` overloads with preprocessor perhaps could be faster than expaning the parameter pack using base classes, since it requires O(N) instantiations. However, if the prerpocessor version is faster, the `vector` could be specialized up to an arbitary limit to be generated by the preprocessor, and then after that it would use the base classes to generate the overloads.

True, but Matt Calabrese and Zach Lane proved that the ways we avoid O(N) instantiation in the existing MPL don't actually result in the expected speedups: http://zao.se/~zao/boostcon/10/2010_presentations/mon/instantiations_must_go... IMO real measurement is a requirement for progress in this area. -- Dave Abrahams