[whatwg] DOMTokenList is unordered but yet requires sorting

[Erik Arvidsson]

On Mon, Jun 15, 2009 at 16:12, Aryeh Gregor
<Simetrical+w3c at gmail.com<Simetrical%2Bw3c at gmail.com>
> wrote:

> On Mon, Jun 15, 2009 at 7:11 PM, Kristof
> Zelechovski<giecrilj at stegny.2a.pl> wrote:
> > The complexity of using a set/map is logarithmic in the size of the set.
>
> Not if it's implemented as a hash table.
>
> Is DOMTokenList really expected to store lists large enough that this
> asymptotic behavior matters, though?
>

For WebKit I was initially not planning to use a backing map/set. Class
lists should be pretty small and for small lists it is faster to iterate
over the list than using a hash table. If this ends up being a performance
issue a backing map/set can be used. (WebKit uses a vector internally and
does O(n) lookups when computing the style so I doubt it will be a
performance issue.)

-- 
erik
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.whatwg.org/pipermail/whatwg-whatwg.org/attachments/20090615/8ae80ed3/attachment-0002.htm>