标签: ordered-set

这类似于How do I use a custom comparator function with BTreeSet? 但就我而言，直到运行时我才会知道排序标准。可能的标准很广泛，并且不能进行硬编码（想想像按到目标的距离排序或按有效负载中的特定字节或其组合排序）。创建地图/集合后，排序标准不会更改。

我看到的唯一替代方案是：

• 使用 a Vec，但 log(n) 插入和删除至关重要
• 用排序标准（直接或间接）包装每个元素，但这似乎很浪费

这对于标准 C++ 容器std::map/是可能的，但对于 Rust 的/std::set似乎不可能。标准库或其他板条箱中是否有替代方案可以做到这一点？或者我必须自己实施这个？BTreeMapBTreeSet

我的用例是一个类似数据库的系统，其中集合中的元素由模式定义，例如：

Element {
    FIELD x: f32
    FIELD y: f32
    FIELD z: i64

    ORDERBY z
}

但由于模式是用户在运行时定义的，因此元素存储在一组字节 ( BTreeSet<Vec<u8>>) 中。同样，元素的顺序是用户定义的。所以我会给的比较器BTreeSet看起来像|a, b| schema.cmp(a, b)。硬编码后，上面的示例可能类似于：

fn cmp(a: &Vec<u8>, b: &Vec<u8>) -> Ordering {
    let a_field = self.get_field(a, 2).as_i64();
    let b_field = self.get_field(b, 2).as_i64(); …

我正在Stack Overflow 上浏览这个答案。我来了解存在OrderedSet于Python的。我想知道它是如何在内部实现的。它类似于集合的哈希表实现吗？

另外，插入、删除、查找等一些常见操作的时间复杂度是多少？

Rust 的有序集是一个BTreeSet：

use std::collections::BTreeSet;

// Type inference lets us omit an explicit type signature (which
// would be `BTreeSet<&str>` in this example).
let mut books = BTreeSet::new();

// Add some books.
books.insert("A Dance With Dragons");
books.insert("To Kill a Mockingbird");
books.insert("The Odyssey");
books.insert("The Great Gatsby");

Run Code Online (Sandbox Code Playgroud)

有序映射是一个BTreeMap.

由于 set 和 map 是有序的，因此应该有一种方法可以获取包含的最大和最小元素。你怎么得到它们？

我是 Erlang 世界的新手，所以我正在尝试尝试它。

我有一个称为数字的 ETS 表。

ets:new(numbers,[ordered_set,named_table])

它的格式为 [{Name,Number},{Name,Number}] 等。

我想知道有没有办法输出整个 ets 表的内容？

以下过程获取两个列表，并将它们的并集作为有序列表返回。

(defun stable-union (lst1 lst2)
  (cond ((null lst1) lst2)
        ((null lst2) lst1)
        ((and (null lst1) (null lst2)) nil)
        (t
         (let ((el1 (car lst1))
               (el2 (car lst2)))
           (cond ((string= el1 el2)
                  (cons el1
                     (stable-union (cdr lst1)  (cdr lst2))))
                  ((string< el1 el2)
                   (cons el1
                         (stable-union (cdr lst1)  lst2)))
                  (t
                   (cons el2
                         (stable-union lst1 (cdr lst2)))))))))

它仅适用于某些示例，而不适用于其他示例。例如：

STABLE-UNION: (STABLE-UNION '(A B C) '(B A D)) failed: 
Expected (A B C D) but saw (A B A C D)
STABLE-UNION: (STABLE-UNION '(A B C) …