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 <al...@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
_______________________________________________ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
