Re: C++ Frequently Questioned Answers
on Mon Nov 05 2007, Yossi Kreinin <yossi.kreinin-AT-gmail.com> wrote:
On Nov 5, 11:26 am, David Abrahams <d...@boost-consulting.com> wrote:
Now, I think that implementing type lists to be "compile time type
hashes or sets" (that is, represent hash tables using TMP) is really
really hard (both for a human to write or read and for a compiler to
process).
Already done:http://www.boost.org/libs/mpl/doc/refmanual/set.html, etc.
Now that I think of it, I wonder how you implement random access for
type lists (or arrays...) of arbitrary length; in particular, I saw
this comment in the boost.org docs:
"If seq is a generic name for some Variadic Sequence, its variadic
form allows us to specify a sequence of n elements t1,t2,... tn, for
any n from 0 up to a preprocessor-configurable limit
BOOST_MPL_LIMIT_seq_SIZE"
This seems to imply that the sequence size is bound by a constant,
Yes. But that's okay; you can change the constant.
and this makes sense to me, because AFAIK there's no way to have a
"type array" with random access in the current C++ standard; all you
have is "compile time cons cells" like these:
template<class H, class T> struct List
{
typedef H Head;
typedef T Tail;
};
No, you also have
struct vector0 {};
template <class A0> struct vector1 {};
template <class A0, class A1> struct vector2 {};
template <class A0, class A1, class A3> struct vector3 {};
Then you can use a bunch of specializations to get at any vector
element in O(1) template instantiations. If your compiler supports
typeof(), you can even do that with unbounded typelists, by creating
an overload set. See my sieve posting.
Apparently the best you can do in terms of search complexity is some
kind of sorted tree structure, but you can't have hash look-up with
random access, for example.
Sure you can. Anything you can do in other pure functional languages,
you can do with templates. It's just a lot uglier ;-)
--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]