JavaScript 的排序（有序）集合

Question

我正在寻找 JavaScript 的排序容器。

我正在使用 C++

std::set

，https://en.cppreference.com/w/cpp/container/set 并尝试将我的代码移植到 JavaScript。

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

我不需要 C++ 上完全兼容的

std::set

容器。 我的要求是

1. 自定义比较器支持
2. 自动排序
3. 求具体值。 如果没有找到值，则获取下一个值（插入位置值）。
4. 迭代器递增/递减操作（移动到上一个/下一个元素）

这里是演示我的要求的 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

js-sdsl

一个以C++ STL为基准的javascript标准数据结构库。

本库有严格的时间复杂度保证，可以放心使用。

最新的 beta 版本包含迭代器函数，可以像 C++ 中的迭代器一样使用。

包含的数据结构

• 矢量
• 堆栈
• 队列
• 链接列表
• 双端队列
• 优先队列
• 设置（使用 RBTree）
• 地图（使用RBTree）
• HashSet（仅供参考）
• HashMap（仅供参考）

使用方法

为了帮助您更好的使用，我们提供此API文档。

Answer 2

collctions/sorted-array-set

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

有效满足以下要求。

1. 自定义比较器支持。 请参阅 http://www.collectionsjs.com/sorted-set 构造函数（页面右上角）。

2. 自动排序。 这很明显。该集合已排序集。

3. 求具体值。如果没有找到值，则获取下一个值（插入位置值）。 使用

   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)。

虽然效率低下，但也满足了以下要求。

4. 迭代器递增/递减操作（移动到上一个/下一个元素）。 没有迭代器来访问同级元素，但您可以使用

   findLGreatestLessThan(value)

   http://www.collectionsjs.com/method/find-greatest-less-than 来访问前一个元素，并且可以使用

   findLeastGreaterThan(value)

   http://www.collectionsjs.com/method/find-least-greater-than 访问下一个元素。 搜索从树的根元素开始。 所以每次访问同级元素，都需要O(logN)的时间复杂度。

Answer 3

您的需求很容易满足。您只需要一个使用自定义比较器排序的数组，并提供一个方法

logSearch(item)

，该方法返回

index

，其中给定的项目是或应该是。

@ut8pia/classifier

库提供的SortedArray类完美地满足了这些要求。然而，这个库提供的不仅仅是传统的

sorted collections

方法。我建议您查看在线文档。