路径： 集合
课程： 接口

排序集合接口

SortedSet是一个按照元素的自然顺序或提供的Comparator按升序维护元素的Set。除了普通的Set操作，SortedSet接口还提供以下操作：

范围视图 — 允许在排序集上进行任意范围操作
端点 — 返回排序集中的第一个或最后一个元素
比较器访问 — 返回用于排序集的Comparator（如果有）

SortedSet接口的代码如下。

public interface SortedSet<E> extends Set<E> {
    // 范围视图
    SortedSet<E> subSet(E fromElement, E toElement);
    SortedSet<E> headSet(E toElement);
    SortedSet<E> tailSet(E fromElement);

    // 端点
    E first();
    E last();

    // 比较器访问
    Comparator<? super E> comparator();
}

Set操作

SortedSet从Set继承的操作在排序集和普通集上的行为完全相同，有两个例外：

iterator操作返回的Iterator按顺序遍历排序集。
toArray返回的数组按顺序包含排序集的元素。

虽然接口不保证，但Java平台的SortedSet实现的toString方法返回一个包含排序集中所有元素的字符串，按顺序排列。

标准构造函数

按照惯例，所有通用的Collection实现都提供一个接受Collection的标准转换构造函数；SortedSet实现也不例外。在TreeSet中，这个构造函数根据元素的自然顺序对其进行排序。这可能是一个错误。更好的做法是动态检查指定的集合是否是SortedSet实例，并根据相同的标准（比较器或自然顺序）对新的TreeSet进行排序。因为TreeSet采取了它所采取的方法，它还提供了一个接受SortedSet的构造函数，并返回一个包含相同元素且按相同标准排序的新TreeSet。需要注意的是，决定调用这两个构造函数的是参数的编译时类型，而不是运行时类型（以及是否保留排序标准）。

SortedSet实现还提供了一个约定的构造函数，它接受一个Comparator并返回一个根据指定Comparator排序的空集合。如果将null传递给此构造函数，则返回一个根据其自然顺序对元素进行排序的集合。

范围视图操作

范围视图操作在某种程度上类似于List接口提供的操作，但有一个重大区别。范围视图对于排序集合来说是有效的，即使直接修改了后端的排序集合。这是因为排序集合的范围视图的端点是元素空间中的绝对点，而不是后端集合中的特定元素，这对于列表来说是这样的。排序集合的范围视图实际上只是窗口，显示指定部分元素空间中集合的内容。对范围视图的更改会写回到后端的排序集合，反之亦然。因此，与列表上的范围视图相比，长时间使用排序集合上的范围视图是可以的。

排序集合提供了三个范围视图操作。第一个是subSet，与subList类似，它接受两个端点。端点不是索引，而是对象，并且必须与排序集合中的元素进行比较，使用Set的Comparator或其元素的自然顺序，取决于Set用于排序的方式。与subList类似，范围是半开的，包括其低端点但不包括高端点。

因此，下面的代码告诉你在名为dictionary的字符串SortedSet中，从"doorbell"到"pickle"之间有多少个单词，包括"doorbell"但不包括"pickle"：

int count = dictionary.subSet("doorbell", "pickle").size();

同样地，下面的一行代码会删除以字母f开头的所有元素。

dictionary.subSet("f", "g").clear();

类似的技巧可以用来打印一个表格，告诉你以每个字母开头的单词有多少个。

for (char ch = 'a'; ch <= 'z'; ) {
    String from = String.valueOf(ch++);
    String to = String.valueOf(ch);
    System.out.println(from + ": " + dictionary.subSet(from, to).size());
}

假设你想要查看一个闭区间，它包含了两个端点，而不是一个开区间。如果元素类型允许计算给定值在元素空间中的后继值，只需请求subSet从lowEndpoint到successor(highEndpoint)。虽然这并不完全明显，但字符串s在String的自然顺序中的后继值是s + "\0"，即在s后附加一个null字符。

因此，下面的一行代码告诉你在字典中从"doorbell"到"pickle"之间有多少个单词，包括doorbell和pickle。

count = dictionary.subSet("doorbell", "pickle\0").size();

类似的技巧可以用来查看一个开放区间，该区间不包含端点。从lowEndpoint到highEndpoint的开放区间视图是从successor(lowEndpoint)到highEndpoint的半开区间。使用以下代码计算在"doorbell"和"pickle"之间有多少个单词，不包括两者。

count = dictionary.subSet("doorbell\0", "pickle").size();

SortedSet接口还包含两个range-view操作——headSet和tailSet，两者都接受一个单一的Object参数。前者返回SortedSet的初始部分的视图，不包括指定的对象。后者返回SortedSet的最后部分的视图，从指定的对象开始，直到SortedSet的末尾。因此，以下代码允许您将字典视为两个不相交的卷（a-m和n-z）。

SortedSet<String> volume1 = dictionary.headSet("n");
SortedSet<String> volume2 = dictionary.tailSet("n");

端点操作

SortedSet接口包含返回排序集合中第一个和最后一个元素的操作，分别被称为first和last。除了显而易见的用途之外，last还允许绕过SortedSet接口的一个缺陷。你希望对SortedSet做的一件事是进入Set的内部并向前或向后迭代。从内部向前走很容易：只需获取一个tailSet并对其进行迭代。不幸的是，没有简单的方法可以向后走。

下面的惯用法获得元素空间中小于指定对象o的第一个元素。

Object predecessor = ss.headSet(o).last();

这是从排序集合内部的一个点向后移动一个元素的好方法。可以重复应用它以向后迭代，但这非常低效，每返回一个元素就需要进行一次查找。

比较器访问器

SortedSet接口包含一个叫做comparator的访问器方法，该方法返回用于对集合进行排序的Comparator，如果集合根据其元素的自然顺序进行排序，则返回null。提供该方法是为了可以将排序集合复制到具有相同排序的新排序集合中。它被SortedSet构造函数使用，如前面所述。