在Java中有SortedSet和SortedMap接口.两者都属于Java的标准集合框架,并提供了一种访问元素的排序方式.
但是,根据我的理解SortedList,Java中没有.您可以使用java.util.Collections.sort()对列表进行排序.
知道为什么它的设计是这样的吗？
我很困惑,我找不到快速的答案.我基本上在Java中寻找一个实现java.util.List接口的数据结构,但它以排序顺序存储其成员.我知道你可以使用普通ArrayList并使用Collections.sort()它,但我有一个场景,我偶尔会添加并经常从我的列表中检索成员,我不希望每次检索成员时都要对它进行排序,以防万一新增了一个.有人能指出我存在于JDK甚至第三方库中的这样的东西吗？
编辑:数据结构将需要保留重复.
答案摘要:我发现所有这些都非常有趣并且学到了很多东西.Aioobe尤其值得一提,因为他坚持不懈地努力实现上述要求(主要是支持重复的有序java.util.List实现).我已经接受了他的答案,因为我提出的问题是最准确的,而且最让我发现的是我正在寻找的内容的影响,即使我问的不完全是我所需要的.
我要求的问题在于List接口本身以及接口中可选方法的概念.引用javadoc:
该接口的用户可以精确控制列表中每个元素的插入位置.
插入排序列表无法精确控制插入点.然后,你必须考虑如何处理一些方法.就拿add例如:
public boolean add(Object o)
Run Code Online (Sandbox Code Playgroud)Appends the specified element to the end of this list (optional operation).
你现在处于令人不安的境地:1)打破合同并实现添加的排序版本2)让add一个元素添加到列表的末尾,打破你的排序顺序3)add抛出(作为其可选)抛出一UnsupportedOperationException和实施这增加了在一个有序的物品的另一种方法.
选项3可能是最好的,但我发现它有一个你不能使用的添加方法和另一个不在界面中的sortedAdd方法令人讨厌.
其他相关解决方案(无特定顺序):
add(Object obj)方法中实现排序来打破List接口的契约,并且奇怪地具有无效方法add(int index, Object obj).一般共识表明throw new UnsupportedOperationException()在这种情况下可能是更好的选择.Warning: This class breaks the contract required by List具体来说,我需要一个集合,它使用一个字段A进行访问,使用另一个字段(字段S)进行排序,但是接受重复的已排序集合就足够了.
我经常到这一点,我需要这个集合,TreeMap不是一个选项,因为它不允许重复.所以现在是时候问这里了.stackoverflow 在这里和这里指出了几种解决方法- 即:
TreeMap<Field_S, List<Value>>:对我来说问题是列表的内存开销和原始键的装箱谁有更好的建议？或者我应该对自己的排序数据结构(哪一个？)起作用？其他来源(Java,开源,单元测试和小deps)也不错.
更新
关于我目前用例的更多细节(虽然我上次有类似的需求).我有一个集合(有数百万)我想要的参考
所以对于斐波那契堆的所有呼声,但我担心它每个元素的开销太多 - >这就是我考虑更高效的"排序+分段数组"解决方案的原因.
ListJava中是否存在基于提供的维护顺序的现有实现Comparator？
可以通过以下方式使用的东西:
Comparator<T> cmp = new MyComparator<T>();
List<T> l = new OrderedList<T>(cmp);
l.add(someT);
使得someT被插入,使得在列表中的顺序是根据保持cmp
(关于@andersoj的建议我正在完成我的问题,还有一个请求)
此外,我希望能够按排序顺序遍历列表而不删除元素,即:
T min = Const.SMALLEST_T;
for (T e: l) {
assertTrue(cmp.compare(min, e) >= 0);
min = e;
}
应该通过.
欢迎所有的建议(除了告诉我Collections.sort在无序的完整列表中使用),但是,我更喜欢某些内容java.*或最终,org.apache.*因为此时很难引入新的库.
注意:(UPDATE4)我意识到这种列表的实现性能不足.有两种一般方法:
没有1. CPU缓存未命中问题No 2.在数组中移位元素有问题.
UPDATE2:
TreeSet不起作用,因为它使用提供的比较器(MyComparator)来检查是否相等,并基于它假设元素相等并排除它们.我需要那个比较器只用于排序,而不是"唯一性"过滤(因为元素按其自然顺序不相等)
UPDATE3:
PriorityQueue不能正常工作List(因为我需要),因为没有办法按照"排序"的顺序遍历它,要按排序顺序获取元素,你必须从集合中删除它们.
更新:
可能重复:
java中的排序集合
我想知道Java中是否有内置类允许我添加自动排序的元素.如果两个元素的排名相同,则排序应保留添加顺序.我认为这将是一个优先级队列,但不应该"弹出"元素,我希望它们留在列表中.
显然我可以自己实现这个,但我宁愿使用Java语言实现的东西(更少的bug测试/对未来的项目也很好,而不是导入我自己的代码).
如果在语言中没有这样的东西,我也会对第三方来源感兴趣.
我需要一个Collection对元素进行排序,但不会删除重复项.
我已经去了TreeSet,因为TreeSet实际上将值添加到支持TreeMap:
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
TreeMap使用Comparators compare逻辑删除重复项
我写了一个Comparator在相同元素的情况下返回1而不是0.因此,在相同元素的情况下,TreeSet使用它Comparator不会覆盖副本,只会对其进行排序.
我已经测试了它的简单String对象,但我需要一组自定义对象.
public static void main(String[] args)
{
List<String> strList = Arrays.asList( new String[]{"d","b","c","z","s","b","d","a"} );
Set<String> strSet = new TreeSet<String>(new StringComparator());
strSet.addAll(strList);
System.out.println(strSet);
}
class StringComparator implements Comparator<String>
{
@Override
public int compare(String s1, String s2)
{
if(s1.compareTo(s2) == 0){
return 1;
}
else{
return s1.compareTo(s2);
}
}
} …我只是想尝试使用原生Java二进制搜索,希望它总能找到第一次出现.但它并不总是第一次出现,我在这里做错了什么？
import java.util.*;
class BinarySearchWithComparator
{
public static void main(String[] args)
{
// Please scroll down to see 'User' class implementation.
List<User> l = new ArrayList<User>();
l.add(new User(10, "A"));
l.add(new User(10, "A"));
l.add(new User(10, "A"));
l.add(new User(20, "B"));
l.add(new User(20, "B"));
l.add(new User(20, "B"));
l.add(new User(20, "B"));
l.add(new User(20, "B"));
l.add(new User(20, "B"));
l.add(new User(20, "B"));
l.add(new User(30, "C"));
l.add(new User(30, "C"));
l.add(new User(30, "C"));
l.add(new User(30, "C"));
Comparator<User> c = new Comparator<User>() {
public int compare(User u1, User u2) …假设我正在构建一个TreeSet对象，其顺序仅取决于一个值。
我不能做
TreeSet<Foo> tree = new TreeSet<>(Comparator.comparingInt(Foo::getX));
因为如果我添加两个Foo具有相同对象的不同对象x，那么一个将替换另一个（即，如果我这样做，tree.add(foo1)并且，将代替）。tree.add(foo2)tree.size()12
我可以比较 的每个字段Foo，但我希望 的两个实例Foo被视为不同，即使每个字段都相同。
一种“几乎有效”的解决方案是
TreeSet<Foo> tree = new TreeSet<>(Comparator.comparingInt(Foo::getX).thenComparing(Foo::hashCode));
但当存在哈希冲突时，这会失败。
总之，我正在寻找类似的东西
TreeSet<Foo> tree = new TreeSet<>(Comparator.comparingInt(Foo::getX).thenComparing(Foo::getInternalAddress));
但我们当然无法使用这样的方法。
我知道有解决方法：
TreeMap<Foo, Integer>（并比较所有字段）来给出Foo特定对象的数量xTreeMap<Foo, List<Foo>>（或TreeMap<Integer, List<Foo>>键为x）。但如果“重复”的 foo 很少，那么所有单例列表都会浪费空间。因此，虽然我知道 a 有解决方法TreeMap，但我仍然想知道是否有一种方法可以仅使用 a 来做到这一点TreeSet。