Set iterators

Mark S. Miller erights at google.com
Mon Feb 13 18:03:18 PST 2012


[+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.



>  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.


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.)

-- 
    Cheers,
    --MarkM
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20120213/c4f2cf68/attachment.html>


More information about the es-discuss mailing list