Skip to content

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?

Answer

collctions/sorted-array-set http://www.collectionsjs.com/sorted-array-set

It satisfies following requirement efficiently.

  1. Custom comparator support. See http://www.collectionsjs.com/sorted-set constructor (top-right of the page).

  2. Automatically sorted. It is obvious. The collection is sorted-set.

  3. Find the specific value. If value is not found, get the next value (insertion position value). Use findLeastGreaterThanOrEqual(value) http://www.collectionsjs.com/method/find-least-greater-than-or-equal If you want to find the specific value, and if value is not found, get the previous value, then you can use findGreatestLessThanOrEqual(value) http://www.collectionsjs.com/method/find-greatest-less-than-or-equal Time complexity is O(logN).

It is inefficient but it also satisfies the following requirement.

  1. Iterator increment/decrement operation (move to prev/next element). There are no iterators to access the sibling elements but you can use findLGreatestLessThan(value) http://www.collectionsjs.com/method/find-greatest-less-than to access the previous element, and can use findLeastGreaterThan(value) http://www.collectionsjs.com/method/find-least-greater-than to access the next element. The search is started from the root element of the tree. So each time to access to the sibling element, it requires O(logN) time complexity.