www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Accessing Dynamic Arrays - best approach?

reply AEon <AEon_member pathlink.com> writes:
Playing around with dynamic arrays like:

    int[] d;   // Dynamic Array has no size! Just declared, not initialized
yet?!
               // -> d.length = 0 

    d[10] = 3; // Error: Access Violation

but with a "dummy call":    

    d.length = 1;

suddenly I can access elements in the array, even though I am exceeding the
length limits?

    d[10] = 3; // Works!

I would have expected that a "d.length = 11;" is required for "d[10] = 3;" to
work?


Put differently, once a dynamic array has been declared (int[] d;), how does one
go about to let you access elements in the array?


Let's say you have a dynamic array, and you want to copy 10 numbers (that are
calculated one by one and do *not* already exist) into it. Would you do this?:

    int[] d;
    d.length = 1;  // First call, dynamic array would only need to hold 1
number
    d[0] = 3;      // 1st number

next number:

    d.length ++;
    d[1] = 8;     // 2nd number

IOW would one resize (re-length) the dynamic array every time?

Obviously one could probably upsize the array in larger steps, e.g. if you know
you will have 1000 numbers, you could "d.length = d.length + 100;", but would
the above be the "good" way to go?

AEon
Mar 15 2005
next sibling parent reply "Regan Heath" <regan netwin.co.nz> writes:
On Tue, 15 Mar 2005 22:07:34 +0000 (UTC), AEon <AEon_member pathlink.com>  
wrote:
 Playing around with dynamic arrays like:

     int[] d;   // Dynamic Array has no size! Just declared, not  
 initialized
 yet?!
                // -> d.length = 0

     d[10] = 3; // Error: Access Violation

 but with a "dummy call":

     d.length = 1;

 suddenly I can access elements in the array, even though I am exceeding  
 the
 length limits?

     d[10] = 3; // Works!

I get an "ArrayBoundsError" when I compile either of these examples with no flags, and "Access Violation" if I compile them with -release.
 I would have expected that a "d.length = 11;" is required for "d[10] =  
 3;" to
 work?

It is.
 Put differently, once a dynamic array has been declared (int[] d;), how  
 does one
 go about to let you access elements in the array?

1. set the length. 2. use [],for,while,do,foreach to access elements.
 Let's say you have a dynamic array, and you want to copy 10 numbers  
 (that are
 calculated one by one and do *not* already exist) into it. Would you do  
 this?:

     int[] d;
     d.length = 1;  // First call, dynamic array would only need to hold 1
 number
     d[0] = 3;      // 1st number

 next number:

     d.length ++;
     d[1] = 8;     // 2nd number

 IOW would one resize (re-length) the dynamic array every time?

 Obviously one could probably upsize the array in larger steps, e.g. if  
 you know
 you will have 1000 numbers, you could "d.length = d.length + 100;", but  
 would
 the above be the "good" way to go?

