## digitalmars.D.learn - Problem with associative arrays

• Piotr Szturmaj (11/11) Mar 19 2011 Shouldn't dynamic array be reference type?
• bearophile (19/21) Mar 19 2011 They are partially a reference type and partially a value :-)
• Mafi (29/38) Mar 19 2011 They are not 'perfect' references. There are pointer+length to/of memory...
• Piotr Szturmaj (4/4) Mar 19 2011 Thank you for your very complete answers :)
• Jesse Phillips (12/17) Mar 19 2011 What everyone else said, but you can get a pointer with 'in'
• Piotr Szturmaj (5/20) Mar 20 2011 Yes, I already used pointers but in other way:
• Jesse Phillips (3/9) Mar 20 2011 Depends on what you mean by "safe." In your example if 5 is not a key th...
• =?UTF-8?B?QWxpIMOHZWhyZWxp?= (32/37) Mar 19 2011 On the other hand, if the dynamic array is sharing a part of another
• Jonathan M Davis (15/60) Mar 19 2011 Yes. Dynamic arrays attempt to resize themselves efficiently, so they av...
```Shouldn't dynamic array be reference type?

uint[][uint] aa;
uint[] temp;

aa[5] = new uint[0];
temp = aa[5]; // copy uint[] reference
temp ~= 1;

assert(temp.length == 1 && temp[0] == 1); // pass
assert(aa[5].length == 1 && aa[5][0] == 1); // fail

Is this a bug?
```
Mar 19 2011
bearophile <bearophileHUGS lycos.com> writes:
```Piotr Szturmaj:

Shouldn't dynamic array be reference type?

They are partially a reference type and partially a value :-)
A D dynamic array is represented with a small struct 2-words long that contains
the pointer to the first item of the array and the length of the array (you are
able to read them with the .ptr and .length attributes). So when you copy a
dynamic array using temp=aa[5] you are copying this little struct. When you
perform the temp~=1 you are changing the length just of the copied struct, not
of the original aa[5] one (in D1 if temp~=1 induces a realloc then the pointer
too gets modified only in the temp struct. In D2 the situation is more complex,
unfortunately).

Is this a bug?

It's clearly a bug-prone characteristic of D2, but it's not a D2 bug, so it's a
bug in your code :-( I think future D2 lint tools will have to test for this
possible source of bugs too.

Keep in mind that D2 associative arrays have an even worse nature:

void test(int[int] arr, int x) {
arr[x] = x;
}
void main() {
int[int] d;
test(d, 0);
int[int] d0;
assert(d == d0);
d[1] = 1;
test(d, 2);
assert(d == [1: 1, 2: 2]);
}

Bye,
bearophile
```
Mar 19 2011
Mafi <mafi example.org> writes:
```Am 19.03.2011 17:29, schrieb Piotr Szturmaj:
Shouldn't dynamic array be reference type?

uint[][uint] aa;
uint[] temp;

aa[5] = new uint[0];
temp = aa[5]; // copy uint[] reference
temp ~= 1;

assert(temp.length == 1 && temp[0] == 1); // pass
assert(aa[5].length == 1 && aa[5][0] == 1); // fail

Is this a bug?

They are not 'perfect' references. There are pointer+length to/of memory.
If you just pass around these refences they reference the same memory.
If you change the reference in some way (eg appending, concating etc)
the memory could be reallocated.

int[] a, b;
a = [3,4,5];
b = a;
assert(a == b);
assert(a is b); //test for refence equality
//a and b now reference exactly the same memory
//concatening is guaranteed to reallocate
a = a ~ [6, 7];
assert(a == [3, 4, 5, 6, 7]);
assert(b == [3, 4, 5]);
// BUT these 3,4,5 are in different places in memeory
b[0] = 42;
assert(a == [3, 4, 5, 6, 7]);
// when slicing you know reference a subpart of the other array
b = a[0.. 3];
assert(b == [3, 4, 5]);
// changes of b will now be visible in a
// until a or b get reallocated
b[0] = 42;
assert(a == [42, 4, 5, 6, 7]);
assert(b == [42, 4, 5]);

Just one note: appending (ar ~= 1) differs from concating (ar = ar ~ 1)
that while the second is guanranteed to reallocate, about the first you
can't be sure. It depends on the GC.
```
Mar 19 2011
```Thank you for your very complete answers :)

I was trying to avoid multiple AA key lookups while appending many
elements to dynamic array. It's clear now, that with D2 semantics it's
better to first build an array and then assign it to AA.
```
Mar 19 2011
Jesse Phillips <jessekphillips+D gmail.com> writes:
```Piotr Szturmaj Wrote:

I was trying to avoid multiple AA key lookups while appending many
elements to dynamic array. It's clear now, that with D2 semantics it's
better to first build an array and then assign it to AA.

What everyone else said, but you can get a pointer with 'in'

void main() {
uint[][uint] aa;

aa[5] = new uint[0];
auto temp = 5 in aa; // copy uint[] reference
*temp ~= 1;

assert(temp.length == 1 && (*temp)[0] == 1); // pass
assert(aa[5].length == 1 && aa[5][0] == 1); // pass

}
```
Mar 19 2011
```Jesse Phillips wrote:
Piotr Szturmaj Wrote:

I was trying to avoid multiple AA key lookups while appending many
elements to dynamic array. It's clear now, that with D2 semantics it's
better to first build an array and then assign it to AA.

What everyone else said, but you can get a pointer with 'in'

void main() {
uint[][uint] aa;

aa[5] = new uint[0];
auto temp = 5 in aa; // copy uint[] reference
*temp ~= 1;

assert(temp.length == 1 && (*temp)[0] == 1); // pass
assert(aa[5].length == 1 && aa[5][0] == 1); // pass

}

Yes, I already used pointers but in other way:

uint[]* temp = &aa[5]; // copy uint[] reference

and it worked the same as using 'in'. However, I wasn't sure it's
completely safe.
```
Mar 20 2011
Jesse Phillips <jessekphillips+D gmail.com> writes:
```Piotr Szturmaj Wrote:

Yes, I already used pointers but in other way:

uint[]* temp = &aa[5]; // copy uint[] reference

and it worked the same as using 'in'. However, I wasn't sure it's
completely safe.

Depends on what you mean by "safe." In your example if 5 is not a key then a
Range violation will be thrown. In mine null will be returned.

Generally safety refers to not corrupting memory, and under that definition
both of these are safe. Under the definition of "will not crash" no solution is
safe.
```
Mar 20 2011
=?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
```On 03/19/2011 10:05 AM, Mafi wrote:
Am 19.03.2011 17:29, schrieb Piotr Szturmaj:
Shouldn't dynamic array be reference type?

Just one note: appending (ar ~= 1) differs from concating (ar = ar ~ 1)
that while the second is guanranteed to reallocate, about the first you
can't be sure. It depends on the GC.

On the other hand, if the dynamic array is sharing a part of another
array, extending the dynamic array always breaks the sharing and the
dynamic array is always relocated.

void main()
{
int[] a = [ 100, 200, 300 ];

// Three slices (aka dynamic arrays) to the first two elements
int[] s0 = a[0..2];
int[] s1 = a[0..2];
int[] s2 = a[0..2];

// They share the same first two elements
assert(s0.ptr == a.ptr);
assert(s1.ptr == a.ptr);
assert(s2.ptr == a.ptr);

// All of these operations break the sharing
++s0.length;
s1 ~= 42;
s2 = s2 ~ 43;

// Nothing happened to the original
assert(a == [ 100, 200, 300 ]);

// Because nobody is sharing anymore
assert(s0.ptr != a.ptr);
assert(s1.ptr != a.ptr);
assert(s1.ptr != s0.ptr);
assert(s2.ptr != a.ptr);
assert(s2.ptr != s0.ptr);
assert(s2.ptr != s1.ptr);
}

I forgot the name of the feature. Basically, no slice (aka dynamic
array) can extend into other elements and starts sharing them.

Ali
```
Mar 19 2011
Jonathan M Davis <jmdavisProg gmx.com> writes:
```On Saturday 19 March 2011 11:12:49 Ali =C3=87ehreli wrote:
On 03/19/2011 10:05 AM, Mafi wrote:
> Am 19.03.2011 17:29, schrieb Piotr Szturmaj:
>> Shouldn't dynamic array be reference type?
>=20
> Just one note: appending (ar ~=3D 1) differs from concating (ar =3D ar=

~ 1)
> that while the second is guanranteed to reallocate, about the first you
> can't be sure. It depends on the GC.
=20
On the other hand, if the dynamic array is sharing a part of another
array, extending the dynamic array always breaks the sharing and the
dynamic array is always relocated.
=20
void main()
{
int[] a =3D [ 100, 200, 300 ];
=20
// Three slices (aka dynamic arrays) to the first two elements
int[] s0 =3D a[0..2];
int[] s1 =3D a[0..2];
int[] s2 =3D a[0..2];
=20
// They share the same first two elements
assert(s0.ptr =3D=3D a.ptr);
assert(s1.ptr =3D=3D a.ptr);
assert(s2.ptr =3D=3D a.ptr);
=20
// All of these operations break the sharing
++s0.length;
s1 ~=3D 42;
s2 =3D s2 ~ 43;
=20
// Nothing happened to the original
assert(a =3D=3D [ 100, 200, 300 ]);
=20
// Because nobody is sharing anymore
assert(s0.ptr !=3D a.ptr);
assert(s1.ptr !=3D a.ptr);
assert(s1.ptr !=3D s0.ptr);
assert(s2.ptr !=3D a.ptr);
assert(s2.ptr !=3D s0.ptr);
assert(s2.ptr !=3D s1.ptr);
}
=20
I forgot the name of the feature. Basically, no slice (aka dynamic
array) can extend into other elements and starts sharing them.

Yes. Dynamic arrays attempt to resize themselves efficiently, so they avoid=
=20
reallocations where they can, but if resizing would cause two arrays to sha=
re=20
elements which they did not share before that resizing operation, then a=20
reallocation of the array being sized takes place, so they no longer share =
any=20
elements even if they did before.

Overall, the way that arrays work works really well, and it's really not al=
l=20
that hard to wrap your head around, but it can certainly be confusing at fi=
rst.

=2D Jonathan M Davis
```
Mar 19 2011