有没有一种集合提供排序、无重复元素和subList(index, index)方法？

Question

我需要一个集合，它不允许有重复元素，并且可以排序，同时支持subList(startIndex, endIndex)方法。是否存在这样的集合，如果存在，是什么集合类型呢？ TreeMap没有重复元素，也可排序，但不支持subList(index, index)方法。ArrayList支持subList(index, index)方法，但可能包含重复值。是否有其他选择？

- emeraldhieu

---

TreeMap甚至不是一个Collection。最接近的是Set或SortedSet，它们都是Collection。 - Steve Kuo

TreeMap有两个方法subMap(K fromKey, K toKey)，可能可以满足您的需求，而TreeSet则有相应的subSet()方法。 - rsp

Answer 1

最接近的东西是 SortedSet。

http://download.oracle.com/javase/6/docs/api/java/util/SortedSet.html

然而，它不允许您执行sublist(int start, int end)。您可以使用subSet(E start, E end)，但从您的描述中不清楚它是否符合您的需求。如果您需要实际索引的概念，则可能需要某种形式的List。如果不重复很重要，则Set是一个很好的起点。任何Collection都将允许您基于Comparator<E>进行排序，因此该标准并不重要 - 只需确保在访问之前进行排序。

- Thorn G

Answer 2

我相信你正在寻找一个叫做“顺序统计树”的东西，它是一种平衡的二叉搜索树，附加了额外的信息，以便在O(log n)时间内查询任何索引处的元素。因为它是一棵二叉搜索树，所以不允许重复，并且因为您可以查询给定位置的元素，所以您可以高效地实现子范围；只需返回一个新的树视图，其中您跟踪起始和结束索引，这样当遍历树时，您可以跨越特定的范围。

Java标准库没有提供此数据结构的实现（我实际上不知道有哪种语言提供了它）。我在谷歌的缓存中找到了这个顺序统计树的实现，其中包含两个文件：

• 一个红黑树的实现，点击此处查看。
• 使用这段代码将其转化为一棵顺序统计树，点击此处查看。

希望能对你有所帮助！

- templatetypedef

Answer 3

使用索引树映射，您可以这样做：

SortedSet range = indexedTreeSet.subSet(
                          indexedTreeSet.exact(indexFrom),
                          indexedTreeSet.exact(indexTo));

- Vitaly Sazanovich