Я ищу сортированный контейнер для JavaScript.

Я использую C std::set , https://en.cppreference.com/w/cpp/container/set и попробуйте перенести мой код на JavaScript.

Карта JavaScript не является упорядоченным контейнером. Мне нужен какой-то упорядоченный контейнер.

Мне не нужен полностью совместимый контейнер std::set на C . Мои требования

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 = [amp;](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.

Кто-нибудь знает какой-нибудь контейнер, который поддерживает мои требования?

js-sdsl

Стандартная библиотека структуры данных javascript, которая сравнивается с C STL.

Эта библиотека имеет строгую гарантию сложности по времени и может использоваться с уверенностью.

Последняя бета-версия включает функции итератора, которые можно использовать как итератор в c .

Включенные структуры данных

• Вектор
• Стек
• Очередь
• Список ссылок
• Deque
• Приоритетная очередь
• Набор (с использованием RBTree)
• Карта (с использованием RBTree)
• HashSet (только для справки)
• HashMap (только для справки)

Использование

Чтобы помочь вам лучше использовать, мы предоставляем этот документ API.

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) время сложности.