insort
JavaScript (ES6) Map, Set, and Object subclasses that efficiently maintain a sorted iteration order.
Usage
let SortedMap SortedSet SortedObject = ; // compare function (defaults to localeCompare)let a - b; let m = 42 'foo' 99 'bar' 0 'quux' cmp;m;for let key val of m console;// 0 'quux'// 42 'foo'// 59 'spam'// 99 'bar' let s = 42 99 0 cmp;s;for let key of s console;// 0// 42// 59// 99 let o = foo: 42 bar: 99 quux: 0;obaz = -8;for let key in o console;// bar 99// baz -8// foo 42// quux 0
Requirements
- ES6
Features
- Simple and small
- Uses standard APIs; just drop into existing Map-, Set-, or Object-based code
- Space efficient (adds an extra O(n) sorted Array of key references)
- Time efficient (O(1) find and replace, O(log(n)) insert and delete)
Caveats
- This works fine for a few thousand entries, but for larger datasets you probably want something fancier, such as a skip list.