www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Empty associative array

reply deadalnix <deadalnix gmail.com> writes:
In D associative array have reference semantic. Well they do, 
except when they are initially created, in which case they are 
null. For instance:

```d
int[int] a1;
int[int] a2 = a1; // a1 is null, so a2 is null too.

a2[3] = 3; // a2 is initialized to something else than null here.
writeln(a1.length); // prints 0.

a1 = a2; // a1 and a2 now point to the same reference.
a2[4] = 4;

writeln(a1.length); // prints 2. a1 was modified with a2 now that 
they point to the same thing.
```

There is an immediate problem with this: how does one gets an 
empty, but non null, associative array?

I find myself in a situation where I use an AA to cache some 
computation results, and this cache might be necessary in a 
couple of places in the application. It works great, unless the 
cache is initially empty, in which case, every location ends up 
with its own cache, defeating the whole point of caching these 
results to begin with.
Aug 09
next sibling parent ikod <igor.khasilev gmail.com> writes:
On Monday, 9 August 2021 at 12:16:44 UTC, deadalnix wrote:

 There is an immediate problem with this: how does one gets an 
 empty, but non null, associative array?
It would be nice to have reserve(capacity) call in AA API, if ia it not already there.
Aug 09
prev sibling next sibling parent Dukc <ajieskola gmail.com> writes:
On Monday, 9 August 2021 at 12:16:44 UTC, deadalnix wrote:
 There is an immediate problem with this: how does one gets an 
 empty, but non null, associative array?
I think this ought to work for that: ```d int[int] empty = []; ``` However, compiler complains `Error: cannot have associative array key of void`.
Aug 09
prev sibling next sibling parent Stefan Koch <uplink.coder googlemail.com> writes:
On Monday, 9 August 2021 at 12:16:44 UTC, deadalnix wrote:
 In D associative array have reference semantic. Well they do, 
 except when they are initially created, in which case they are 
 null. For instance:

 [...]
You could use a global and/or pass by ref.
Aug 09
prev sibling next sibling parent reply Mike Parker <aldacron gmail.com> writes:
On Monday, 9 August 2021 at 12:16:44 UTC, deadalnix wrote:

 I find myself in a situation where I use an AA to cache some 
 computation results, and this cache might be necessary in a 
 couple of places in the application. It works great, unless the 
 cache is initially empty, in which case, every location ends up 
 with its own cache, defeating the whole point of caching these 
 results to begin with.
Do you mean you're passing the AA to those locations as a function parameter? In that case, it's no different from the behavior of dynamic arrays. The AA handle itself is not a reference, so you need to explicitly pass it by reference: ```d void func(ref int[int] aa) { aa[3] = 3; } void main() { int[int] aa; func(aa); assert(aa[3] == 10); } ```
Aug 09
next sibling parent Mike Parker <aldacron gmail.com> writes:
On Monday, 9 August 2021 at 12:46:19 UTC, Mike Parker wrote:
     assert(aa[3] == 10);
Derp... `assert(aa[3] == 3);`
Aug 09
prev sibling parent deadalnix <deadalnix gmail.com> writes:
On Monday, 9 August 2021 at 12:46:19 UTC, Mike Parker wrote:
 Do you mean you're passing the AA to those locations as a 
 function parameter? In that case, it's no different from the 
 behavior of dynamic arrays. The AA handle itself is not a 
 reference, so you need to explicitly pass it by reference:

 ```d
 void func(ref int[int] aa) { aa[3] = 3; }

 void main()
 {
     int[int] aa;
     func(aa);
     assert(aa[3] == 10);
 }
 ```
This is cache, I need to keep it around. passing it by ref to function isn't going to cut it. There are other solution, such as wrapping the AA into a struct a newing it, but this is introducing extra indirection for no good reasons.
Aug 09
prev sibling next sibling parent jfondren <julian.fondren gmail.com> writes:
On Monday, 9 August 2021 at 12:16:44 UTC, deadalnix wrote:
 In D associative array have reference semantic. Well they do, 
 except when they are initially created, in which case they are 
 null. For instance:

 ```d
 int[int] a1;
 int[int] a2 = a1; // a1 is null, so a2 is null too.

 a2[3] = 3; // a2 is initialized to something else than null 
 here.
 writeln(a1.length); // prints 0.
 ```
```d class Cache { int[int] aa; } unittest { auto a1 = new Cache; auto a2 = a1; a2.aa[3] = 3; assert(a1.aa.length == 1); } ```
 I find myself in a situation where I use an AA to cache some 
 computation results, and this cache might be necessary in a 
 couple of places in the application.