If you know you need 1000 numbers, you can write: d.length = 1000; foreach(int i, inout int v; d) { //i is the index into the array v = //calculation goes here } Regan
Mar 15 2005
parent reply AEon <AEon_member pathlink.com> writes:
Regan Heath says...

 Playing around with dynamic arrays like:

     int[] d;
     d[10] = 3; // Error: Access Violation

 but with a "dummy call":

     d.length = 1;

 suddenly I can access elements in the array, even though I am exceeding  
 the length limits?

     d[10] = 3; // Works!

I get an "ArrayBoundsError" when I compile either of these examples with no flags, and "Access Violation" if I compile them with -release.

Just tested this again. Using any of these parameter sets in my makefile: DFLAGS=-I. DFLAGS=-O -I. DFLAGS=-w -O -I. DFLAGS=-w -O -inline -I. yields the "Error: ArrayBoundsError test(266)" you mentioned. DFLAGS=-w -O -release -inline -I. compiles cleanly for me. And running the test program will show the proper values. No crash. This seems to mean that when developping, one should *not* use the -release switch since that "hides" certain bugs, e.g. turns off full checking?
 I would have expected that a "d.length = 11;" is required for "d[10] =  
 3;" to work?


Good... the above made me nervous, and I was starting to wonder if array boundary checks are actually done.
 Put differently, once a dynamic array has been declared (int[] d;), how  
 does one go about to let you access elements in the array?

2. use [],for,while,do,foreach to access elements.

Ok... so setting the length is a *must*. AEon
Mar 15 2005
parent reply "Regan Heath" <regan netwin.co.nz> writes:
On Tue, 15 Mar 2005 22:59:14 +0000 (UTC), AEon <AEon_member pathlink.com>  
wrote:
 Playing around with dynamic arrays like:

     int[] d;
     d[10] = 3; // Error: Access Violation

 but with a "dummy call":

     d.length = 1;

 suddenly I can access elements in the array, even though I am exceeding
 the length limits?

     d[10] = 3; // Works!

I get an "ArrayBoundsError" when I compile either of these examples with no flags, and "Access Violation" if I compile them with -release.

Just tested this again. Using any of these parameter sets in my makefile: DFLAGS=-I. DFLAGS=-O -I. DFLAGS=-w -O -I. DFLAGS=-w -O -inline -I. yields the "Error: ArrayBoundsError test(266)" you mentioned. DFLAGS=-w -O -release -inline -I. compiles cleanly for me. And running the test program will show the proper values. No crash.

Can you attach your test code. I still get "Access Violation". I suspect it's a 'fluke', as in the memory referenced by d[10] just happens to be yours to modify, perhaps part of another variable.
 This seems to mean that when developping, one should *not* use
 the -release switch since that "hides" certain bugs, e.g. turns off full
 checking?

Yes. -release disables the runtime array bounds checks, and others.
 I would have expected that a "d.length = 11;" is required for "d[10] =
 3;" to work?


Good... the above made me nervous, and I was starting to wonder if array boundary checks are actually done.

Only when -release is not used.
 Put differently, once a dynamic array has been declared (int[] d;), how
 does one go about to let you access elements in the array?

2. use [],for,while,do,foreach to access elements.

Ok... so setting the length is a *must*.

Sort of, yes.. you can get an array with a valid length without setting it explicitly, eg. int[] original = "12345"; //original.length is 5 int[] new; new = original.dup; //new.length is now 5 new = original[0..3] //new.length is now 3 //note: new[1] = 5; //will crash on linux, but not windows, as 'new' slices 'original' which is static. Regan
Mar 15 2005
next sibling parent "Regan Heath" <regan netwin.co.nz> writes:
On Wed, 16 Mar 2005 12:08:27 +1300, Regan Heath <regan netwin.co.nz> wrote:
 int[] original = "12345"; //original.length is 5
 int[] new;

 new = original.dup;   //new.length is now 5
 new = original[0..3]  //new.length is now 3

 //note:
 new[1] = 5; //will crash on linux, but not windows, as 'new' slices  
 'original' which is static.

To clarify: new = original.dup; new[1] = 5; will not crash. But: new = original[0..3]; new[1] = 5; might, depending on OS. Regan
Mar 15 2005
prev sibling parent reply AEon <AEon_member pathlink.com> writes:
Regan Heath says...

Can you attach your test code. I still get "Access Violation". I suspect  
it's a 'fluke', as in the memory referenced by d[10] just happens to be  
yours to modify, perhaps part of another variable.

<code> import std.c.stdio; int main (char[][] args) { printf("\n Clearing dynamic arrays int[] d and d = null\n\n"); int[] d; printf(" d.length = %d (int[] d)\n", d.length); d.length = 1; printf(" d.length = %d (d.length = 11)\n", d.length); printf(" d[10] = %d (inits values!)\n", d[10]); d[10] = 3; printf(" d[10] = %d (d[10] = 3)\n", d[10]); d = null; // printf(" d[10] = %d (d = null)\n", d[10]); // Error: Access Violation return 0; } </code> (dmd 0.118, windows)
dmd -w -release test3.d

test3

Clearing dynamic arrays int[] d and d = null d.length = 0 (int[] d) d.length = 1 (d.length = 11) d[10] = 0 (inits values!) d[10] = 3 (d[10] = 3) As you can see d[10] access works when -release is turned on.
dmd -w test3.d

test3

Clearing dynamic arrays int[] d and d = null d.length = 0 (int[] d) d.length = 1 (d.length = 11) Error: ArrayBoundsError test3.d(12) A "normal" compile on the other hand shows the boundary violation.
Sort of, yes.. you can get an array with a valid length without setting it  
explicitly, eg.

int[] original = "12345"; //original.length is 5
int[] new;

new = original.dup;   //new.length is now 5
new = original[0..3]  //new.length is now 3

The length of 5 to me reads a bit strange, I would have assumed 1. And that you can assign a string literal (what that the right term) to an int array is also strange. Will test the above some more. BTW since IIRC "new" is a keyword, using it as a variable is kinda evil :) AEon
Mar 15 2005
parent "Regan Heath" <regan netwin.co.nz> writes:
On Tue, 15 Mar 2005 23:41:35 +0000 (UTC), AEon <AEon_member pathlink.com>  
wrote:
 Regan Heath says...

 Can you attach your test code. I still get "Access Violation". I suspect
 it's a 'fluke', as in the memory referenced by d[10] just happens to be
 yours to modify, perhaps part of another variable.

<code> import std.c.stdio; int main (char[][] args) { printf("\n Clearing dynamic arrays int[] d and d = null\n\n"); int[] d; printf(" d.length = %d (int[] d)\n", d.length); d.length = 1; printf(" d.length = %d (d.length = 11)\n", d.length); printf(" d[10] = %d (inits values!)\n", d[10]); d[10] = 3; printf(" d[10] = %d (d[10] = 3)\n", d[10]); d = null; // printf(" d[10] = %d (d = null)\n", d[10]); // Error: Access Violation return 0; } </code> (dmd 0.118, windows)
 dmd -w -release test3.d

 test3

Clearing dynamic arrays int[] d and d = null d.length = 0 (int[] d) d.length = 1 (d.length = 11) d[10] = 0 (inits values!) d[10] = 3 (d[10] = 3) As you can see d[10] access works when -release is turned on.

I now get the same results as you did. I would call this 'undefined' behaviour. Perhaps Walter can shed some light? Perhaps arrays allocate a minimum size for efficiency?
 Sort of, yes.. you can get an array with a valid length without setting  
 it
 explicitly, eg.

 int[] original = "12345"; //original.length is 5
 int[] new;

 new = original.dup;   //new.length is now 5
 new = original[0..3]  //new.length is now 3

The length of 5 to me reads a bit strange, I would have assumed 1. And that you can assign a string literal (what that the right term) to an int array is also strange.

Doh! sorry, the code above will never compile. Will test the above some more. BTW since IIRC "new" is a
 keyword, using
 it as a variable is kinda evil :)

Yet another reason my code is illegal. Let me try again: char[] original = "12345"; char[] a; a = original.dup; a = original[0..3]; (same comments as before) Regan
Mar 15 2005
prev sibling next sibling parent Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
AEon wrote:
 Playing around with dynamic arrays like:
 
     int[] d;   // Dynamic Array has no size! Just declared, not initialized
 yet?!
                // -> d.length = 0 
 
     d[10] = 3; // Error: Access Violation
 
 but with a "dummy call":    
 
     d.length = 1;
 
 suddenly I can access elements in the array, even though I am exceeding the
 length limits?
 
     d[10] = 3; // Works!

You're correct that this code is not valid. You're obviously compiling with -release, because, otherwise, D would do bounds checking for you and you would get an ArrayBoundsError. My guess why it works is that D has allocated some memory for the array, and while the allocation is small, theOScan only do access protection on a page level. Thus, when you overflow the array, you are reading memory which you are not supposed to touch - but there is no way to force you not to.
Mar 15 2005
prev sibling next sibling parent Derek Parnell <derek psych.ward> writes:
On Tue, 15 Mar 2005 22:07:34 +0000 (UTC), AEon wrote:

 Playing around with dynamic arrays like:
 
     int[] d;   // Dynamic Array has no size! Just declared, not initialized
 yet?!
                // -> d.length = 0 
 
     d[10] = 3; // Error: Access Violation

Because at this point your array does not point to any RAM.
 but with a "dummy call":    
 
     d.length = 1;

By doing this, D allocates at least enough RAM to hold one element and sets the array to point to that RAM.
 suddenly I can access elements in the array, even though I am exceeding the
 length limits?
 
     d[10] = 3; // Works!
 
 I would have expected that a "d.length = 11;" is required for "d[10] = 3;" to
 work?

If you compile with -release, DMD turns off checking for bad index values. It instead assumes you know what you are doing. By luck, you got to access some RAM that your application owned, but it wasn't necessarily owned by the array itself.
 Put differently, once a dynamic array has been declared (int[] d;), how does
one
 go about to let you access elements in the array?
 
 Let's say you have a dynamic array, and you want to copy 10 numbers (that are
 calculated one by one and do *not* already exist) into it. Would you do this?:
 
     int[] d;
     d.length = 1;  // First call, dynamic array would only need to hold 1
 number
     d[0] = 3;      // 1st number
 
 next number:
 
     d.length ++;
     d[1] = 8;     // 2nd number
 
 IOW would one resize (re-length) the dynamic array every time?

