SortedSet 接口

原文： https://docs.oracle.com/javase/tutorial/collections/interfaces/sorted-set.html

SortedSet 是 Set ，按升序维持其元素，根据元素的自然顺序或根据SortedSet创建时提供的Comparator进行排序时间。除了正常的Set操作外，SortedSet接口还提供以下操作：

  • Range view - 允许对有序集进行任意范围操作
  • Endpoints - 返回有序集合中的第一个或最后一个元素
  • Comparator access - 返回用于对集合进行排序的Comparator（如果有）

接下来是SortedSet接口的代码。

  1. public interface SortedSet<E> extends Set<E> {
  2.     // Range-view
  3.     SortedSet<E> subSet(E fromElement, E toElement);
  4.     SortedSet<E> headSet(E toElement);
  5.     SortedSet<E> tailSet(E fromElement);
  7.     // Endpoints
  8.     E first();
  9.     E last();
  11.     // Comparator access
  12.     Comparator<? super E> comparator();
  13. }

设置操作

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

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

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

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

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

范围视图操作

range-view操作有点类似于List接口提供的操作，但有一个很大的区别。即使直接修改了后备排序集，排序集的范围视图仍然有效。这是可行的，因为有序集的范围视图的端点是元素空间中的绝对点，而不是后备集合中的特定元素，如列表的情况。有序集合的range-view实际上只是集合的任何部分位于元素空间的指定部分的窗口。对range-view的更改会写回后退排序集，反之亦然。因此，与列表上的range-view不同，可以长时间在排序集上使用range-view。

排序集提供三个range-view操作。第一个subSet采用两个端点，如subList。而不是索引，端点是对象，必须与有序集合中的元素相比较，使用Set的Comparator或其元素的自然顺序，无论Set用于自我排序。与subList类似，范围是半开放的，包括其低端点但不包括高端点。

因此，以下代码行告诉您"doorbell"和"pickle"之间有多少字，包括"doorbell"但不包括"pickle"，包含在称为dictionary的字符串的SortedSet中：

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

以类似的方式，以下单行删除以字母f开头的所有元素。

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

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

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

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

因此，下面的单线程告诉您"doorbell"和"pickle"之间有多少单词，包括门铃*和 _ pickle，都包含在字典中。

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

可以使用类似的技术来查看开放区间，其中既不包含端点也不包含端点。从lowEndpoint到highEndpoint的开路间隔视图是从successor(lowEndpoint)到highEndpoint的半开间隔。使用以下内容计算"doorbell"和"pickle"之间的字数，不包括两者。

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

SortedSet接口包含两个range-view操作 - headSet和tailSet，两者都采用单个Object参数。前者返回后备SortedSet的初始部分的视图，最多但不包括指定的对象。后者返回背景SortedSet的最后部分的视图，从指定对象开始并继续到背景SortedSet的末尾。因此，以下代码允许您将字典视为两个不相交的volumes（a-m和n-z）。

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

端点操作

SortedSet接口包含返回有序集合中第一个和最后一个元素的操作，毫不奇怪地称为first和last。除了明显的用途之外，last还允许解决SortedSet接口缺陷的问题。你想用SortedSet做的一件事就是进入Set的内部并向前或向后迭代。从内部向前行很容易：只需得到一个tailSet并迭代它。不幸的是，没有简单的方法可以倒退。

以下习语获得的元素空间中的第一个元素小于指定对象o。

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

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

比较器访问器

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