std.container & ranges

[Steven Schveighoffer]

On Thu, 03 Nov 2011 16:27:46 -0400, Dmitry Olshansky  
<dmitry.olsh at gmail.com> wrote:

> On 03.11.2011 22:37, Steven Schveighoffer wrote:
>> 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];
>
> hm-h will that actually work? I mean searching in ts for node from ts2?

c1 is a cursor, so there is no need to search for it (the point of a  
cursor is to keep a reference to an element for later use).  All you have  
to do is verify it's in the container (and the ordering is valid).

If unchecked, it will result in likely a segfault, because the two  
endpoints are not connected.

>> Here I can say, we can skip the belongs check (which is an O(lgn) walk
>> up the tree).
>>
>
> Well, I was mostly talking about this kind of scenario i.e. skip  
> checking that cursor do belong to this collection. While in ts[2..4]  
> example there is no (explicit) cursors so it's a different situation.

So what should happen?  Should it throw?

>> 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]?
>>
>
> I'd say release mode should avoid as much extra work as possible while  
> keeping primary functionality intact, but that's just me.

Yes, it's a dilemma that I'm not sure what the right answer is.  It does  
make sense that release mode should just avoid the checks altogether.

-Steve