[phobos] Definition of Random Access Range

Andrei Alexandrescu andrei at erdani.com
Wed Jun 23 20:49:15 PDT 2010


On 06/23/2010 10:42 PM, David Simcha wrote:
> On 6/23/2010 11:36 PM, Andrei Alexandrescu wrote:
>> On 06/23/2010 10:22 PM, David Simcha wrote:
>>> Should we just redefine random access ranges such that they must either
>>> have a length or be infinite?
>>
>> I think that's reasonable. If a finite range didn't define length, it
>> would be easy to find it in O(log n) by binary search.
> I guess you're assuming some method of signaling on out of bounds
> access, such as throwing an exception?

Yah. What I'm basically saying is, if you can decide in O(1) what 
element at position n is, there's no way you can't write (inside the 
range) some sort of a test that gives you the length in logarithmic 
time. A range can't be at the same time random-access, finite, and 
unable to figure its bounds. Or so I believe :o).

Andrei


More information about the phobos mailing list