You could, but that is not the way I'd do it. I would do either ... d.length = 10; d[0] = 3; d[1] = 8; d[3] = ... etc... or d ~= 3; d ~= 8; d ~= ... etc ...
 Obviously one could probably upsize the array in larger steps, e.g. if you know
 you will have 1000 numbers, you could "d.length = d.length + 100;", but would
 the above be the "good" way to go?

You would probably select the method that made more sense for the application. Presetting the length is fine if you know how many items you are adding, but the concatenation method may be more useful when you don't know how many items there will be. -- Derek Melbourne, Australia 16/03/2005 11:59:08 AM
Mar 15 2005
prev sibling parent reply =?ISO-8859-1?Q?Anders_F_Bj=F6rklund?= <afb algonet.se> writes:
AEon wrote:

 next number:
 
     d.length ++;
     d[1] = 8;     // 2nd number

As a side note, "d.length++;" is not allowed (since you *might* use it to hurt yourself...) One must do "d.length = d.length + 1;" instead. Or just use "d ~= 8;", which is a lot easier ? --anders
Mar 16 2005
parent reply AEon <AEon_member pathlink.com> writes:
Derek Parnell says...

   d ~= 3;
   d ~= 8;
   d ~= ... etc ...

You would probably select the method that made more sense for the
application. Presetting the length is fine if you know how many 
items you are adding, but the concatenation method may be more 
useful when you don't know how many items there will be.

