SortedArray in JavaScript?

Alex Vincent ajvincent at gmail.com
Fri Aug 9 23:27:59 PDT 2013


Hi, folks.  After a year of computer science courses (yay for learning
fundamentals), I've been thinking about arrays and their indexOf() method,
and wondering:  why don't we have an array type that sorts the items for us
in JavaScript?

(By the way, I love the Map & Set implementations in Firefox.  Very, very
handy.)

Because arrays in JS are assumed to be unsorted, indexOf is an O(n)
operation.  But if I have an array of values, and use a simple comparator
function, indexOf becomes O(log n), plus whatever the invocation time is
for the comparator.

In the simplest cases, I'm sorting numbers or strings, which wouldn't need
a fancy comparator function.  If I'm sorting objects, I can write my
comparator function just like I would for Array.sort.

Many of the methods for manipulating arrays would go away (unshift, shift,
push, pop, splice).  There would also be a need to add .has(), .set(),
.remove() methods, probably (like a Map).

I'm sure I'm just repeating the obvious now, so I'm wondering if it would
be worth adding to the language in some form.  I'm well aware it would be
easy to implement in JavaScript, but would a JS-based implementation be
faster than a native one?

-- 
"The first step in confirming there is a bug in someone else's work is
confirming there are no bugs in your own."
-- Alexander J. Vincent, June 30, 2001
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20130809/9f15cf76/attachment-0001.html>


More information about the es-discuss mailing list