std.container & ranges

[Dmitry Olshansky]

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?

>
> 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.

> 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.


-- 
Dmitry Olshansky