Am I getting this all right?

[Sean Kelly]

Jason House wrote:
> An earlier post showed stack with push and pop for an array.  How does one do a
> queue? a set?

A queue isn't easy because array-based queues generally need to track 
where the head of the queue is (that or move the rest of the queue on 
each pop operation), so queues really need an object wrapper to be done 
well.  However, storing the data in an array is still generally faster 
than using a linked list.  I ran a test not too long ago in Java, and an 
array-based queue was roughly 50% faster than a linked list-based queue 
for inserting and removing one million elements, and that was using a 
'for' loop to copy elements during a resize operation (instead of a 
memcpy).  A free-list could improve average performance of a linked list 
implementation, but in a worst case scenario the array-based queue will 
still win (assuming a non-trivial allocation cost).  Sets are easily 
modeled as sorted arrays however.

But the real advantage of offering these algorithms apart from any 
specific container is that they can be applied to any sequence that 
supports the appropriate operations.  For example, the set intersection 
operation could be applied to two SQL result sets as easily as to 
arrays, and no copying to a Set container would be necessary.  My code 
currently only supports arrays, but that is mostly because there is no 
accepted iterator definition for D.  But this topic was discussed pretty 
heavily about a month ago and I may go ahead and just create one.  It's 
just lingering a bit low on my to-do list at the moment.

> Also, I haven't found a way to check if something is in an associative array or not.

     if( x in myAA ) {}

The 'in' operator actually returns a pointer to the value, or null if 
the value is not present, so a test and modify operation might do:

     if( auto t = x in myAA )
         *t = u;

> This may all boil down to me not being able to find a comprehensive list of array
> properties and/or quality documentation on the D language.

The array documentation is actually some of the best in the spec.  "in" 
is mentioned in the Associative Array section:

http://www.digitalmars.com/d/arrays.html#associative

But is also documented as an expression:

http://www.digitalmars.com/d/expression.html#InExpression


Sean