Suggestion: dynamic array operations

[Gregor Richards]

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