about dynamic array

classic Classic list List threaded Threaded
35 messages Options
12
Reply | Threaded
Open this post in threaded view
|

about dynamic array

spir ☣
Hello,



Where can one find information on types like dynamic array? Also, on funcs or procs that apply on them, like setLength & copy. If the answers to the following questions are somewhere, just tell me...

* Can one rely on the fact that setLength keeps existing data (in the range of the new size), both when up- and down-sizing? Or do my trials work only because the pointed memory has not yet been overwritten?

* How is resizing actually performed (is the data moved to a newly allocated area)?

* Does copy onto a dynamic array automatically resize (setLength), even if the target is greater than needed? (I would like no.)

* Can one set the first index where to copy on the target array? (eg to join 2 arrays into a greater one, or to extend an existing one that has free space at tail)

* Can one use copy from/to a *static* array? (If no, why not?)

* What other differences with static array, if any? (Aside the fact that one does not need to explicitely reallocate and copy on resizing.)



For Christmas:

* Can one add or remove an element --at the end? (And have the array behave accordingly.)

* Can one add or remove an element --anywhere? (And have the array behave accordingly.)

If the answers to last 2 questions is "only every 29th of februar", how can one have a "flexible" array? Is there something like that in stock? Would you implement it on top of dynamic array, or rather from scratch on top of static array (since the "dynamicity" does not seem very helpful)?



Denis
________________________________

vit esse estrany ☣

spir.wikidot.com
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: about dynamic array

Jonas Maebe-2

On 06 May 2010, at 11:39, spir ☣ wrote:

> Where can one find information on types like dynamic array? Also, on  
> funcs or procs that apply on them, like setLength & copy.

In the documentation: http://www.freepascal.org/docs-html/ref/refsu14.html

> * Can one rely on the fact that setLength keeps existing data (in  
> the range of the new size), both when up- and down-sizing?

Yes.

> * How is resizing actually performed (is the data moved to a newly  
> allocated area)?

That's implementation-defined.

> * Does copy onto a dynamic array automatically resize (setLength),  
> even if the target is greater than needed? (I would like no.)

Copy() creates a copy of the original dynamic array. If you assign the  
result afterwards to another dynamic array, that other dynamic array  
is finalised. The copy() operation itself has no idea about what you  
will do with the result.

> * Can one set the first index where to copy on the target array? (eg  
> to join 2 arrays into a greater one, or to extend an existing one  
> that has free space at tail)

See above.

> * Can one use copy from/to a *static* array? (If no, why not?)

No, simply because copy() is only defined for dynamic arrays.

> * What other differences with static array, if any? (Aside the fact  
> that one does not need to explicitely reallocate and copy on  
> resizing.)

Please read the monster thread that I just closed, rather than  
starting it all over again.

> For Christmas:
>
> * Can one add or remove an element --at the end? (And have the array  
> behave accordingly.)

Use setlength to increase/decrease the length by one and add/

> * Can one add or remove an element --anywhere? (And have the array  
> behave accordingly.)

Not trivially/efficiently. In general, if you want to do something  
like that you should use a linked list rather than an array. Arrays  
are notoriously inefficient (even if you use plain static arrays with  
move() and other low level operations) if you often have to insert/
delete elements in the middle.

> If the answers to last 2 questions is "only every 29th of februar",  
> how can one have a "flexible" array? Is there something like that in  
> stock? Would you implement it on top of dynamic array, or rather  
> from scratch on top of static array (since the "dynamicity" does not  
> seem very helpful)?

Don't use a hammer to tighten screws.


Jonas_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: about dynamic array

Michael Van Canneyt
In reply to this post by spir ☣


On Thu, 6 May 2010, spir ☣ wrote:

> Hello,
>
>
>
> Where can one find information on types like dynamic array? Also, on funcs
> or procs that apply on them, like setLength & copy.  If the answers to the
> following questions are somewhere, just tell me...
>
> * Can one rely on the fact that setLength keeps existing data (in the range of the new size), both when up- and down-sizing? Or do my trials work only because the pointed memory has not yet been overwritten?

Yes, one can rely on this.

>
> * How is resizing actually performed (is the data moved to a newly allocated area)?

This is an implementation detail which should be of no concern to the user.

