[antlr-interest] C Runtime - list container suggestions

[Cameron Esfahani]

Interesting.

Then what would the difference between a list and a vector be?

Personally, I thought that vector would do what you describe.  That  
things would move up in the container as items were deleted.

The reason I thought that list would supported persistent IDs is that  
the list routines are built on top of Jim's hash table routines.

If that's the case, then one way to fix list to handle persistent IDs  
would be to use an increasing integer value as the key, supplied by  
list add(), to the hash routine.  Right now, it uses the size of the  
hash, which means it can decrease when items are deleted, causing  
keys to collide.

This is how I solved it.  I stopped using the list routines and just  
created a hash with an integer key that increased each time I called  
add().

On Aug 14, 2007, at 1:09 AM, Gavin Lambert wrote:

> At 10:29 14/08/2007, Jim Idle wrote:
>> I will implement a temporary fix, then look at changing to  
>> vectors, which are faster than the hash table for this anyway. I  
>> think my doubts were whether you should be able to delete an  
>> element from the list and expect the keys to be preserved, or  
>> whether the key should be an ordinal, in that you can delete list  
>> entry #1 as many times as there is a list entry #1 left. I need to  
>> decide which it should be then implement either a key field in the  
>> structure (so that it does not reuse the same key in the  
>> hashtable), or change to vectors and make the key ordinal (which  
>> is what I think a list means actually).
>
> By normal definitions, a "list" could either be a "linked list" or  
> a "vector"; either way it's logically unkeyed (though frequently  
> they are implicitly keyed by their position in the collection).  So  
> for a "list" I think everyone would expect the behaviour that if  
> you deleted item #1 then item #2 would "move" to become the new  
> item #1.  (Which is not what it does right now.)
>
> I imagine hashtables could still be useful in some places (eg. the  
> string factory), but I suspect most of the public stuff should  
> probably be dealing with lists.
>

Cameron Esfahani
dirty at apple.com

"With or without religion, good people can behave well and bad people  
can do evil; but for good people to do evil - that takes religion."

Steven Weinberg



-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20070815/ffd28b5a/attachment.html