Missing OrderedMap or SortedMap data structure

[stanf0rd]

As you know, ES6 Map just remembers the original insertion order of the keys. There is no option to store all values in some sorted order for getting first/last value, fast conversion to sorted Array or get index without any additional sorting.

Suddenly i didn't find any SortedMap in that library, too :(

I think it is a nice thing to have.

[Yomguithereal]

Hello @stanf0rd. You are right indeed. But if you need this to be actually efficient some benchmarks must be done to be able to find the best way to do so in JavaScript and this is not trivial. What I mean is that there probably exists a threshold where using a binary tree is actually slower than keeping a map and a sorted array by hand, which is unintuitive. Then you have the issue of determining which balanced binary tree implementation would work best in JavaScript (which might differ with any other language, lower-level ones even so). My money is between red-black, splay and AVL. Then if you want to keep performant enough you probably need to reproduce the pointer tricks I use in other structure of the lib and then you need to assert whether you need deletions or not.

So this requires quite a lot of work, which we can try to do together but I don't have time in the near-future to draft the necessary benchmark. Do you want to attempt something, or research whether those questions have already been answered by somebody?