Re: [boost] Re: MPL containers and algorithms

From: Douglas Gregor (gregod_at_[hidden])
Date: 2002-08-12 19:05:13

On Monday 12 August 2002 12:12 am, Paul Mensonides wrote:
> Okay.  I have a question though.  Do you think it is possible on any
> compiler to compute the length of such a construct with an MPL algorithm? 
> <-- I mean realistically, not in theory.  There is an obvious physical
> limit on instantiation depth.  Sometimes you can change it, but what would
> you have to change it to in order to process 10,000 elements?

The phyisical limits on instantiation depth come from memory limitations. 
Either you run out of heap+swap to hold the instantiations (I haven't found 
this to be a problem -- 10,000 instantiations isn't really many at all) or 
you run out of stack space. I'm sure we could easily test this, I'm just 
being lazy about it :)

> A vector of types that is large is difficult to maintain because there are
> so many elements.  Maybe I don't understand what you mean by type-vectors. 
> What I mean by them is a series of types that is defined in a tuple-like
> fashion:
>
> template<> struct type_vector<10> {
>     template<class T1, ... class T10> struct args {
>
>         template<int, int D = 0> struct subscript;
>
>         template<int D> struct subscript<0, D> {
>             typedef T1 type;
>         };
>
>         template<int D> struct subscript<1, D> {
>             typedef T2 type;
>         };
>
>         // etc.
>
>         template<int D> struct subscript<9, D> {
>             typedef T10 type;
>         };
>     };
> };
>
> // etc.
>
> typedef type_vector<3>::args<int, double, char> types;
>
> typedef types::subscript<1> y; // double
> typedef types::subscript<0> z; // int
>
> ...Or something similar.  In other words, constant-time random access.

That's one form of type-vector, but not the type that Burton et al. used. They 
used type vectors that look like this:

  struct end_of_vector {};

  // Basis case, which ends the list
  template<int Idx> struct integral_types { typedef end_of_vector type; };

  // specializations contain the elements
  template<> struct integral_types<0> { typedef bool type; }
  template<> struct integral_types<1> { typedef short type; }
  template<> struct integral_types<2> { typedef int type; }
  template<> struct integral_types<3> { typedef long type; }

That's it. You can define a bidirectional iterator like this:

  template<template<int N> struct TypeVector, int Pos = 0>
  struct typevector_iterator
  {
    typedef typename TypeVector<Pos>::type type;
    typedef typevector_iterator<TypeVector, Pos+1> next;
    typedef typevector_iterator<TypeVector, Pos-1> prev;
  };

> > The typevector example I've given is _not_ speculation; it's not a
> > what-if. It's research that was presented at WCGP'02 last month and will
> > be published as part of the proceedings of that conference; I can send
> > the preproceedings version of the paper privately to any interested
> > persons.
>
> Unless I'm completely misunderstanding you, it only shows the utility of
> type-vectors.  My question is, what is the utility of cons-style lists if
> you already have a full blown type-vector implementation?

This form of typevector has very different characteristics from typelists.  
It's quite compact to create even for very large typevectors in this style, 
but it can't be used as a general metaprogramming sequence because most 
sequence operations just can't be done with it. How would you write 
push_front for this typevector? insert? Basically, it boils down to this 
style of typevector being great for big, immutable compile-time data 
structures but it can't be used in more dynamic scenarios.

Typelists, on the other hand, are great for small, dynamic data structures. 
You can insert into a typelist, reverse a typelist, splice typelists, etc. 
All these operations you can't do with the style of typevectors described 
above.

> I'm not making the case for typelists, I'm making the case that multiple
> pure sequence types are not necessary.  I totally agree that type-vectors
> of some kind are inherently faster than cons-style lists.  Do you have
> another example that implemented with a typelist that is inherently better
> implemented with a typelist?

Most of the metaprograms out there fall into this category. But not all :)

        Doug