$(SUBJ) can be useful and not so difficult feature to implement.

Disnel

Post a reply to this message

dis### [at] hlavacek-partnercz wrote:
: $(SUBJ) can be useful and not so difficult feature to implement.

  Actually dynamic arrays in C are not trivial.

  Luckily in C++ there's a standard library for that.

-- 
main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
):_;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/

Post a reply to this message

But in POV documentation says, that POV arrays are implemented
as linked lists. Thus growings arrays needs only remember number
of elements atually stored, first element and last element.

Warp wrote:
> 
> dis### [at] hlavacek-partnercz wrote:
> : $(SUBJ) can be useful and not so difficult feature to implement.
> 
>   Actually dynamic arrays in C are not trivial.
> 
>   Luckily in C++ there's a standard library for that.
> 
> --
> main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
> ):_;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/

Post a reply to this message

Disnel <dis### [at] itamcascz> wrote:
: But in POV documentation says, that POV arrays are implemented
: as linked lists.

  Wrong. Section 4.1.7.1 says:

"Large uninitalized arrays do not take much memory. Internally they
are arrays of pointers so they probably use just 4 bytes per element."

  They are implemented as an array, not a list. Growing this array of
pointers is not impossible at all, but not trivial (at least if wanting to
do it efficiently).

-- 
main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
):_;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/

Post a reply to this message

Warp wrote:
> 
> Disnel <dis### [at] itamcascz> wrote:
> : But in POV documentation says, that POV arrays are implemented
> : as linked lists.
> 
>   Wrong. Section 4.1.7.1 says:
> 
> "Large uninitalized arrays do not take much memory. Internally they
> are arrays of pointers so they probably use just 4 bytes per element."
> 
>   They are implemented as an array, not a list.

You are right. My mistake.

> Growing this array of
> pointers is not impossible at all, but not trivial (at least if wanting to
> do it efficiently).

If we assume, that array can only grow, thinkgs become simplier.

> 
> --
> main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
> ):_;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/

Post a reply to this message

Disnel <dis### [at] itamcascz> wrote:
: If we assume, that array can only grow, thinkgs become simplier.

  Actually it's the opposite: If we assume that an array can only shrink
(ie. get smaller) then the answer is very trivial (unless you really want
to _free_ that non-used memory as well).
  If it has to be possible to grow the array, some specialized algorithm
has to be implemented. You can't make the array bigger every time the
user wants to make it one item bigger because it would be extremely slow
(specially with big arrays) but you have to reserve space for more than
one item at a time. When the array gets full you have to reserve a bigger
array and copy the old one there (and then free the old one). This copying
is the heaviest operation in the dynamic array and shouldn't be done
too often.

-- 
main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
):_;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/

Post a reply to this message

Warp wrote:
> 
> Disnel <dis### [at] itamcascz> wrote:
> : If we assume, that array can only grow, thinkgs become simplier.
> 
>   Actually it's the opposite: If we assume that an array can only shrink
> (ie. get smaller) then the answer is very trivial (unless you really want
> to _free_ that non-used memory as well).
>   If it has to be possible to grow the array, some specialized algorithm
> has to be implemented. You can't make the array bigger every time the
> user wants to make it one item bigger because it would be extremely slow
> (specially with big arrays) but you have to reserve space for more than
> one item at a time. When the array gets full you have to reserve a bigger
> array and copy the old one there (and then free the old one). This copying
> is the heaviest operation in the dynamic array and shouldn't be done
> too often.

Sure. But if we assume, that access to array is perormed only via
some control functions (methods of array object in OO), we can
work with pieces of array with fixed size organised to some sort
of tree.

> 
> --
> main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
> ):_;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/

Post a reply to this message

On 28 Sep 2000 11:06:47 -0400, Warp wrote:
>dis### [at] hlavacek-partnercz wrote:
>: $(SUBJ) can be useful and not so difficult feature to implement.
>
>  Actually dynamic arrays in C are not trivial.

Maybe not trivial but pretty easy. Just realloc to exponentially growing
sizes. My ant library (http://www.hjp.at/programs/ant/) includes a few
handy macros for this (Caveat - they have a subtle bug which hasn't
bitten me so far - bonus points if you can spot it).

The main program with dynamic arrays in C is that the code which uses
them must be aware that they are dynamic and may change location as well
as size. It must never preserve any pointers into the array across a
point where the array may be resized, but must recompute them from
indexes or stick to using indexes.

	hp

-- 

|_|_) | Sysadmin WSR       | vor dem rechner.

__/   | http://www.hjp.at/ |       at.linux, 2000-09-24

Post a reply to this message

Disnel <dis### [at] itamcascz> wrote:
: Sure. But if we assume, that access to array is perormed only via
: some control functions (methods of array object in OO), we can
: work with pieces of array with fixed size organised to some sort
: of tree.

  But then indexing the array will be slower. Depending on the size of each
block and the number of blocks it may be very slow.
  That's why it's not a list, anyways.

-- 
main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
):_;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/

Post a reply to this message

Warp wrote:
> 
> Disnel <dis### [at] itamcascz> wrote:
> : Sure. But if we assume, that access to array is perormed only via
> : some control functions (methods of array object in OO), we can
> : work with pieces of array with fixed size organised to some sort
> : of tree.
> 
>   But then indexing the array will be slower. Depending on the size of each
> block and the number of blocks it may be very slow.
>   That's why it's not a list, anyways.

Lets use hexadecimal numbers for indexing and chunks of array with
length
of 16. First 16 objects added to array are in one starting chunk and
indexing is direct. When we try to add 17th object then new chunk
is created with reference to starting chunk at the begin. The first
16 objects has indexes 00-0FH which mean zero position in the first
chunk and 0-FH position in subchunk. Then we can have 256 objects
indexed in two passes. Three passes indexes 4096 objects, four
65536 objects and so on. Sure, it is slower than direct indexing
of one big array, but is can grow without memory reallocation ;-).

> 
> --
> main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
> ):_;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/

Post a reply to this message