Re: [boost] Re: MPL containers and algorithms

From: Terje Slettebø (tslettebo_at_[hidden])
Date: 2002-08-01 19:02:23

>From: "David Abrahams" <dave_at_[hidden]>

>>From: "Terje Slettebø" <tslettebo_at_[hidden]>

>> Having looked at mpl::vector, and its docs, it appears that it may be
>> possible to get O(1) access to elements, if the compiler supports typeof.

>I don't see why typeof should be needed for O(1) access.

Yeah, I thought of that, too. I read the docs on vector, but it wasn't clear
to me if typeof was required for O(1) access, or not. The complexity for
access isn't that well specified. It's only mentioned in a note. To quote:

"On compilers that support the typeof extension, vector is the simplest and
in many cases the most efficient sequence [1].

[1] The typeof operator allows one to use overload resolution to implement a
constant-time random access to elements of the sequence with minimum amount
of code (in contrast to the usual brute-force approach the library has to
resort to when the typeof operator is not available):" [What follows is the
code using typeof]

Perhaps you now can see what it was hard to understand what the complexity
guarantee was, if typeof wasn't available? It is simply not stated.

This is why I put this conservatively (so I wouldn't claim more than what
was the case). Perhaps complexity for access (and any conditions for it, and
what the complexity is they don't hold) could be stated clearly in the docs?

I think this is an important point, since efficiency for the various
sequences have been discussed.

>All you need is a
>specialization of at<> for each N up to the maximum size of vector. Of
>course, you can use that trick for type lists as well. In fact, I did that
>in one place in Boost.Python in order to speed it up on some old compilers,
>with the old MPL codebase.

Regards,

Terje