I'm not sure I understand what use this container would have in common cases. You can simply sort an ordinary array and then binary search it. A 'SortedArray' primitive would be very strange in JS also since as soon as you modified the value at an index, either the array becomes unsorted or it has to be resorted and now the value you just wrote isn't there anymore, that is:
a[i] = 1; a[i] !== 1; Which is pretty strange for a container. Normally a container like this would not allow those sorts of operations, which makes it somewhat less useful. If all you want is has/remove (I have no idea what 'set' would do in this case - is it just add?), why not use Set? Do you just need the ability to store duplicates? If so, I think a map of item->count might suffice, though I'm not sure precisely how easy that is to express in JS. It sounds like all you really need here is Array.binarySearch as a builtin (or JS polyfill) to implement the container you want, but it's also not clear why you want this container or what it would do for you. JS-based implementations can outperform native implementations in some cases; it depends. I think in this case a self-hosted implementation would end up faster, but only if it were specialized for the element type(s) in the array. On Fri, Aug 9, 2013 at 11:27 PM, Alex Vincent <[email protected]> wrote: > 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 > > _______________________________________________ > es-discuss mailing list > [email protected] > https://mail.mozilla.org/listinfo/es-discuss > >
_______________________________________________ es-discuss mailing list [email protected] https://mail.mozilla.org/listinfo/es-discuss
