Inserting and removing elements from a sorted container

[Jonathan M Davis]

On Sunday, November 19, 2017 16:48:00 Dirk via Digitalmars-d-learn wrote:
> On Sunday, 19 November 2017 at 16:05:53 UTC, Jonathan M Davis
>
> wrote:
> > I'd suggest that you use std.container.rbtree..RedBlackTree. A
> > red-black tree exactly the sort of data structure that is
> > typically used in a sorted set.
> >
> > - Jonathan M Davis
>
> Thank you, i will look into it.
>
>
> I have a question related to ranges:
>
> An input range has an interface like this:
>
> struct inputRange
> {
>      void popFront();
>      @property bool empty();
>      @property int front();
> }
>
>
> So if i use a foreach loop to iterate over all elements of a
> range, i would expect the range to shrink for every iteration:
>
> auto list = SList!uint(1,2,3);
> auto range = list[].save();
> foreach( i; range ) {
>    writeln(range);
> }
>
> Expected output:
> [1,2,3]
> [2,3]
> [3]
>
> But i get:
> [1,2,3]
> [1,2,3]
> [1,2,3]
>
> Why don't i see the expected output?

foreach(e; range)
{
    ...
}

gets lowered to something like

for(auto __range = range; !__range.empty; __range.popFront())
{
    auto e = __range.front;
    ...
}

So, the range gets copied when it's used with foreach. foreach then consumes
the copy. If a range is a value type such that copying the range is
equivalent to calling save on a forward range, then using the range with
foreach implicitly saves it, and so you iterate over a separate copy, and if
you then iterate over the original, then it continues to iterate from
wherever it was. However, if the range is a reference type, then copying the
range just copies its reference rather than implicitly saving it, and when
you try to iterate over the original, it won't work, because it's empty. And
if the range is a pseudo-reference type such that copying the range does not
simply copy a reference, and copying the range is not the same as calling
save, then if you try to iterate over the original after copying the range
with foreach will result in really weird behavior.

So, in the general case, you should never use a range again after having
copied it. It will work in some cases, but in others, it will fail miserably
- potentially in very weird ways. So, if you want to iterate over a range
with foreach and then do something with the range afterwards, call save when
you pass it to foreach. e.g.

foreach(e; range.save)
{
    ...
}

though if you're just grabbing the range from a container, you can just use
the container in foreach. e.g.

foreach(e; container)
{
    ...
}

The compiler implicitly calls [] on the container to get its range. So, it
would be equivalent to

foreach(e; container[])
{
    ...
}

Also, I would point out that your use of save in your example doesn't really
make sense:

> auto list = SList!uint(1,2,3);
> auto range = list[].save();

list[] will give you a fresh range every time you call it. You only need to
be calling save if you already have a range and want an indepedent copy to
iterate over. e.g.

auto list = SList!uint(1, 2, 3);
auto range = list[];
range.popFront();
foreach(e; range.save)
    writeln(e); // prints 2 and then 3
writeln(range.save); // prints [2. 3]

On a side note, you should be calling save without parens. In most cases,
with parens will work, but the range API specifically treats save like a
property (much as that doesn't really make sense, since save doesn't fit the
typical definition of what a property is), so it's technically possible for
someone to implement a range where save is a variable (which would be really
weird, but as long as copying it then resulted in range.save giving you a
range that was the same as the original range, it would work).

I wouldn't expect you to have problems calling save with parens in practice,
but it's best to use range primitives in the way that isInputRange,
isForwardRange, etc. test for them (the code that they test should be in the
docs). For other range primitives, it really does matter in practice (e.g.
empty is typically a function for most ranges but for infinite ranges, it's
an enum, so if you call it with parens, some ranges will fail to compile
with your code). So, it's best to get in the habit of calling them the same
way that the range API traits call them - which for forward ranges, means
front, empty, length, popFront(), and save.

- Jonathan M Davis