std.container & ranges

[Steven Schveighoffer]

On Thu, 03 Nov 2011 14:08:31 -0400, Dmitry Olshansky  
<dmitry.olsh at gmail.com> wrote:

> On 03.11.2011 21:13, Steven Schveighoffer wrote:
>>
>> dcollections stipulates that all ranges/cursors can be verified in
>> O(lgn) time or better to belong to a specific container. In some cases,
>> this adds an extra word to the range/cursor, and in others, it's easy to
>> determine or the owner-reference was already needed. Since everything is
>> a class, the fallback is to just stick an owner class instance in the
>> range.
>>
>> This stipulation is necessary to allow safe slicing.
>>
>
> Seems reasonable, I'd expect checks to go away in release, right(?).

For the moment, no.  I am not sure whether this is the right decision or  
not, because once you get beyond arrays, when to do bounds checks becomes  
fuzzy.

For example, imagine you have this:

auto ts = new TreeSet!int(1, 3, 5, 7, 9);

What does this mean?

auto r = ts[2..4];

Note that a range type for a treeset has a pointer to a begin and end node  
for the container.  For arrays, not doing a bounds check is simply less  
code.  For a RBTree, you still have to look for the specific node, even if  
you are in release mode.

Another example:

auto ts2 = ts.dup; // duplicate the treeset

auto c1 = ts2.elemAt(3); // get the node for 3 in ts2

auto r2 = ts[c1..ts.end];

Here I can say, we can skip the belongs check (which is an O(lgn) walk up  
the tree).

But I'm still doing it in release mode.  I'm not sure what's best.  Should  
I just do the least work possible, or should I make it consistent with  
ts[2..4]?

-Steve