Thanx for the ~= example. I have read about it but was not aware that would work when adding array elements. Just continued reading the documentation, and found an "optimized" example: int[] array; array.length = 100; // guess for (i = 0; 1; i++) { c = getinput(); if (!c) break; if (i == array.length) array.length = array.length * 2; array[i] = c; } array.length = i; // Resize to actual array size! And indeed the manual frowns on, doing "inefficient" array.length++; calls. Regan,
 int[] original = "12345"; //original.length is 5
 ...



Glad, I am not totally wacking out :)
Let me try again:

    char[] original = "12345";
    char[] a;

    a = original.dup;
    a = original[0..3];

I have read a scary section in the manual under Arrays, Setting Dynamic Array Length... where it seems to turn out that slicing can lead to code that will not be fully predicatble. In the above example, if you where to change elements in a a = original[0..3]; a[2] = 'd'; then original[2] could be 'd' or it could still be '3'. Because when slicing it seems to be not clear if a is actually a seperate copy of original or just a "reference". To ensure that you are manipulating a copy, the manual suggests one use .dup: a = original.dup; a[2] = 'd'; -> original[2] uneffected. This is only how I understand things from first reading, I may have missunderstood something. I had the feeling that the example in Arrays, Setting Dynamic Array Length, had a mistake, or at least I did not understand what was meant: char[] a = new char[20]; char[] b = a[0..10]; char[] c = a[10..20]; b.length = 15; // always resized in place because it is sliced // from a[] which has enough memory for 15 chars b[11] = 'x'; // a[15] and c[5] are also affected ... Should that not read?: b[11] = 'x'; // a[11] and c[1] are also affected Visualization of the memory: var element number 1111111111 a 01234567890123456789 b 0123456789 c 0123456789 With this behavior I would assume that slices are probably wonderful as convenient "aliases" to (in this example) substrings, but should not be used to manipulate the original arrays? anders,
     d.length ++;
     d[1] = 8;     // 2nd number


