I’m looking for sorted container for JavaScript.
I’m using C++ std::set
, https://en.cppreference.com/w/cpp/container/set
and try porting my code to JavaScript.
JavaScript Map is not ordered container. I need some ordered container.
I don’t need completely compatible container of std::set
on C++.
My requirements are
- Custom comparator support
- Automatically sorted
- Find the specific value. If value is not found, get the next value (insertion position value).
- Iterator increment/decrement operation (move to prev/next element)
Here is C++ code example that demonstrates my requirements: https://wandbox.org/permlink/wGnTvTPyOej4G9jo
#include <set> #include <iostream> int main() { // 1. Custom comparator support auto comp = [](auto lhs, auto rhs) { return lhs < rhs; }; std::set<int, decltype(comp)> s(comp); // 2. Automatically sorted s.insert(5); s.insert(2); s.insert(3); for (auto v : s) std::cout << v << std::endl; auto finder = [&](auto v) { std::cout << "try find " << v << std::endl; // 3. Find the specific value. // If value is not found, get the next value (insertion position value). auto it = s.lower_bound(v); auto end = s.end(); if (it == end) { std::cout << v << " not found. Insertion point is tail" << std::endl; } else { if (*it == v) { std::cout << v << " found" << std::endl; if (it != s.begin()) { auto left = it; // 4. Iterator increment/decrement operation --left; std::cout << "prev elem is " << *left << std::endl; } if (it != --end) { auto right = it; // 4. Iterator increment/decrement operation ++right; std::cout << "next elem is " << *right << std::endl; } } else { std::cout << v << " not found. Insertion point is just before " << *it << std::endl; } } }; finder(1); finder(3); }
I found the following containers:
collctions/sorted-set
https://www.npmjs.com/package/sorted-btree
It satisfies 1, 2, and 3, but not support 4.
collctions/sorted-array-set
http://www.collectionsjs.com/sorted-array-set
It satisfies 1, 2, and 4(maybe), but not support 3.
Does someone know any container that support my requirements?
Advertisement
Answer
js-sdsl
A javascript standard data structure library which benchmark against C++ STL.
This library has strict time complexity guarantee and can be used with confidence.
The latest beta version includes iterator functions which can be used like iterator in c++.
Included data structures
- Vector
- Stack
- Queue
- LinkList
- Deque
- PriorityQueue
- Set (using RBTree)
- Map (using RBTree)
- HashSet (for reference only)
- HashMap (for reference only)
Usage
To help you have a better use, we provide this API document.