www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Strange rbtree behaviour

reply Arafel <er.krali gmail.com> writes:
Hi!

I am seeing what it seems to me a very strange behavior with 
rbtrees:

---
import std.stdio;
import std.container.rbtree;

public struct A {
	public int i;
	
	public this (int _i) {
		this.i = _i;
	}
}

public struct B {
	public auto col = new RedBlackTree!(A,"a.i < b.i");
}

void main() {
	B b1;
	B b2;
	b1.col.insert(A(5));
	
	static assert(&b1 != &b2);
	assert(&(b1.col) != &(b2.col));
	writeln(b1.col.length, " ", b2.col.length);
	writeln(b1.col[], " ", b2.col[]);
}
---

I get the (to me) surprising result of:

---
1 1
[A(5)] [A(5)]
---

Is this the expected result? If so, why? I'd have expected two 
new empty but different rbtrees to be created, and in fact that's 
what happen if I declare them as local variables inside main().

In this case, two different rbtrees are indeed created (as seen 
with the assertion), but they apparently point to the same 
underlying data...

Thanks!
Jul 07 2016
next sibling parent reply Lodovico Giaretta <lodovico giaretart.net> writes:
On Thursday, 7 July 2016 at 09:33:38 UTC, Arafel wrote:

 Hi!

 I am seeing what it seems to me a very strange behavior with 
 rbtrees:

 ---
 import std.stdio;
 import std.container.rbtree;

 public struct A {
 	public int i;
 	
 	public this (int _i) {
 		this.i = _i;
 	}
 }

 public struct B {
 	public auto col = new RedBlackTree!(A,"a.i < b.i");
 }

 void main() {
 	B b1;
 	B b2;
 	b1.col.insert(A(5));
 	
 	static assert(&b1 != &b2);
 	assert(&(b1.col) != &(b2.col));
 	writeln(b1.col.length, " ", b2.col.length);
 	writeln(b1.col[], " ", b2.col[]);
 }
 ---

 I get the (to me) surprising result of:

 ---
 1 1
 [A(5)] [A(5)]
 ---

 Is this the expected result? If so, why? I'd have expected two 
 new empty but different rbtrees to be created, and in fact 
 that's what happen if I declare them as local variables inside 
 main().

 In this case, two different rbtrees are indeed created (as seen 
 with the assertion), but they apparently point to the same 
 underlying data...

 Thanks!


Initially it looks very surprising, but then if you add 
`writeln(B.init.col[]);` you can easily find out what's going on.

And I'm quite sure it's expected behaviour.
Jul 07 2016
parent reply Lodovico Giaretta <lodovico giaretart.net> writes:
On Thursday, 7 July 2016 at 09:40:57 UTC, Lodovico Giaretta wrote:

 Initially it looks very surprising, but then if you add 
 `writeln(B.init.col[]);` you can easily find out what's going 
 on.

 And I'm quite sure it's expected behaviour.


An RBTree is just a pointer to the memory containing the actual 
tree. Your `col`s have different addresses because they are 
different copies of the same pointer. If you cast `col` to a 
pointer and write the address it's pointing at, you find out that 
the two structures are pointing to the same memory.

This is because assignments used in a structure declaration are 
not re-executed for each instantiation. Instead, they are 
executed one to create the `.init` member of the type, which is 
then bit-copied on every other instance. So your code does this:

B.init.col = new RBTree(...);

B b1 = B.init;
B b2 = B.init;
Jul 07 2016
parent Arafel <er.krali gmail.com> writes:
On Thursday, 7 July 2016 at 09:46:25 UTC, Lodovico Giaretta wrote:

 On Thursday, 7 July 2016 at 09:40:57 UTC, Lodovico Giaretta 
 wrote:

 Initially it looks very surprising, but then if you add 
 `writeln(B.init.col[]);` you can easily find out what's going 
 on.

 And I'm quite sure it's expected behaviour.


 An RBTree is just a pointer to the memory containing the actual 
 tree. Your `col`s have different addresses because they are 
 different copies of the same pointer. If you cast `col` to a 
 pointer and write the address it's pointing at, you find out 
 that the two structures are pointing to the same memory.

 This is because assignments used in a structure declaration are 
 not re-executed for each instantiation. Instead, they are 
 executed one to create the `.init` member of the type, which is 
 then bit-copied on every other instance. So your code does this:

 B.init.col = new RBTree(...);

 B b1 = B.init;
 B b2 = B.init;


Still, if I make B a class instead of a struct (and instantiate 
using new), I get the same result... Do classes behave the same 
as structs in this regard? I mean, static initializers compared 
to "this" (now that I write it, I guess the word "static" gives 
an important clue...).

Anyway, glad to know what was happening... still a bit 
unintuitive, but I guess it makes sense after all.

Thanks!!
Jul 07 2016
prev sibling parent reply Jonathan M Davis via Digitalmars-d-learn writes:
On Thursday, July 07, 2016 09:33:38 Arafel via Digitalmars-d-learn wrote:

 public struct B {
   public auto col = new RedBlackTree!(A,"a.i < b.i");
 }


If you default-initialize a member of a struct, then every instance of that
struct gets that exact same value. In the case of a value type, this results
in completely distinct values, but in the case of a reference type, it's
shared across instances. If you want each struct to have its own
RedBlackTree for col, then you're going to need to use a constructor. And
since there are no default constructors for structs, and you don't want a
constructor that takes an argument, then you should probably use a factory
function. e.g.

struct B
{
    static B factory()
    {
        B b;
        b.col = new typeof(col);
        return b;
    }

    RedBlackTree!(A, "a.i < b.i") col;
}

void main()
{
    auto b = B.factory();
}

- Jonathan M Davis
Jul 07 2016
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 07/07/2016 02:57 AM, Jonathan M Davis via Digitalmars-d-learn wrote:


 then you should probably use a factory function. e.g.


And name that function "opCall" and you have a non-constructor that 
supports the default-constructor syntax. :p

     static B opCall()
     {
         // ...
     }

     auto b = B();

Ali
Jul 07 2016
parent Jonathan M Davis via Digitalmars-d-learn writes:
On Thursday, July 07, 2016 05:13:56 Ali Çehreli via Digitalmars-d-learn wrote:

 On 07/07/2016 02:57 AM, Jonathan M Davis via Digitalmars-d-learn wrote:
  > then you should probably use a factory function. e.g.

 And name that function "opCall" and you have a non-constructor that
 supports the default-constructor syntax. :p

      static B opCall()
      {
          // ...
      }

      auto b = B();


That only works as long as there are no constructors. As soon as you have a
constructor, a struct can't have a static opCall with no parameters. So,
while it might be visually appealing, I'm not sure that it's actually a good
idea to do it. Even if you didn't need a constructor now, so it worked, if
you needed to add one later, you couldn't without breaking code. So, it's
probably better to use an explicit factory function rather than a static
opCall.

- Jonathan M Davis
Jul 07 2016