Java中的sorting数组列表
我很困惑，我找不到一个快速的答案。 我本质上是在Java中寻找一个实现了java.util.List接口的数据结构，但它按照sorting顺序存储它的成员。 我知道你可以使用一个正常的ArrayList并使用Collections.sort() ，但我有一个场景，我偶尔添加，并经常从列表中检索成员，我不想每次都sorting检索一个成员，以防一个新的被添加。 任何人都可以指向我在JDK甚至是第三方库中存在的东西吗？
编辑 ：数据结构将需要保留重复。
答案的总结 ：我发现这一切非常有趣，并且学到了很多东西。 Aioobe特别值得一提的是他在试图达到我上面的要求（主要是一个支持重复的sortingjava.util.List实现）的毅力。 我已经接受了他的答案，因为对于我所问的问题而言，他的答案是最准确的，而且即使我问的并不是我所需要的，我也多半想到了我所寻找的东西的含意。
我所要求的问题在于List接口本身以及接口中可选方法的概念。 引用javadoc：
这个接口的用户可以精确地控制每个元素插入到列表中的哪个位置。
插入到已sorting的列表中不能精确控制插入点。 然后，你必须考虑如何处理一些方法。 以add为例：
public boolean add（Object o）
Appends the specified element to the end of this list (optional operation).
你现在处于不舒服的情况1）打破合同，并实施加分的版本2）让add添加一个元素到列表的末尾，打破你的sorting顺序3）离开add （作为其可选的）通过抛出一个UnsupportedOperationException并实现另一种按sorting顺序添加项目的方法。
选项3可能是最好的，但我觉得它有一个不能使用的add方法和另一个不在接口中的sortedAdd方法。
其他相关解决scheme（无特定顺序）：
- java.util.PriorityQueue这可能是最接近我所需要的，而不是我所要求的。 在我的情况下，队列不是对象集合的最精确的定义，但是在function上它完成了我所需要的一切。
- net.sourceforge.nite.util.SortedList 。 然而，这个实现通过在
add(Object obj)方法中实现sorting来破坏List接口的契约，而奇怪地，add(int index, Object obj)没有效果方法。 一般共识build议throw new UnsupportedOperationException()在这种情况下可能是一个更好的select。 - 番石榴的TreeMultiSet一个支持重复的集合实现
- ca.odell.glazedlists.SortedList这个类在javadoc中有
Warning: This class breaks the contract required by List
简约的解决scheme
这是一个“最小”的解决scheme。
class SortedArrayList<T> extends ArrayList<T> { @SuppressWarnings("unchecked") public void insertSorted(T value) { add(value); Comparable<T> cmp = (Comparable<T>) value; for (int i = size()-1; i > 0 && cmp.compareTo(get(i-1)) < 0; i--) Collections.swap(this, i, i-1); } }
插入以线性时间运行，但无论如何，您将使用ArrayList（插入元素右侧的所有元素都必须以某种方式移动）。
在ClassCastException中插入一些不可比较的结果。 （这也是PriorityQueue采用的方法： 依赖于自然sorting的优先级队列也不允许插入不可比较的对象（这样做可能导致ClassCastException）。 ）
重写List.add
请注意，重写List.add （或List.addAll ）就可以直接违反接口规范 。 你可以做的是重写这个方法抛出一个UnsupportedOperationException 。
从List.add的文档：
boolean add(E e)
将指定的元素附加到此列表的末尾（可选操作）。
同样的推理适用于两个版本的add ， addAll和set两个版本。 （所有这些都是根据列表界面的可选操作。）
一些testing
SortedArrayList<String> test = new SortedArrayList<String>(); test.insertSorted("ddd"); System.out.println(test); test.insertSorted("aaa"); System.out.println(test); test.insertSorted("ccc"); System.out.println(test); test.insertSorted("bbb"); System.out.println(test); test.insertSorted("eee"); System.out.println(test);
….打印：
[ddd] [aaa, ddd] [aaa, ccc, ddd] [aaa, bbb, ccc, ddd] [aaa, bbb, ccc, ddd, eee]
使用java.util.PriorityQueue 。
看看SortedList
这个类实现了一个sorting列表。 它是用比较器构build的，可以比较两个对象并相应地对对象进行sorting。 当你添加一个对象到列表中时，它被插入到正确的位置。 根据比较器相等的对象，将按照它们被添加到该列表的顺序在列表中。 仅添加比较器可以比较的对象。
当列表已经包含根据比较器相等的对象时，新对象将被立即插入到这些其他对象之后。
你可以尝试番石榴的 TreeMultiSet 。
Multiset<Integer> ms=TreeMultiset.create(Arrays.asList(1,2,3,1,1,-1,2,4,5,100)); System.out.println(ms);
列表通常保留添加项目的顺序。 你肯定需要一个列表 ，或者一个有序的集合 （比如TreeSet<E> ）对你来说可以吗？ 基本上，你需要保留重复吗？
这对你来说可能有点太重了，但是GlazedLists有一个SortedList ，可以很好地用作表或JList的模型
Aioobe的方法是要走的路。 我想build议他的解决scheme，但以下改善。
class SortedList<T> extends ArrayList<T> { public void insertSorted(T value) { int insertPoint = insertPoint(value); add(insertPoint, value); } /** * @return The insert point for a new value. If the value is found the insert point can be any * of the possible positions that keeps the collection sorted (.33 or 3.3 or 33.). */ private int insertPoint(T key) { int low = 0; int high = size() - 1; while (low <= high) { int mid = (low + high) >>> 1; Comparable<? super T> midVal = (Comparable<T>) get(mid); int cmp = midVal.compareTo(key); if (cmp < 0) low = mid + 1; else if (cmp > 0) high = mid - 1; else { return mid; // key found } } return low; // key not found } }
使用大型列表时，aioobe的解决scheme变得非常慢。 使用列表sorting的事实允许我们使用二分查找find新值的插入点。
我也将使用inheritance的组合，沿线的东西
SortedList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
你可以inheritanceArrayList，并且在添加任何元素之后调用Collections.sort（this） – 你需要重写两个版本的add和两个addAll来做到这一点。
性能不如在适当的地方插入元素的更聪明的实现，但它可以完成这项工作。 如果增加清单是很less的，那么清单上所有操作的摊销成本应该很低。
我认为SortedSets / Lists和“普通”可sorting集合之间的select取决于您是否仅需要为了演示目的或几乎在运行时间的每个点进行sorting。 使用sorting后的集合可能会更加昂贵，因为每次插入元素时都会进行sorting。
如果你不能在JDK中select一个集合，你可以看看Apache Commons集合
由于目前提出的通过中断Collection API来实现sorting列表的实现，具有自己的树或类似的实现，所以我很好奇基于TreeMap的实现将如何执行。 （特别是TreeSet也是基于TreeMap的）
如果有人也对此感兴趣，他或她可以随意查看：
的TreeList
它是核心库的一部分，当然你可以通过Maven依赖关系添加它。 （Apache许可证）
目前这个实现似乎比guava SortedMultiSet和Apache Commons库的TreeList在相同的层次上相当好。
但是，如果不仅仅是我会testing执行，以确保我没有错过重要的事情，我会很高兴。
最好的祝福！
我有同样的问题。 于是我拿了java.util.TreeMap的源代码编写了IndexedTreeMap 。 它实现了我自己的IndexedNavigableMap ：
public interface IndexedNavigableMap<K, V> extends NavigableMap<K, V> { K exactKey(int index); Entry<K, V> exactEntry(int index); int keyIndex(K k); }
这个实现是基于在更改红黑树时更新节点权重。 权重是给定节点下面的子节点的数量，加上一个自我。 例如，当一棵树向左旋转时：
private void rotateLeft(Entry<K, V> p) { if (p != null) { Entry<K, V> r = p.right; int delta = getWeight(r.left) - getWeight(p.right); p.right = r.left; p.updateWeight(delta); if (r.left != null) { r.left.parent = p; } r.parent = p.parent; if (p.parent == null) { root = r; } else if (p.parent.left == p) { delta = getWeight(r) - getWeight(p.parent.left); p.parent.left = r; p.parent.updateWeight(delta); } else { delta = getWeight(r) - getWeight(p.parent.right); p.parent.right = r; p.parent.updateWeight(delta); } delta = getWeight(p) - getWeight(r.left); r.left = p; r.updateWeight(delta); p.parent = r; } }
updateWeight只是更新权重，直到根：
void updateWeight(int delta) { weight += delta; Entry<K, V> p = parent; while (p != null) { p.weight += delta; p = p.parent; } }
而当我们需要通过索引来查找元素时，这里是使用权重的实现：
public K exactKey(int index) { if (index < 0 || index > size() - 1) { throw new ArrayIndexOutOfBoundsException(); } return getExactKey(root, index); } private K getExactKey(Entry<K, V> e, int index) { if (e.left == null && index == 0) { return e.key; } if (e.left == null && e.right == null) { return e.key; } if (e.left != null && e.left.weight > index) { return getExactKey(e.left, index); } if (e.left != null && e.left.weight == index) { return e.key; } return getExactKey(e.right, index - (e.left == null ? 0 : e.left.weight) - 1); }
还有一个非常方便的find一个关键的索引：
public int keyIndex(K key) { if (key == null) { throw new NullPointerException(); } Entry<K, V> e = getEntry(key); if (e == null) { throw new NullPointerException(); } if (e == root) { return getWeight(e) - getWeight(e.right) - 1;//index to return } int index = 0; int cmp; index += getWeight(e.left); Entry<K, V> p = e.parent; // split comparator and comparable paths Comparator<? super K> cpr = comparator; if (cpr != null) { while (p != null) { cmp = cpr.compare(key, p.key); if (cmp > 0) { index += getWeight(p.left) + 1; } p = p.parent; } } else { Comparable<? super K> k = (Comparable<? super K>) key; while (p != null) { if (k.compareTo(p.key) > 0) { index += getWeight(p.left) + 1; } p = p.parent; } } return index; }
您可以在http://code.google.com/p/indexed-tree-map/find这项工作的结果。;
TreeSet / TreeMap（以及来自索引树映射项目的索引对应项）不允许重复的键，您可以使用1个键作为值的数组。 如果你需要一个带有重复项的SortedSet，使用TreeMap的值作为数组。 我会这样做的。
