JavaScript 的排序（有序）集合

Question

我正在寻找 JavaScript 的分类容器。

我正在使用 C++ std::set、https://en.cppreference.com/w/cpp/container/set 并尝试将我的代码移植到 JavaScript.

JavaScript 地图不是有序容器。我需要一些订购的容器。

我不需要 std::set 在 C++ 上完全兼容的容器。我的要求是

自定义比较器支持
自动排序
求出具体值。如果找不到值，则获取下一个值（插入位置值）。
迭代器increment/decrement操作（移动到prev/next元素）

这是演示我的要求的 C++ 代码示例： 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);
}

我找到了以下容器：

collctions/sorted-set https://www.npmjs.com/package/sorted-btree

满足1、2、3，不支持4。

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

满足1、2、4（可能），但不支持3。

有人知道满足我要求的任何容器吗？

Answer 1

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

有效满足以下需求

自定义比较器支持。请参阅 http://www.collectionsjs.com/sorted-set 构造函数（页面右上角）。
自动排序。这很明显。该集合是排序-集合。
求具体值。如果找不到值，则获取下一个值（插入位置值）。使用 findLeastGreaterThanOrEqual(value) http://www.collectionsjs.com/method/find-least-greater-than-or-equal 如果要查找具体的值，如果没有找到就取之前的值，那么可以使用findGreatestLessThanOrEqual(value) http://www.collectionsjs.com/method/find-greatest-less-than-or-equal 时间复杂度为 O(logN).

虽然效率不高，但也满足了下面的要求

迭代器increment/decrement操作（移动到prev/next元素）。没有访问同级元素的迭代器，但您可以使用 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 访问下一个元素。搜索从树的根元素开始。所以每次访问兄弟元素，都需要O(logN)的时间复杂度。

JavaScript 的排序（有序）集合

Sorted (ordered) collection for JavaScript

javascript

collections

set

sortedset