javascriptcollectionssetsortedset

Sorted (ordered) collection for JavaScript

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

  1. Custom comparator support
  2. Automatically sorted
  3. Find the specific value. If value is not found, get the next value (insertion position value).
  4. 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?

Solution

  • 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

    Usage

    To help you have a better use, we provide this API document.