>
> * Does copy onto a dynamic array automatically resize (setLength), even if the target is greater than needed? (I would like no.)
>
>
> * Can one set the first index where to copy on the target array? (eg to join 2 arrays into a greater one, or to extend an existing one that has free space at tail)
>
> * Can one use copy from/to a *static* array? (If no, why not?)

What does 'copy onto' mean  in these questions ?


>
> * What other differences with static array, if any? (Aside the fact that one does not need to explicitely reallocate and copy on resizing.)

A dynamic array is reference counted.

Thus
   A:=B;

Does not actually copy the entire array, it just lets B point to the same
memory area where the array data is stored and increases the reference count.
With static arrays

   A:=B;

Will actually create a copy.

> For Christmas:
>
> * Can one add or remove an element --at the end? (And have the array behave accordingly.)

No.

>
> * Can one add or remove an element --anywhere? (And have the array behave accordingly.)

No.

>
> If the answers to last 2 questions is "only every 29th of februar", how
> can one have a "flexible" array?  Is there something like that in stock?
> Would you implement it on top of dynamic array, or rather from scratch on
> top of static array (since the "dynamicity" does not seem very helpful)?

If you want a flexible array, use TList or TFPList or TCollection from the classes unit.

Michael.
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: about dynamic array

Graeme Geldenhuys-2
In reply to this post by spir ☣
2010/5/6 spir ☣ <[hidden email]>:
>
> If the answers to last 2 questions is "only every 29th of februar", how can one have a "flexible" array? Is there something like that in stock? Would you implement it on top of dynamic array, or rather from scratch on top of static array (since the "dynamicity" does not seem very helpful)?
>

Use a list class instead. Descend from TList or embed TList in a class
as a field variable. I hardly ever use arrays, simply because list
classes can do everything you mention and works as expected.


--
Regards,
  - Graeme -


_______________________________________________
fpGUI - a cross-platform Free Pascal GUI toolkit
http://opensoft.homeip.net/fpgui/
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: about dynamic array

spir ☣
On Thu, 6 May 2010 12:16:22 +0200
Graeme Geldenhuys <[hidden email]> wrote:

> 2010/5/6 spir ☣ <[hidden email]>:
> >
> > If the answers to last 2 questions is "only every 29th of februar", how can one have a "flexible" array? Is there something like that in stock? Would you implement it on top of dynamic array, or rather from scratch on top of static array (since the "dynamicity" does not seem very helpful)?
> >
>
> Use a list class instead. Descend from TList or embed TList in a class
> as a field variable. I hardly ever use arrays, simply because list
> classes can do everything you mention and works as expected.

