Suggestion: dynamic array operations

[Gregor Richards]

Gregor Richards wrote:
> Steve Horne wrote:
>> On Wed, 06 Sep 2006 10:51:32 -0700, Gregor Richards
>> <Richards at codu.org> wrote:
>>
>>> Arrays are arrays, not lists.  You can abuse them into stacks, queues 
>>> and the ilk, but it's an inefficient use of memory.
>>
>> Sorry for pedanting, but it's an inefficient use of CPU cycles, not
>> memory. Arrays are more memory efficient than linked lists - no
>> per-item pointers, and only a one-off malloc overhead.
>>
>> Even for time, it depends on how big the stack/deque will get. For
>> small sizes arrays are a good choice. Realloc problems are minimised,
>> time to shift the items up/down is trivial, and there are cache
>> benefits to keeping the items in adjacent memory locations.
>>
>> For large deques, what you really want is a list of small arrays. A
>> trade-off between the costs and benefits of both lists and arrays.
>> IIRC this is pretty much what std::deque does in C++. But even then,
>> pushing and popping on the small arrays is needed to implement the
>> full deque logic.
>>
>> And of course, that large deque class could overload those operators
>> to allow the same syntax.
>>
>> I just think methods are a better choice than operators for this.
>>
> 
> To pop an element off the front of an array requires either losing that 
> chunk of memory or moving the entire rest of the array back such that 
> that memory is still used.  Pushing an element onto either side of an 
> array involves expanding the memory used by that array, which often 
> involves duplication.  Using an array as a stack or queue is a waste of 
> MEMORY, not CPU cycles.
> 
>  - Gregor Richards

Erm, totally misread everything.  Wowza.

Yeah, that'd be CPU cycles :P

  - Gregor Richards