As a side note, "d.length++;" is not allowed
(since you *might* use it to hurt yourself...)

One must do "d.length = d.length + 1;" instead.
Or just use "d ~= 8;", which is a lot easier ?

Aha... good to know! AEon
Mar 16 2005
next sibling parent reply "Unknown W. Brackets" <unknown simplemachines.org> writes:
 I have read a scary section in the manual under Arrays, Setting 
 Dynamic Array Length... where it seems to turn out that slicing can 
 lead to code that will not be fully predicatble. In the above example, 
 if you where to change elements in a
 
     a = original[0..3];
     a[2] = 'd';
 
 then original[2] could be 'd' or it could still be '3'. Because when 
 slicing it seems to be not clear if a is actually a seperate copy of 
 original or just a "reference". To ensure that you are manipulating a 
 copy, the manual suggests one  use .dup:

I didn't see anything "scary" or "unclear". If you use a slice, you get the memory, not a copy of it. If you use .dup, you get a copy. Sometimes you don't want a copy - imagine: if (str[0 .. 7] == "http://") ... Do you want to actually allocate more memory for that, or are you happy with the comparison as is?
 With this behavior I would assume that slices are probably wonderful 
 as convenient "aliases" to (in this example) substrings, but should 
 not be used to manipulate the original arrays? 

Why not? What if you did this: char[] str = "test<script>"; int i = find(str, "<script>"); str[i .. i + 8] = ' '; Doesn't it make sense, there, to modify in place? Faster than making a copy, modifying it, and then replacing the old, no? -[Unknown]
Mar 16 2005
parent reply AEon <AEon_member pathlink.com> writes:
Unknown W. Brackets says...

I didn't see anything "scary" or "unclear".  If you use a slice, you get 
the memory, not a copy of it.  If you use .dup, you get a copy. 

Well it had surprised me, would have been a better way of putting it.
Sometimes you don't want a copy - imagine:

if (str[0 .. 7] == "http://")
    ...

Do you want to actually allocate more memory for that, or are you happy 
with the comparison as is?

Ah... indeed.
 With this behavior I would assume that slices are probably wonderful 
 as convenient "aliases" to (in this example) substrings, but should 
 not be used to manipulate the original arrays? 

Why not? What if you did this: char[] str = "test<script>"; int i = find(str, "<script>"); str[i .. i + 8] = ' '; Doesn't it make sense, there, to modify in place? Faster than making a copy, modifying it, and then replacing the old, no?

Ahem :)... yes it does make sense. But I had only been thinking of working with "copies" and manipulating those, my mistake. When directly manipulating the "original" strings via slices, that would indeed be predicatable in outcome and useful. Thanx for the real world examples. Regan,
It appears someone else agreed also:
http://www.prowiki.org/wiki4d/wiki.cgi?DocComments/Arrays

Indeed. Thanx for the link.
If you find any other possible typos you can amend them here:
http://www.prowiki.org/wiki4d/wiki.cgi?DocComments

Hmmm... I have trouble finding some link/button to actually submit something new?! I use the Firefox browser, could that be the problem? AEon
Mar 16 2005
parent reply "Regan Heath" <regan netwin.co.nz> writes:
On Wed, 16 Mar 2005 12:20:24 +0000 (UTC), AEon <AEon_member pathlink.com>  
wrote:
 It appears someone else agreed also:
 http://www.prowiki.org/wiki4d/wiki.cgi?DocComments/Arrays

Indeed. Thanx for the link.
 If you find any other possible typos you can amend them here:
 http://www.prowiki.org/wiki4d/wiki.cgi?DocComments

Hmmm... I have trouble finding some link/button to actually submit something new?! I use the Firefox browser, could that be the problem?

At the bottom of each page, i.e. http://www.prowiki.org/wiki4d/wiki.cgi?DocComments/Arrays there is and 'Edit' link and als 'Edit text of this page'. before you can do that you need to go to preferences and enter your name, so it can track who changed what. Regan
Mar 16 2005
parent AEon <AEon_member pathlink.com> writes:
Regan Heath says...