Right, Michael gives the same advice. What I need is actually a general-purpose sequence type. The point is that insertion/deletion is indeed required, but the most common operations are the ones efficient with arrays, esp. plain item access via index. This is the reason why sequences in dynamic languages (eg python lists) are in fact implemented as flexible arrays, that simply happen to also behave like lists from the point of view of client code.
So, if TList is a type of linked list, it can probably not do the job for me. Anyway, I'm not a production programmer & would be pleased to explore this topic as an occasion to learn Pascal and fp further.
Tips/pointers welcome. (I'm currently stuck with how to have a [pointer] variable/field refer to a static array which size may change ;-)

denis
________________________________

vit esse estrany ☣

spir.wikidot.com
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: about dynamic array

cobines
2010/5/6 spir ☣ <[hidden email]>:
> So, if TList is a type of linked list, it can probably not do the job for me. Anyway, I'm not a production programmer & would be pleased to explore this topic as an occasion to learn Pascal and fp further.

TList wraps TFPList, which is based internally on an array. So access
is fast; insertion, deletion not.

--
cobines
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re[2]: about dynamic array

José Mejuto
Hello FPC-Pascal,

Thursday, May 6, 2010, 3:53:59 PM, you wrote:

c> TList wraps TFPList, which is based internally on an array. So access
c> is fast; insertion, deletion not.

But it is faster than inserting elements in a dynamic array (unless
reference counted ones) because it usually moves less amount of data
(4/8 bytes per element).

--
Best regards,
 José

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: about dynamic array

spir ☣
On Thu, 6 May 2010 16:20:58 +0200
José Mejuto <[hidden email]> wrote:

> Hello FPC-Pascal,
>
> Thursday, May 6, 2010, 3:53:59 PM, you wrote:
>
> c> TList wraps TFPList, which is based internally on an array. So access
> c> is fast; insertion, deletion not.
>
> But it is faster than inserting elements in a dynamic array (unless
> reference counted ones) because it usually moves less amount of data
> (4/8 bytes per element).
>

Thank you very much, José & Henry, have the information I needed. I'll use TList for all kinds of flexible & ordered sequences.

Denis
________________________________

vit esse estrany ☣

spir.wikidot.com
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: about dynamic array

Florian Klämpfl
In reply to this post by José Mejuto
José Mejuto schrieb:

> Hello FPC-Pascal,
>
> Thursday, May 6, 2010, 3:53:59 PM, you wrote:
>
> c> TList wraps TFPList, which is based internally on an array. So access
> c> is fast; insertion, deletion not.
>
> But it is faster than inserting elements in a dynamic array (unless
> reference counted ones) because it usually moves less amount of data
> (4/8 bytes per element).
>

Why do you think so? You can also create dyn. arrays of pointers.
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: about dynamic array

etrusco
On Thu, May 6, 2010 at 11:58 AM, Florian Klaempfl
<[hidden email]> wrote:

> José Mejuto schrieb:
>> Hello FPC-Pascal,
>>
>> Thursday, May 6, 2010, 3:53:59 PM, you wrote:
>>
>> c> TList wraps TFPList, which is based internally on an array. So access
>> c> is fast; insertion, deletion not.
>>
>> But it is faster than inserting elements in a dynamic array (unless
>> reference counted ones) because it usually moves less amount of data
>> (4/8 bytes per element).
>>
>
> Why do you think so? You can also create dyn. arrays of pointers.

I guess José is well aware of it, but isn't it a good thing to suggest
the use of TFPList to "newbies"?

-Flávio
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re[2]: about dynamic array

José Mejuto
In reply to this post by Florian Klämpfl
Hello FPC-Pascal,

Thursday, May 6, 2010, 4:58:41 PM, you wrote:

>> c> TList wraps TFPList, which is based internally on an array. So access
>> c> is fast; insertion, deletion not.
>>
>> But it is faster than inserting elements in a dynamic array (unless
>> reference counted ones) because it usually moves less amount of data
>> (4/8 bytes per element).
>>
FK> Why do you think so? You can also create dyn. arrays of pointers.

I know, but I think this user is looking for a general purpose ordered
list accesible by index and TList more or less matches the request and
keep a more user friendly interface. Is quote "unless referenced
counted ones" because as referenced counted are pointers, a dyn array
of strings would be more or less as fast as a TList, well, a bit
faster in fact. If the user plans to use a record (which is my
suspect) with TList he must "new" and "dispose" the elements and he
will end up with a dyn array of pointers after all, which is a TList.

I know that sometimes I over simplify some things, but I think that
you'll agree with me that a deeper explain sometimes add fog to a
clear concept.

--
Best regards,
 José

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: about dynamic array

Florian Klämpfl
José Mejuto schrieb:

> Hello FPC-Pascal,
>
> Thursday, May 6, 2010, 4:58:41 PM, you wrote:
>
>>> c> TList wraps TFPList, which is based internally on an array. So access
>>> c> is fast; insertion, deletion not.
>>>
>>> But it is faster than inserting elements in a dynamic array (unless
>>> reference counted ones) because it usually moves less amount of data
>>> (4/8 bytes per element).
>>>
> FK> Why do you think so? You can also create dyn. arrays of pointers.
>
> I know, but I think this user is looking for a general purpose ordered
> list accesible by index and TList more or less matches the request and
> keep a more user friendly interface. Is quote "unless referenced
> counted ones" because as referenced counted are pointers, a dyn array
> of strings would be more or less as fast as a TList, well, a bit
> faster in fact. If the user plans to use a record (which is my
> suspect) with TList he must "new" and "dispose" the elements and he
> will end up with a dyn array of pointers after all, which is a TList.

A dyn. array of records requires no new/dispose as well as no type casts
as TList does.
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re[2]: about dynamic array

José Mejuto
Hello FPC-Pascal,

Thursday, May 6, 2010, 8:58:33 PM, you wrote:

>> faster in fact. If the user plans to use a record (which is my
>> suspect) with TList he must "new" and "dispose" the elements and he
>> will end up with a dyn array of pointers after all, which is a TList.
FK> A dyn. array of records requires no new/dispose as well as no type casts
FK> as TList does.

OK, I see :) Do you remember how this veryyyy long thread starts ?