You want reference semantics (class) and an AA (put it in the class).
Aug 09
prev sibling next sibling parent reply Dukc <ajieskola gmail.com> writes:
On Monday, 9 August 2021 at 12:16:44 UTC, deadalnix wrote:
 It works great, unless the cache is initially empty, in which 
 case, every location ends up with its own cache, defeating the 
 whole point of caching these results to begin with.
It turns out the dark corners with empty static arrays don't stop with initialization. One can inefficiently hack an empty static array: ```d import std; safe: int[int] emptyAA; void setEmptyAA() { alias Key = int, Value = int; emptyAA = [Key.init: Value.init]; auto remover = emptyAA; remover.remove(Key.init); } void main() { setEmptyAA; int[int] a = emptyAA; int[int] b = a; b[5] = 3; a.writeln; //[5:3] } ``` ...however, if you initialize `a` with `emptyAA.dup` it will again be `null`! I believe we can only conclude that empty AA's are not supposed to rely on being non-`null`. Sorry Walter - in my eyes this is a design failure.
Aug 09
next sibling parent reply jfondren <julian.fondren gmail.com> writes:
On Monday, 9 August 2021 at 13:10:53 UTC, Dukc wrote:
 ```d
 import std;

  safe:

 int[int] emptyAA;

 void setEmptyAA()
 { alias Key = int, Value = int;

   emptyAA = [Key.init: Value.init];
   auto remover = emptyAA;
   remover.remove(Key.init);
 }

 void main()
 { setEmptyAA;
   int[int] a = emptyAA;
   int[int] b = a;

   b[5] = 3;

   a.writeln; //[5:3]
 }
 ```

 ...however, if you initialize `a` with `emptyAA.dup` it will 
 again be `null`!
You get this with dynamic arrays as well. ```d unittest { int[] a; assert(a == []); assert(a is null); a ~= 1; a = a[1 .. $]; assert(a == []); assert(a !is null); assert(a.length == 0); a = a.dup; assert(a is null); } ```
 I believe we can only conclude that empty AA's are not supposed 
 to rely on being non-`null`. Sorry Walter - in my eyes this is 
 a design failure.
They're very convenient, scripting-language-like types, and this comes with a few caveats that can be emphasized in tutorials and learned. If the convenience isn't worth the caveats for you, there's std.container.array and perhaps https://code.dlang.org/packages/bcaa
Aug 09
parent Dukc <ajieskola gmail.com> writes:
On Monday, 9 August 2021 at 13:21:06 UTC, jfondren wrote:
 You get this with dynamic arrays as well.

 They're very convenient, scripting-language-like types, and 
 this comes with a few caveats that can be emphasized in 
 tutorials and learned. If the convenience isn't worth the 
 caveats for you, there's std.container.array and perhaps 
 https://code.dlang.org/packages/bcaa
I believe that's good design with dynamic arrays, because their pointer and length data are passed by copy. Testing a dynamic array against `null` means, in practice, testing whether it's `.ptr` property points to `null`. There is no such thing as a dynamic array that is itself `null` (unless it has `ref` storage class). Associative arrays, however, are passed around by reference. When we test those against `null` we test whether we have an associative array at all, not whether that associative array points to any memory area.
Aug 09
prev sibling parent deadalnix <deadalnix gmail.com> writes:
On Monday, 9 August 2021 at 13:10:53 UTC, Dukc wrote:
 ...however, if you initialize `a` with `emptyAA.dup` it will 
 again be `null`!

 I believe we can only conclude that empty AA's are not supposed 
 to rely on being non-`null`. Sorry Walter - in my eyes this is 
 a design failure.
I don't think this is a much of a problem, after all, .dup is meant to create a new identity, and you can't really rely on that identity being anything specific. That being said, yes, there is clearly some level of snafu involved in that design.
Aug 09
prev sibling parent Steven Schveighoffer <schveiguy gmail.com> writes:
On 8/9/21 8:16 AM, deadalnix wrote:

 There is an immediate problem with this: how does one gets an empty, but 
 non null, associative array?
There isn't a "good" way to do this. The only way I know is: ```d a1[0] = 0; a1.clear(); ``` This will leave an empty, but allocated AA. It would be pretty trivial to add this feature (make me an empty but allocated AA). Probably 2 lines of code in druntime. People have tried in the past to allow reserving memory for an AA, but it's not a trivial task (unlike this). I think there is an issue report somewhere, let me see... No didn't find one. -Steve
Aug 09