At the bottom of each page, i.e.
http://www.prowiki.org/wiki4d/wiki.cgi?DocComments/Arrays

there is and 'Edit' link and als 'Edit text of this page'.
before you can do that you need to go to preferences and enter your name,  
so it can track who changed what.

Thanx... sigh, need to check my eyes ;) AEon
Mar 16 2005
prev sibling parent reply "Regan Heath" <regan netwin.co.nz> writes:
On Wed, 16 Mar 2005 10:18:26 +0000 (UTC), AEon <AEon_member pathlink.com>  
wrote:
 int[] original = "12345"; //original.length is 5
 ...



Glad, I am not totally wacking out :)

No, that was me :)
 Let me try again:

    char[] original = "12345";
    char[] a;

    a = original.dup;
    a = original[0..3];

I have read a scary section in the manual under Arrays, Setting Dynamic Array Length... where it seems to turn out that slicing can lead to code that will not be fully predicatble. In the above example, if you where to change elements in a a = original[0..3]; a[2] = 'd'; then original[2] could be 'd' or it could still be '3'.

original[2] will be 'd'. This is guaranteed IIRC. When you type "a = " you always make a reference to the original data. However, if you said: char[] original = "12345"; char[] a; a.length = 3; a[0..3] = original[0..3]; it would copy the values from 'original' to 'a'.
 Because when
 slicing it seems to be not clear if a is actually a seperate copy of
 original or just a "reference".

It depends on what you say, "a = " always creates a reference, but "a[x..y] = " always copies the data.
 To ensure that you are manipulating a
 copy, the manual suggests one  use .dup:

     a = original.dup;
     a[2] = 'd';
 -> original[2] uneffected.

Correct. dup creates a copy of the array or slice. eg. (note .dup on a slice) a = original[0..3].dup; a[2] = 'd' //original[2] unaffected
 This is only how I understand things from first reading, I may have
 missunderstood something.

There may be a few subtle things left to learn. I've tried to show them above.
 I had the feeling that the example in Arrays, Setting Dynamic Array
 Length, had a mistake, or at least I did not understand what was
 meant:

     char[] a = new char[20];
     char[] b = a[0..10];
     char[] c = a[10..20];

     b.length = 15;  // always resized in place because it is sliced
                     // from a[] which has enough memory for 15 chars
     b[11] = 'x';    // a[15] and c[5] are also affected
     ...

 Should that not read?:

     b[11] = 'x';    // a[11] and c[1] are also affected

I agree. I think it's a typo/mistake.
 Visualization of the memory:

     var  element number
                    1111111111
     a    01234567890123456789
     b    0123456789
     c              0123456789

 With this behavior I would assume that slices are probably wonderful
 as convenient "aliases" to (in this example) substrings, but should
 not be used to manipulate the original arrays?

You can use them to manipulate the originals, it can be quite handy. The rest of the time, make sure you use COW (Copy On Write), meaning every time you write to an array (which you're not intentionally using to manipulate the original) call "dup" first, then write to it. eg. char[] original = "12345"; char[] a; a = original; ..lots of code.. a = a.dup; a[2] = 'd'; Regan
Mar 16 2005
parent "Regan Heath" <regan netwin.co.nz> writes:
On Thu, 17 Mar 2005 00:20:44 +1300, Regan Heath <regan netwin.co.nz> wrote:
     char[] a = new char[20];
     char[] b = a[0..10];
     char[] c = a[10..20];

     b.length = 15;  // always resized in place because it is sliced
                     // from a[] which has enough memory for 15 chars
     b[11] = 'x';    // a[15] and c[5] are also affected
     ...

 Should that not read?:

     b[11] = 'x';    // a[11] and c[1] are also affected

I agree. I think it's a typo/mistake.

It appears someone else agreed also: http://www.prowiki.org/wiki4d/wiki.cgi?DocComments/Arrays If you find any other possible typos you can amend them here: http://www.prowiki.org/wiki4d/wiki.cgi?DocComments I believe Walter will eventually get round to making all these changes to the real docs? Regan
Mar 16 2005