Set iterators

Allen Wirfs-Brock allen at wirfs-brock.com
Mon Feb 13 18:26:39 PST 2012


On Feb 13, 2012, at 6:03 PM, Mark S. Miller wrote:

> [+tjclose]
> 
> On Mon, Feb 13, 2012 at 5:32 PM, Allen Wirfs-Brock <allen at wirfs-brock.com> wrote:
> 
> Before getting too deep into iteration protocol for Sets (and Maps) there is a more fundamental issues:  Will Set define a standard, implementation independent ordering of elements? If so, what is the basis for the ordering?
> 
> Yes. Insertion order.
>  
> 
> Is it iteration order?
> 
> Well yes by definition ;). Did you mean to ask if it is insertion order? Yes.
yes
> 
>  
>  Is so this will add likely add space overhead to the internal  representation  of Set and Map and/or time overhead to insert/delete operations.  
> 
> Tyler Close previously posted a deterministic hash table implementation, with no extra space or time overhead. Before I saw it I thought it impossible.
>  
> Also, for specializations of Set such as Integer Sets insertion order may not be the most desirable iteration ordering.

do you have the link to that post?

> 
> That's a good point. Perhaps we can say that the abstract Map and Set contract merely demands that each concrete kind of Map or Set specify how their iteration order depends on their inputs. The default Maps and Sets can use insertion order (and typically be implemented using Tyler's algorithm.)

I suspect that requiring a consistent or implementation independent iteration order for user written concrete Maps or Sets  would be an unenforcable

Allen


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20120213/045ff7d9/attachment-0001.html>


More information about the es-discuss mailing list