A: array of MyArray;
SetLength(A,x);
A[0]:=MyArrayElement;
Move(A,B,sizeof..);

Entering the doom again... Next question could be why:

p1: TObject;
p2: TObject;
p1:=TObject.Create();
p2:=p1;
P1.free;
p1:=nil;

Why I get an AV if accesing p2 ? Because the object has been freed...
So why is not p2 = nil as p1 ?

This kind of messages will end up or in a master class of pointers for
dummies or a lot of developers dropping the list for days.

I had proposed the "solution" that I think is easy to understand what
happends behind the scenes or maybe I wrongly choose the moment of hit
reply :(

--
Best regards,
 José

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: about dynamic array

Doug Chamberlin
On 5/6/2010 3:12 PM, José Mejuto wrote:

> Entering the doom again... Next question could be why:
> p1: TObject;
> p2: TObject;
> p1:=TObject.Create();
> p2:=p1;
> P1.free;
> p1:=nil;
>
> Why I get an AV if accesing p2 ? Because the object has been freed...
> So why is not p2 = nil as p1 ?
The short answer is because you have not set p2 to nil as you did to p1.

Pointer operations (and the disguised ones that are references to class
instances and dynamic data structures) are NOT managed for you. You
still have to be careful in handling them. That is why the FreeAndNil
procedure was created. To help you manage object instance references.

Consider this: The runtime system does not keep track of how many
variables you set pointing to a given location. To do so would be VERY
inefficient. Therefore, it cannot go out and find all those variables
and set them for you. As the programmer you have to do this yourself.
That's part of what programming is all about.

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re[2]: about dynamic array

José Mejuto
Hello FPC-Pascal,

Thursday, May 6, 2010, 9:50:34 PM, you wrote:

DC> The short answer is because you have not set p2 to nil as you did to p1.

I do not want to be rude but, do you read all the message ? I was
trying to be ironic, but seems that I was unable maybe due my very
limited english, sorry.

--
Best regards,
 José

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: about dynamic array

spir ☣
In reply to this post by etrusco
On Thu, 6 May 2010 12:10:39 -0300
Flávio Etrusco <[hidden email]> wrote:

> On Thu, May 6, 2010 at 11:58 AM, Florian Klaempfl
> <[hidden email]> wrote:
> > José Mejuto schrieb:
> >> Hello FPC-Pascal,
> >>
> >> Thursday, May 6, 2010, 3:53:59 PM, you wrote:
> >>
> >> c> TList wraps TFPList, which is based internally on an array. So access
> >> c> is fast; insertion, deletion not.
> >>
> >> But it is faster than inserting elements in a dynamic array (unless
> >> reference counted ones) because it usually moves less amount of data
> >> (4/8 bytes per element).
> >>
> >
> > Why do you think so? You can also create dyn. arrays of pointers.
>
> I guess José is well aware of it, but isn't it a good thing to suggest
> the use of TFPList to "newbies"?

Both are good to me. I first implemented my needs as a dynamic array of pointers, precisely.
(By the way, started playing with TFPList already, and could not find how to get data back! I mean the symtric of add(). Even tried indexing (who knows, with the syntactic magic of modern language? ;-).)

Denis
________________________________

vit esse estrany ☣

spir.wikidot.com
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: about dynamic array

cobines
2010/5/6 spir ☣ <[hidden email]>:
> (By the way, started playing with TFPList already, and could not find how to get data back! I mean the symtric of add(). Even tried indexing (who knows, with the syntactic magic of modern language? ;-).)

It is indexing.

var
  l: TFPList;
  p: Pointer;
  index: Integer;
begin
  l := TFPList.Create;
  index := l.Add(p);
  p := l[index];
end;

You can use it like an array too:

var
  l: TFPList;
begin
  l := TFPList.Create;
  l.Count := 20;
  // now you have l[0]..l[19] elements for read/write
end;


--
cobines
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: about dynamic array

spir ☣
On Fri, 7 May 2010 06:10:30 +0200
cobines <[hidden email]> wrote:

> 2010/5/6 spir ☣ <[hidden email]>:
> > (By the way, started playing with TFPList already, and could not find how to get data back! I mean the symtric of add(). Even tried indexing (who knows, with the syntactic magic of modern language? ;-).)
>
> It is indexing.
>
> var
>   l: TFPList;
>   p: Pointer;
>   index: Integer;
> begin
>   l := TFPList.Create;
>   index := l.Add(p);
>   p := l[index];
> end;
> [...]

Thank you, I must have written a typo or messed up indices, since now it works fine. Still, remains a mystery about untyped pointers, illustrated by the code below:

var
        l : TFPList;
        i : Integer;
        p : ^Integer;
begin
        l := TFPList.Create;
        i := 1 ; new(p) ; p^ := i; l.Add(p);
        p := l[0] ; writeln(p^);
        writeln(l[0]^); // error
end.

I cannot directly "fish" and use the pointer's target. Seems I always need to pass _via_ the pointer, then all is fine. It's not really annoying. But I don't understand the difference: in code, both versions are indeed strictly equivalent. I guess there's an implicit (pointer?) conversion somewhere?
Are there cases where the pointer's mediation is not needed?

Denis
________________________________

vit esse estrany ☣

spir.wikidot.com
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: about dynamic array

Michael Van Canneyt


On Fri, 7 May 2010, spir ☣ wrote:

> On Fri, 7 May 2010 06:10:30 +0200
> cobines <[hidden email]> wrote:
>
>> 2010/5/6 spir ☣ <[hidden email]>:
>>> (By the way, started playing with TFPList already, and could not find how to get data back! I mean the symtric of add(). Even tried indexing (who knows, with the syntactic magic of modern language? ;-).)
>>
>> It is indexing.
>>
>> var
>>   l: TFPList;
>>   p: Pointer;
>>   index: Integer;
>> begin
>>   l := TFPList.Create;
>>   index := l.Add(p);
>>   p := l[index];
>> end;
>> [...]
>
> Thank you, I must have written a typo or messed up indices, since now it works fine. Still, remains a mystery about untyped pointers, illustrated by the code below:
>
> var
> l : TFPList;
> i : Integer;
> p : ^Integer;
> begin
> l := TFPList.Create;
> i := 1 ; new(p) ; p^ := i; l.Add(p);
> p := l[0] ; writeln(p^);
> writeln(l[0]^); // error
> end.
>
> I cannot directly "fish" and use the pointer's target. Seems I always need to pass _via_ the pointer, then all is fine. It's not really annoying. But I don't understand the difference: in code, both versions are indeed strictly equivalent. I guess there's an implicit (pointer?) conversion somewhere?
> Are there cases where the pointer's mediation is not needed?
L[0] is an untyped pointer. Dereferencing it gives you a memory address,
but not a type. So the compiler doesn't know what to do with it.

p is a pointer to an integer. When dereferencing it, the compiler knows that
at the address an integer is waiting, and it knows how to deal with
integers.

Adding a typed pointer (p) to an untyped pointer list does not store
the type information in the list, any type information available is
lost: the compiler or the list do not remember that you stored a pointer
to an integer. They just remember the address, not the type.

Michael.
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: about dynamic array -- p

spir ☣
In reply to this post by cobines
On Fri, 7 May 2010 06:10:30 +0200
cobines <[hidden email]> wrote:


PS : I also need the pointer's mediation when a func/proc expects a (typed) element. Must rewrite the code to use an element pointer as parameter (and pass a pointer from the list). This is more annoying since it obscures the func/proc's signature.

Is the source of this issue really that these pointers are untyped? If yes, maybe a way to get rid of such noise would be to subtype TFPList into a list of typed pointers?

(I don't know yet how to use fpc's type system. So new in this domain I have no idea what the difference between type & class may be ;-) But this will come soon, I guess...)

Denis
________________________________

vit esse estrany ☣

spir.wikidot.com
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
12