在Java中有SortedSet和SortedMap接口。两者都属于Java Collections框架,并提供了一种访问元素的排序方式。
然而,在我的理解中,Java中没有SortedList。您可以使用java.util.Collections.sort()对列表进行排序。
知道它为什么是这样设计的吗?
在Java中有SortedSet和SortedMap接口。两者都属于Java Collections框架,并提供了一种访问元素的排序方式。
然而,在我的理解中,Java中没有SortedList。您可以使用java.util.Collections.sort()对列表进行排序。
知道它为什么是这样设计的吗?
当前回答
我认为以上都不能回答这个问题,原因如下:
Since same functionality can be achieved by using other collections such as TreeSet, Collections, PriorityQueue..etc (but this is an alternative which will also impose their constraints i.e. Set will remove duplicate elements. Simply saying even if it does not impose any constraint, it does not answer the question why SortedList was not created by java community) Since List elements do not implements compare/equals methods (This holds true for Set & Map also where in general items do not implement Comparable interface but when we need these items to be in sorted order & want to use TreeSet/TreeMap,items should implement Comparable interface) Since List uses indexing & due to sorting it won't work (This can be easily handled introducing intermediate interface/abstract class)
但没有人告诉它背后的确切原因,因为我相信这类问题最好由java社区自己来回答,因为它只有一个具体的答案,但让我尽我所能回答如下:
我们知道排序是一个昂贵的操作,列表和Set/Map之间有一个基本的区别,列表可以有重复,而Set/Map不能。 这就是我们为Set/Map提供TreeSet/TreeMap形式的默认实现的核心原因。在内部,这是一个红黑树,每个操作(插入/删除/搜索)的复杂度为O(log N),其中由于重复列表无法适合这种数据存储结构。
Now the question arises we could also choose a default sorting method for List also like MergeSort which is used by Collections.sort(list) method with the complexity of O(N log N). Community did not do this deliberately since we do have multiple choices for sorting algorithms for non distinct elements like QuickSort, ShellSort, RadixSort...etc. In future there can be more. Also sometimes same sorting algorithm performs differently depending on the data to be sorted. Therefore they wanted to keep this option open and left this on us to choose. This was not the case with Set/Map since O(log N) is the best sorting complexity.
其他回答
可以这样想:List接口有add(int index, E element), set(int index, E element)这样的方法。约定是,一旦你在X位置添加了一个元素,你就会在那里找到它,除非你在它之前添加或删除元素。
如果任何列表实现都以某种顺序存储元素,而不是基于索引,那么上述列表方法就没有意义了。
因为所有列表都已经按照条目的添加顺序(FIFO顺序)“排序”了,所以可以使用java.util.Collections.sort()使用另一种顺序“使用”它们,包括元素的自然顺序。
编辑:
列表作为数据结构的基础是有趣的是插入项的顺序。
集合没有这个信息。
如果您想通过添加时间来排序,请使用List。如果您想按其他标准排序,请使用SortedSet。
https://github.com/geniot/indexed-tree-map
考虑使用索引树映射。它是一个增强的JDK的TreeSet,它提供了通过索引访问元素的功能,并且无需迭代或隐藏的底层列表来备份树,就可以找到元素的索引。该算法基于每次有变化时更新已更改节点的权重。
对于任何新手来说,从2015年4月开始,Android现在在支持库中有一个SortedList类,专门用于与RecyclerView一起工作。这是关于它的博客文章。
Set和Map是非线性数据结构。列表是线性数据结构。
树数据结构SortedSet和SortedMap接口使用常用的红黑树实现算法分别实现TreeSet和TreeMap。因此,它确保没有重复的项(或Map情况下的键)。
List已经维护了有序的集合和基于索引的数据结构,树不是基于索引的数据结构。 树根据定义不能包含重复项。 在List中,我们可以有副本,所以没有TreeList(即。没有SortedList)。 List按插入顺序维护元素。因此,如果我们想对列表进行排序,就必须使用java.util.Collections.sort()。它根据元素的自然顺序,将指定的列表按升序排序。