gb_sets

模块

gb_sets

模块摘要

一般平衡的树。

描述

本模块使用Arne Andersson教授的一般平衡树提供有序集。有序集合比使用有序列表更有效率，对于更大的集合，但取决于应用程序。

当且仅当它们不比较equal（==）时，该模块将两个元素视为不同。

复杂性说明

设置操作的复杂度受到O（| S |）或O（| T | * log（| S |））的约束，其中S是最大的给定集合，取决于对于任何特定函数调用哪个最快。对于几乎相同大小的集合进行操作，此实现比直接使用排序列表集大约慢3倍。然而，对于非常不同尺寸的套件，这种解决方案可以任意快得多; 在实际情况下，往往是10-100倍。这个实现特别适合于一次累积几个元素，建立一个大集合（> 100-200个元素），并且重复测试当前集合中的成员资格。

与普通树结构一样，查找（成员测试），插入和删除具有对数复杂性。

兼容性

本模块中的下列函数也存在，并在sets(3)和ordsets(3)模块。也就是说，只需更改每个调用的模块名称，就可以尝试不同的集合表示。

add_element/2

del_element/2

filter/2

fold/3

from_list/1

intersection/1

intersection/2

is_element/2

is_set/1

is_subset/2

new/0

size/1

subtract/2

to_list/1

union/1

union/2

数据类型

set(Element)

一般的平衡集。

set() =set(term())

iter(Element)

一般的平衡集迭代器。

iter() =iter(term())

输出

add(Element, Set1) -> Set2

add_element(Element, Set1) -> Set2

类型

返回一个新集。Set1带着Element插入。如果Element中的一个元素。Set1没有什么改变。

balance(Set1) -> Set2

类型

重新平衡树的表示Set1。请注意，这很少需要，但是如果没有进一步插入从树中删除大量元素，就可能出现动机。然后可以强制重新平衡以最小化查找时间，因为删除不会重新平衡树。

del_element(Element, Set1) -> Set2

类型

返回一个新集。Set1带着Element移除。如果Element不是Set1没有什么改变。

delete(Element, Set1) -> Set2

类型

返回由Set1删除Element的新集合。假定元素存在于Set1中。

delete_any(Element, Set1) -> Set2

类型

返回一个新集。Set1带着Element移除。如果Element不是Set1没有什么改变。

difference(Set1, Set2) -> Set3

类型

仅返回Set1那些不是元素的元素Set2。

empty() -> Set

类型

返回一个新的空集。

filter(Pred, Set1) -> Set2

类型

Set1使用谓词函数过滤元素Pred。

fold(Function, Acc0, Set) -> Acc1

类型

Function对每个元素进行折叠，以Set返回累加器的最终值。

from_list(List) -> Set

类型

返回一组元素List，其中List可以无序并包含重复项。

from_ordset(List) -> Set

类型

转一个有序集列表。List变成一组。列表不得包含重复项。

insert(Element, Set1) -> Set2

类型

返回从形成了一套新的Set1与Element插入。假设Element不存在于Set1。

intersection(SetList) -> Set

类型

返回集合的非空列表的交集。

intersection(Set1, Set2) -> Set3

类型

返回的Set1和Set2的交集

is_disjoint(Set1, Set2) -> boolean()

类型

如果Set1和Set2不相交（没有共同的元素），则返回true，否则返回false。

is_element(Element, Set) -> boolean()

类型

如果Element是Set的一个元素，则返回true，否则返回false。

is_empty(Set) -> boolean()

类型

如果Set是空集，则返回true，否则返回false

is_member(Element, Set) -> boolean()

类型

如果Element是Set的一个元素，则返回true，否则返回false。

is_set(Term) -> boolean()

类型

如果Term看起来是一个集合，则返回true，否则返回false。

is_subset(Set1, Set2) -> boolean()

类型

当Set1的每个元素也是Set2的成员时返回true，否则返回false。

iterator(Set) -> Iter

类型

返回可用于遍历Set条目的迭代器; 见下一个/ 1。这个实施非常有效; 使用next / 1遍历整个集合只比获取使用to_list / 1的所有元素的列表并且遍历该列表稍慢。迭代器方法的主要优点是它不需要一次在内存中构建所有元素的完整列表。

iterator_from(Element, Set) -> Iter

类型

返回可用于遍历条目的迭代器Set; 见next/1。与返回的迭代器相比，差异在于返回iterator/1大于或等于的第一个元素Element。

largest(Set) -> Element

类型

返回中的最大元素Set。假设这Set不是空的。

new() -> Set

类型

返回一个新的空集。

next(Iter1) -> {Element, Iter2} | none

类型

返回{Element, Iter2}，其中Element是迭代器引用的最小元素Iter1，Iter2是用于遍历剩余元素的新迭代器，none如果没有元素保留，则为原子。

singleton(Element) -> set(Element)

返回仅包含元素的集合Element。

size(Set) -> integer() >= 0

类型

返回中Set的元素数量。

smallest(Set) -> Element

类型

返回Set中的最小元素。假设这Set不是空的。

subtract(Set1, Set2) -> Set3

类型

只返回Set1也不是Set2...

take_largest(Set1) -> {Element, Set2}

类型

返回{Element，Set2}，其中Element是Set1中最大的元素，Set2是这个元素被删除的集合。假定Set1不是空的。

take_smallest(Set1) -> {Element, Set2}

类型

返回{Element，Set2}，其中Element是Set1中最小的元素，Set2是此元素被删除的元素。假定Set1不是空的。

to_list(Set) -> List

类型

返回Set作为一份清单。

union(SetList) -> Set

类型

返回集合列表的合并（联合）集合。

union(Set1, Set2) -> Set3

类型

返回的合并（联合）组Set1和Set2。

另见

gb_trees(3)，ordsets(3)，sets(3)