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 <ajvincent at gmail.com> 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
> es-discuss at mozilla.org
> https://mail.mozilla.org/listinfo/es-discuss
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20130810/a7c93c54/attachment.html>

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:

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