On Thu, 03 Nov 2011 16:27:46 -0400, Dmitry Olshansky
<dmitry.o...@gmail.com> wrote:
On 03.11.2011 22:37, Steven Schveighoffer wrote:
On Thu, 03 Nov 2011 14:08:31 -0400, Dmitry Olshansky
<dmitry.o...@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
