Thread overview
Is there an elegant way to non-destructively step through a red black tree?
March 20
Is there an elegant way, like with foreach, to step through a red black tree non-destructively?  This destructive failure is the best I've been able to come up with.

while(!rbt.empty)
{
    Node e = rbt.front;
    writeln("e = ", e);
    rbt.removeFront;
}

I don't suppose there are any gentle tutorials regarding the library containers?

March 20
On Thu, Mar 20, 2025 at 11:51:46PM +0000, WhatMeWorry via Digitalmars-d-learn wrote:
>     Is there an elegant way, like with foreach, to step through a red black
> tree non-destructively?  This destructive failure is the best I've been able
> to come up with.
> 
>     while(!rbt.empty)
>     {
>         Node e = rbt.front;
>         writeln("e = ", e);
>         rbt.removeFront;
>     }
> 
> 
> I don't suppose there are any gentle tutorials regarding the library containers?

Doesn't RedBlackTree have a member function or operator overload that
returns a (non-destructive) range over the container?  IIRC it should be
opSlice(), which means you should be able to do this:

	foreach (Node e; rbt[]) {
		... // whatever you need here
	}


T

-- 
Valentine's Day: an occasion for florists to reach into the wallets of nominal lovers in dire need of being reminded to profess their hypothetical love for their long-forgotten.
April 03
On Thursday, March 20, 2025 6:32:03 PM MDT H. S. Teoh via Digitalmars-d-learn wrote:
> On Thu, Mar 20, 2025 at 11:51:46PM +0000, WhatMeWorry via Digitalmars-d-learn wrote:
> >     Is there an elegant way, like with foreach, to step through a red black
> > tree non-destructively?  This destructive failure is the best I've been able
> > to come up with.
> >
> >     while(!rbt.empty)
> >     {
> >         Node e = rbt.front;
> >         writeln("e = ", e);
> >         rbt.removeFront;
> >     }
> >
> >
> > I don't suppose there are any gentle tutorials regarding the library containers?
>
> Doesn't RedBlackTree have a member function or operator overload that
> returns a (non-destructive) range over the container?  IIRC it should be
> opSlice(), which means you should be able to do this:
>
>   foreach (Node e; rbt[]) {
>       ... // whatever you need here
>   }

Yes, all of the containers in std.container should have an opSlice function which returns a range over the container. And since for better or worse, foreach calls opSlice on its argument if it has it, then

foreach (auto e; rbt[]) {
}

is equivalent to

foreach (auto e; rbt) {
}

so long as rbt[] doesn't return something that in turn implements [] (which is part of why ranges shouldn't implement opSlice with no arguments).

As for tutorials on the containers in std.container, I'm not aware of any, though maybe tour.dlang.org has something. The Phobos containers work well overall, but they're also kind of awkward in some respects, because they use ranges for pretty much everything - which makes perfect sense for iterating through the elements of the container but gets awkward when it comes to stuff like removing elements.

There are some alternate container libraries on code.dlang.org for those who want something different, though for a lot of use cases, D's built-in dynamic arrays and AAs tend to be plenty. RedBlackTree is probably the only container from Phobos that I've actually used in any of my code, since occasonally, you need a sorted map or set, and dynamic arrays and AAs don't work well for that, but RedBlackTree does.

- Jonathan M Davis