How to iterate over const(RedBlackTree)?

John McFarlane via Digitalmars-d digitalmars-d at puremagic.com
Thu Oct 16 18:08:59 PDT 2014


On Friday, 3 January 2014 at 07:22:32 UTC, monarch_dodra wrote:
> On Thursday, 2 January 2014 at 14:59:55 UTC, Adam D. Ruppe 
> wrote:
>> On Thursday, 2 January 2014 at 13:30:06 UTC, monarch_dodra 
>> wrote:
>>> Currently, this is not possible. Or if it was, it would have a
>>> *very* high code cost inside RBT.
>>
>> It is possible in theory; RBT returns a separate Range type 
>> with opSlice that is implemented in terms of pointers to node. 
>> (This is hidden by an alias RBNode!Elem* Node, which gets in 
>> the way, but if those were inout(RBNode)* or const()* it'd 
>> work).
>>
>> We can have mutable pointers to const data, which would work 
>> with the range. So opSlice returns a mutable range that points 
>> back to const data.
>>
>>
>> But in this case, none of the functions in rbtree use const 
>> nor inout, and there's some caching (e.g. _left and _right) 
>> that I'm not sure can work with it at all anyway. In a const 
>> node, the left and right properties won't work..
>
> Right. Doable, but not trivially so :/
>
> Array might be able to pull it off more easily.
>
> That said, it would only solve the "const container => Range"
> issue, but the "const range" problem itself would remain :(

I'm trying to get to grips with D, coming from a C++ background 
and const correctness is tough thing to get comfortable with. 
I've got a member variable that's RedBlackTree and I'd like to 
examine its contents inside an invariants() block. Is this 
possible at all right now? Obviously, this would be trivial to 
achieve using std::set::const_iterator so is it the language or 
the library that poses the difficulty for me? Thanks.


More information about the Digitalmars-d mailing list