在 Java 中，您可以建立一个ArrayListwith items 然后调用：
Collections.sort(list, comparator);
无论如何在列表时传递比较器，像你一样创建TreeMap？
目标是能够将一个元素添加到列表中，而不是将其自动附加到列表的末尾，列表将根据 保持自身排序Comparator，并将新元素插入到由 确定的索引处Comparator。所以基本上列表可能必须根据添加的每个新元素重新排序。
无论如何，是否可以通过Comparator或其他类似方式以这种方式实现这一目标？
您可以更改 ArrayList 的行为
List<MyType> list = new ArrayList<MyType>() {
public boolean add(MyType mt) {
super.add(mt);
Collections.sort(list, comparator);
return true;
}
};
注意：PriorityQueue 不是 List，如果您不关心它是什么类型的集合，最简单的方法是使用 TreeSet，它就像 TreeMap 但它是一个集合。PriorityQueue 的唯一优势是允许重复。
注意：resorting 对于大型集合不是很有效，使用二分搜索和插入条目会更快。（但更复杂）
编辑：很大程度上取决于您需要“列表”做什么。我建议您为 ArrayList、LinkedList、PriorityQueue、TreeSet 或其他排序集合之一编写一个 List 包装器，并实现将实际使用的方法。这样您就可以很好地了解集合的要求，并且可以确保它适合您。
编辑（2）：因为人们对使用 binarySearch 很感兴趣。;)
List<MyType> list = new ArrayList<MyType>() {
public boolean add(MyType mt) {
int index = Collections.binarySearch(this, mt);
if (index < 0) index = ~index;
super.add(index, mt);
return true;
}
};
每个人都在建议PriorityQueue。但是，重要的是要意识到，如果您遍历a 的内容PriorityQueue，元素将不会按排序顺序排列。您只能保证从 methods , 等中获得“最小”peek()元素poll()。
ATreeSet似乎更合适。需要注意的是，作为 a Set，它不能包含重复的元素，并且它不支持使用索引进行随机访问。
JDK中没有SortedList实现可能是有充分理由的。我个人想不出在 JDK 中有一个自动排序的理由。
过早的优化出了问题。如果列表的读取频率不如插入的频率高，那么您将无缘无故地浪费循环排序。在读取之前进行排序会更具反应性，并且在boolean某个地方指示列表在读取之前是否需要排序会更好。
Iterator问题是您只在使用or循环遍历列表时才真正关心顺序for each，因此在任何迭代代码之前调用Collections.sort()可能比尝试在每次插入时始终保持列表排序更高效。
由于重复存在歧义List，您如何确定地对重复进行排序？有SortedSet，这是有道理的，因为它的独特性。但是对 a 进行排序List可能会因为重复项和其他约束的副作用而变得更加复杂，例如制作每个对象Comparable，或者正如我在代码中显示的那样，必须有一个Comparator可以代替工作的 a。
.add()如果您有一些非常特殊的情况，自动排序List会很有用，那么您可能会做的一件事是将实现子类化List并覆盖.add()以执行Collections.sort(this, comparator)您传递给自定义构造函数的操作。我之所以使用LinkedList而不是ArrayList出于某种原因，ArrayList是以自然插入排序顺序List开头的。如果你想要一个不断排序的，它也有能力.add()在一个非常无用的索引上List，这将不得不以某种可能不太理想的方式处理。根据Javadoc；
void add(int index, Object element)
在此列表中的指定位置插入指定元素（可选操作）。
所以它只是抛出是可以接受的，或者如果你在方法的 JavaDoc 中记录它，UnSupportedOperationException你可以忽略index并委托给。.add(Object element);
通常，当您想要进行大量插入/删除和排序时，您会使用 a LinkedList，因为使用 `List' 可以获得更好的性能特征。
这是一个简单的例子：
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
public class SortedList<E> extends LinkedList<E>
{
private Comparator<E> comparator;
public SortedList(final Comparator<E> comparator)
{
this.comparator = comparator;
}
/**
* this ignores the index and delegates to .add()
* so it will be sorted into the correct place immediately.
*/
@Override
public void add(int index, Object element)
{
this.add(element);
}
@Override
public boolean add(final E e)
{
final boolean result = super.add(e);
Collections.sort(this, this.comparator);
return result;
}
}
或者，您只能在获取 时进行Iterator排序，如果排序顺序仅在迭代List. 这将涵盖在每次迭代之前不必调用客户端代码的用例，Collections.sort()并将该行为封装到类中。
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
public class SortedList<E> extends LinkedList<E>
{
private Comparator<E> comparator;
public SortedList(final Comparator<E> comparator)
{
this.comparator = comparator;
}
@Override
public Iterator<E> iterator()
{
Collections.sort(this, this.comparator);
return super.iterator();
}
}
当然，需要进行错误检查和处理以查看是否存在以及如果Comparator是null这种情况该怎么办，但这给了你这个想法。您仍然没有任何确定性的方法来处理重复项。
如果你正在使用 Guava 并且你应该使用，你可以使用
Ordering.immutableSortedCopy()只有当您需要迭代并完成它时。
Something like TreeSet (or TreeMultiset in case you need duplicates) with more efficient random access is possible, but I doubt it was implemented in Java. Making each node of the tree remembers the size of its left subtree allows accessing an element by index in time O(log(size)) which is not bad.
In order to implement it, you'd need to rewrite a good portion of the underlying TreeMap.
我会使用Guava TreeMultiset假设你想要一个List，因为你可能有重复的元素。它会做你想做的一切。它没有的一件事是基于索引的访问，这没有多大意义，因为无论如何您都没有将元素放在您选择的索引处。要注意的另一件事是它实际上不会存储对象的重复项equal......只是对它们总数的计数。
SortedSet 和 List 的主要区别在于：
您似乎想要两者的融合：自动排序和允许（合理快速）索引访问。根据数据的大小以及索引读取或添加新元素的频率，我的想法如下：
在任何情况下，SortedSet 和 List 的接口和契约都不是真正兼容的，所以你会希望 List 部分是只读的（或只读和删除），不允许设置和添加，并且有一个额外的对象（可能实现 Collection 接口）用于添加对象。
考虑一下我在面临类似问题时创建的索引树图，您将能够通过索引访问元素并获取元素的索引，同时保持排序顺序。可以将重复项作为同一键下的值放入数组中。
公共收藏有TreeBag
最初我建议PriorityQueue，但它的迭代顺序是未定义的，所以它没有用，除非你通过获取队列克隆的头部直到它变空来迭代它。
由于您最有可能关心迭代顺序，我相信您可以覆盖该iterator()方法：
public class OrderedIterationList<E> extends ArrayList<E> {
@Override
public Iterator<E> iterator() {
Object[] array = this.toArray(); // O(1)
Arrays.sort(array);
return Arrays.asList(array).iterator(); // asList - O(1)
}
}
您可以通过存储已排序集合的快照来改进这一点，并用于modCount验证集合是否未更改。
根据用例，这可能比 Peter 的建议效率低或高。例如，如果您添加多个项目并进行迭代。（在迭代之间不添加项目），那么这可能更有效。
拥有任何排序结构的添加/indexOf/remove/get 元素的时间少于 O(n) 的唯一方法是使用树。在这种情况下，操作通常有 O(log2n) 并且遍历就像 O(1)。
O(n) 只是一个链表。
编辑：插入带有二进制搜索的链表。对于插入操作，不使用二进制结构，而不是小尺寸，这应该是最佳的。
@Peter：有算法 w/ O(log2n) 比较（很慢）插入和 O(n) 移动。如果您需要覆盖 LinkedList，那就这样吧。但这是尽可能整洁的。我保持算法尽可能简洁以便易于理解，可以对其进行一些优化。
package t1;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Random;
public class SortedList {
private static <T> int binarySearch(ListIterator<? extends Comparable<? super T>> i, T key){
int low = 0;
int high= i.previousIndex();
while (low <= high) {
int mid = (low + high) >>> 1;
Comparable<? super T> midVal = get(i, mid);
int cmp = midVal.compareTo(key);
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid;
}
return -(low + 1); // key not found
}
private static <T> T get(ListIterator<? extends T> i, int index) {
T obj = null;
int pos = i.nextIndex();
if (pos <= index) {
do {
obj = i.next();
} while (pos++ < index);
} else {
do {
obj = i.previous();
} while (--pos > index);
}
return obj;
}
private static void move(ListIterator<?> i, int index) {
int pos = i.nextIndex();
if (pos==index)
return;
if (pos < index) {
do {
i.next();
} while (++pos < index);
}
else {
do {
i.previous();
} while (--pos > index);
}
}
@SuppressWarnings("unchecked")
static <T> int insert(List<? extends Comparable<? super T>> list, T key){
ListIterator<? extends Comparable<? super T>> i= list.listIterator(list.size());
int idx = binarySearch(i, key);
if (idx<0){
idx=~idx;
}
move(i, idx);
((ListIterator<T>)i).add(key);
return i.nextIndex()-1;
}
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<Integer>();
LinkedList<Integer> unsorted = new LinkedList<Integer>();
Random r =new Random(11);
for (int i=0;i<33;i++){
Integer n = r.nextInt(17);
insert(list, n);
unsorted.add(n);
}
System.out.println(" sorted: "+list);
System.out.println("unsorted: "+unsorted);
}
显而易见的解决方案是创建自己的类来实现java.util.List接口并将 aComparator作为构造函数的参数。您将在正确的位置使用比较器，即该add方法将遍历现有项目并在正确的位置插入新项目。您将不允许调用诸如此类的方法add(int index, Object obj)。
事实上，必须有人已经创建了这个......快速的谷歌搜索显示至少一个例子：
http://www.ltg.ed.ac.uk/NITE/nxt/apidoc/net/sourceforge/nite/util/SortedList.html
在 JavaFX TransformationList 层次结构中，有一个称为 SortedList 的东西。该列表是完全可观察的，因此添加/删除将通知任何其他正在查看该列表的听众。
执行此操作的基本方法是查看另一个 ObservableList 的更改并战略性地使用Collections.binarySearch()，因为其他人建议在 Olog(n) 时间内定位添加或删除的索引。
这里有一个我没有看到的问题，那就是能够跟踪添加的具有相同compareTo签名的项目，即 T1.compareTo(T2) == 0。在这种情况下，排序列表（我将发布我自己的下面的源代码）必须有一个包装元素类型，我将称之为Element。这类似于 JavaFX 中的创建者对SortedList所做的。其原因完全是由于删除操作，如果存在 compareTo 重复，则无法定位原始元素。通常在像 TreeSet 这样的NavigableSet实现中，这些重复项永远不会进入 Set。列表是不同的。
我有一个可观察列表库，可以有效地链接在一起（非常类似于 Java Streams），它可以将结果完全传播到下游，作为链更新中的前一个源。
类层次结构
界面
/**
* Binds the elements of this list to the function application of each element of a
* source observable list.
* <p>
* While a {@code IListContentBinding} is bound, any attempt to modify its contents
* will result in an {@code UnsupportedOperationException}. To unbind the list, call
* {@link #unbind() unbind}.
*
* @param <S> The element type of the input source list that will generate change
* events.
* @param <T> The element type of this output list.
*/
public interface IListContentBinding<S, T> extends ObservableList<T>, ObservableListValue<T>, IContentBinding {... details not shown ....}
所有绑定类型（Sort、Distinct、Map、FlatMap 等）的抽象基类
/**
* Binds the elements of this list to the function application of each element of a
* source observable list.
* <p>
* While a {@code ListContentBinding} is bound, any attempt to modify its contents
* will result in an {@code UnsupportedOperationException}. To unbind the list, call
* {@link #unbind() unbind}.
*
* @param <S> The element type of the source list that will generate change events.
* @param <T> The element type of this binding.
*/
public abstract class ListContentBinding<S, T> extends ObservableListWrapper<T>
implements IListContentBinding<S, T> {.... details not shown ....}
排序绑定类
/**
* A {@code ListContentBinding} implementation that generates sorted elements from a
* source list. The comparator can be set to another {@code Comparator} function at
* any time through the {@link #comparatorProperty() comparator} property.
* <p>
* Unlike the Collections {@link Collections#sort(List) list sort} or Arrays
* {@link Arrays#sort(Object[]) array sort}, once this binding has been added to the
* order of duplicate elements cannot be guaranteed to match the original order of
* the source list. That is the insertion and removal mechanism do not guarantee that
* the original order of duplicates (those items where T1.compareTo(T2) == 0) is
* preserved. However, any removal from the source list is <i>guaranteed</i> to
* remove the exact object from this sorted list. This is because an int <i>ID</i> field
* is added to the wrapped item through the {@link Element} class to ensure that
* matching duplicates can be further compared.
* <p>
* Added/Removed objects from the source list are placed inside this sorted list
* through the {@link Arrays#binarySearch(Object[], Object, Comparator) array binary
* search} algorithm. For any duplicate item in the sorted list, a further check on
* the ID of the {@code Element} corresponding to that item is compared to the
* original, and that item. Each item added to this sorted list increases the
* counter, the maximum number of items that should be placed in this list should be
* no greater than {@code Integer.MAX_VALUE - Integer.MIN_VALUE}, or 4,294,967,295
* total elements. Sizes greater than this value for an instance of this class
* may produce unknown behavior.
* <p>
* Removal and additions to this list binding are proportional to <i>O(logn)</i>
* runtime, where <i>n</i> is the current total number of elements in this sorted
* list.
*
* @param <T> The element type of the source and this list binding.
*/
class ListContentSortBinding<T> extends ListContentBinding<T, T> implements IListContentSortBinding<T> {
/**
* Each location in the source list has a random value associated it with to deal
* with duplicate elements that would return T1.compareTo(T2) == 0.
*/
private Element[] elements = newElementArray(10);
/**
* The same elements from {@link #elements} but placed in their correct sorted
* position according to the {@link #elementComparator element comparator}.
*/
protected Element[] sortedElements = newElementArray(10);
/**
* Create a new instance.
*
* @param source The source observable list. Sorted elements will be generated
* from the source and set as the content of this list binding.
* @param comparator The sorter. An observable that will update the comparator of
* this binding when invalidated. The sorter can be set to another
* {@code Comparator} function at anytime through the
* {@link #comparatorProperty() comparator} property.
* @param options The options of this binding. Considers {@code DependencyOption}
* instances.
* <p>
* All bindings consider {@code BeforeChangeOption} and
* {@code AfterChangeOption}.
*/
@SafeVarargs
ListContentSortBinding(ObservableList<T> source, ObservableObjectValue<Comparator<? super T>> comparator,
BindingOption<T, T>... options) {
this(source, comparator.get(), options);
comparatorProperty().bind(comparator);
}
/**
* Create a new instance.
*
* @param source The source observable list. Sorted elements will be generated
* from the source and set as the content of this list binding.
* @param comparator The sorter. The sorter can be set to another
* {@code Comparator} function at anytime through the
* {@link #comparatorProperty() comparator} property.
* @param options The options of this binding. Considers {@code DependencyOption}
* instances.
* <p>
* All bindings consider {@code BeforeChangeOption} and
* {@code AfterChangeOption}.
*/
@SafeVarargs
ListContentSortBinding(ObservableList<T> source, Comparator<? super T> comparator,
BindingOption<T, T>... options) {
super(new ArrayList<>(), options);
List<Observable> observables = new ArrayList<>(
Arrays.asList(BindingOptionBuilder.extractDependencies(options)));
setComparator(comparator);
observables.add(comparatorProperty());
bind(source, observables.toArray(new Observable[observables.size()]));
}
@Override
protected void sourceChanged(Change<? extends T> change) {
List<? extends T> source = change.getList();
while (change.next()) {
int from = change.getFrom();
if (change.wasPermutated() || change.wasUpdated()) {
List<? extends T> srcMod = source.subList(from, change.getTo());
removed(source, from, srcMod.size());
added(source, from, srcMod);
} else {
List<? extends T> removed = change.getRemoved();
List<? extends T> added = change.getAddedSubList();
if (change.wasReplaced()) {
int min = Math.min(added.size(), removed.size());
replaced(source, from, added.subList(0, min));
added = added.subList(min, added.size());
removed = removed.subList(min, removed.size());
}
if (removed.size() > 0) {
removed(source, from, removed.size());
}
if (added.size() > 0) {
if (source.size() >= elements.length) {
ensureSize(source.size());
}
added(source, from, added);
}
ensureSize(source.size());
}
}
}
/**
* Replace the items in this sorted list binding resulting from a replacement
* operation in the source list. For each of the items added starting at the
* <i>from</i> index in the source list, and items was removed at the same source
* position.
*
* @param source The source list.
* @param from The index of where the replacement started in the source
* (inclusive). The removed and added elements occurred starting at
* the same source position.
* @param added The added source elements from the change.
*/
@SuppressWarnings({})
private void replaced(List<? extends T> source, int from, List<? extends T> added) {
int oldSize = size();
for (int i = 0; i < added.size(); i++) {
int index = from + i;
Element e = elements[index];
// Find the old element and remove it
int pos = findPosition(e, index, oldSize);
System.arraycopy(sortedElements, pos + 1, sortedElements, pos, oldSize - pos - 1);
remove(pos);
T t = added.get(i);
// Create a new element and add it
e = new Element(t);
elements[index] = e;
pos = findPosition(e, index, oldSize - 1);
if (pos < 0) {
pos = ~pos;
}
System.arraycopy(sortedElements, pos, sortedElements, pos + 1, oldSize - pos - 1);
sortedElements[pos] = e;
add(pos, t);
}
}
/**
* Add the elements from the source observable list to this binding.
*
* @param source The source list.
* @param from The index of where the addition started in the source (inclusive).
* @param added The added source elements from the change.
*/
@SuppressWarnings({})
private void added(List<? extends T> source, int from, List<? extends T> added) {
if (size() == 0) {
int size = added.size();
Element[] temp = newElementArray(size);
for (int i = 0; i < added.size(); i++) {
T t = added.get(i);
Element e = new Element(t);
elements[i] = e;
temp[i] = e;
}
if (elementComparator == null) {
addAll(added);
return;
}
Arrays.sort(temp, elementComparator);
System.arraycopy(temp, 0, sortedElements, 0, temp.length);
addAll(Arrays.stream(temp).map(e -> (T) e.t).collect(Collectors.toList()));
return;
}
int size = size();
System.arraycopy(elements, from, elements, from + added.size(), size - from);
for (int i = 0; i < added.size(); i++) {
int index = from + i;
T t = added.get(i);
Element e = new Element(t);
int pos = findPosition(e, index, size);
if (pos < 0) {
pos = ~pos;
}
elements[index] = e;
if (pos < size) {
System.arraycopy(sortedElements, pos, sortedElements, pos + 1, size - pos);
}
sortedElements[pos] = e;
add(pos, t);
size++;
}
}
/**
* Remove the elements from this binding that were removed from the source list.
* Update the {@link #elements} mapping.
*
* @param source The source list.
* @param from The index of where the removal started in the source (inclusive).
* @param removedSize The total number of removed elements from the source list
* for the change.
*/
@SuppressWarnings({})
private void removed(List<? extends T> source, int from, int removedSize) {
if (source.size() == 0) {
elements = newElementArray(10);
sortedElements = newElementArray(10);
elementCounter = Integer.MIN_VALUE;
clear();
return;
}
int oldSize = size();
int size = oldSize;
for (int i = 0; i < removedSize; i++) {
int index = from + i;
Element e = elements[index];
int pos = findPosition(e, index, size);
System.arraycopy(sortedElements, pos + 1, sortedElements, pos, size - pos - 1);
remove(pos);
sortedElements[--size] = null;
}
System.arraycopy(elements, from + removedSize, elements, from, oldSize - from - removedSize);
for (int i = size; i < oldSize; i++) {
elements[i] = null;
}
}
/**
* Locate the position of the element in this sorted binding by performing a
* binary search. A binary search locates the index of the add in Olog(n) time.
*
* @param e The element to insert.
* @param sourceIndex The index of the source list of the modification.
* @param size The size of the array to search, exclusive.
*
* @return The position in this binding that the element should be inserted.
*/
private int findPosition(Element e, int sourceIndex, int size) {
if (size() == 0) {
return 0;
}
int pos;
if (elementComparator != null) {
pos = Arrays.binarySearch(sortedElements, 0, size, e, elementComparator);
} else {
pos = sourceIndex;
}
return pos;
}
/**
* Ensure that the element array is large enough to handle new elements from the
* source list. Also shrinks the size of the array if it has become too large
* with respect to the source list.
*
* @param size The minimum size of the array.
*/
private void ensureSize(int size) {
if (size >= elements.length) {
int newSize = size * 3 / 2 + 1;
Element[] replacement = newElementArray(newSize);
System.arraycopy(elements, 0, replacement, 0, elements.length);
elements = replacement;
replacement = newElementArray(newSize);
System.arraycopy(sortedElements, 0, replacement, 0, sortedElements.length);
sortedElements = replacement;
} else if (size < elements.length / 4) {
int newSize = size * 3 / 2 + 1;
Element[] replacement = newElementArray(newSize);
System.arraycopy(elements, 0, replacement, 0, replacement.length);
elements = replacement;
replacement = newElementArray(newSize);
System.arraycopy(sortedElements, 0, replacement, 0, replacement.length);
sortedElements = replacement;
}
}
/**
* Combines the {@link #comparatorProperty() item comparator} with a secondary
* comparison if the items are equal through the <i>compareTo</i> operation. This
* is used to quickly find the original item when 2 or more items have the same
* comparison.
*/
private Comparator<Element> elementComparator;
/**
* @see #comparatorProperty()
*/
private ObjectProperty<Comparator<? super T>> comparator =
new SimpleObjectProperty<Comparator<? super T>>(this, "comparator") {
@Override
protected void invalidated() {
Comparator<? super T> comp = get();
if (comp != null) {
elementComparator = Comparator.nullsLast((e1, e2) -> {
int c = comp.compare(e1.t, e2.t);
return c == 0 ? Integer.compare(e1.id, e2.id) : c;
});
} else {
elementComparator = null;
}
}
};
@Override
public final ObjectProperty<Comparator<? super T>> comparatorProperty() {
return comparator;
}
@Override
public final Comparator<? super T> getComparator() {
return comparatorProperty().get();
}
@Override
public final void setComparator(Comparator<? super T> comparator) {
comparatorProperty().set(comparator);
}
@Override
protected void onInvalidating(ObservableList<T> source) {
clear();
ensureSize(source.size());
added(source, 0, source);
}
/**
* Counter starts at the Integer min value, and increments each time a new
* element is requested. If this list becomes empty, the counter is restarted at
* the min value.
*/
private int elementCounter = Integer.MIN_VALUE;
/**
* Generate a new array of {@code Element}.
*
* @param size The size of the array.
*
* @return A new array of null Elements.
*/
@SuppressWarnings("unchecked")
private Element[] newElementArray(int size) {
return new ListContentSortBinding.Element[size];
}
包装元素类
/**
* Wrapper class to further aid in comparison of two object types <T>. Since
* sorting in a list allows duplicates we must assure that when a removal occurs
* from the source list feeding this binding that the removed element matches. To
* do this we add an arbitrary <i>int</i> field inside this element class that
* wraps around the original object type <T>.
*/
final class Element {
/** Object */
private final T t;
/** ID helper for T type duplicates */
private int id;
Element(T t) {
this.t = Objects.requireNonNull(t);
this.id = elementCounter++;
}
@Override
public String toString() {
return t.toString() + " (" + id + ")";
}
}
}
JUNIT验证测试
@Test
public void testSortBinding() {
ObservableList<IntWrapper> source = FXCollections.observableArrayList();
int size = 100000;
for (int i = 0; i < size / 2; i++) {
int index = (int) (Math.random() * size / 10);
source.add(new IntWrapper(index));
}
ListContentSortBinding<IntWrapper> binding =
(ListContentSortBinding<IntWrapper>) CollectionBindings.createListBinding(source).sortElements();
Assert.assertEquals("Sizes not equal for sorted binding | Expected: " +
source.size() + ", Actual: " + binding.size(),
source.size(), binding.size());
List<IntWrapper> sourceSorted = new ArrayList<>(source);
Collections.sort(sourceSorted);
for (int i = 0; i < source.size(); i++) {
IntWrapper expected = sourceSorted.get(i);
IntWrapper actual = binding.get(i);
Assert.assertEquals("Elements not equal in expected sorted lists | Expected: " +
expected.value + ", Actual: " + actual.value,
expected.value, actual.value);
}
System.out.println("Sorted Elements Equal: Complete.");
// Randomly add chunks of elements at random locations in the source
int addSize = size / 10000;
for (int i = 0; i < size / 4; i++) {
List<IntWrapper> added = new ArrayList<>();
int toAdd = (int) (Math.random() * addSize);
for (int j = 0; j < toAdd; j++) {
int index = (int) (Math.random() * size / 10);
added.add(new IntWrapper(index));
}
int atIndex = (int) (Math.random() * source.size());
source.addAll(atIndex, added);
}
sourceSorted = new ArrayList<>(source);
Collections.sort(sourceSorted);
for (int i = 0; i < source.size(); i++) {
IntWrapper expected = sourceSorted.get(i);
IntWrapper actual = binding.get(i);
Assert.assertEquals("Elements not equal in expected sorted lists | Expected: " +
expected.value + ", Actual: " + actual.value,
expected.value, actual.value);
}
System.out.println("Sorted Elements Equal - Add Multiple Elements: Complete.");
// Remove one element at a time from the source list and compare
// to the elements that were removed from the sorted binding
// as a result. They should all be identical index for index.
List<IntWrapper> sourceRemoved = new ArrayList<>();
List<IntWrapper> bindingRemoved = new ArrayList<>();
ListChangeListener<IntWrapper> bindingListener = change -> {
while (change.next()) {
if (change.wasRemoved()) {
bindingRemoved.addAll(change.getRemoved());
}
}
};
// Watch the binding for changes after the upstream source changes
binding.addListener(bindingListener);
for (int i = 0; i < size / 4; i++) {
int index = (int) (Math.random() * source.size());
IntWrapper removed = source.remove(index);
sourceRemoved.add(removed);
}
for (int i = 0; i < bindingRemoved.size(); i++) {
IntWrapper expected = bindingRemoved.get(i);
IntWrapper actual = sourceRemoved.get(i);
Assert.assertEquals("Elements not equal in expected sorted lists | Expected: " +
expected + ", Actual: " + actual,
expected.value, actual.value);
Assert.assertEquals("Element refs not equal in expected sorted lists | Expected: " +
expected.value + ", Actual: " + actual.value,
expected.r, actual.r, 0);
}
System.out.println("Sorted Remove Single Element: Complete.");
// Replace random elements from the source list
bindingRemoved.clear();
sourceRemoved.clear();
int removeSize = size / 10000;
for (int i = 0; i < size / 1000; i++) {
int replaceIndex = (int) (Math.random() * source.size());
int index = (int) (Math.random() * size / 10);
IntWrapper replace = new IntWrapper(index);
source.set(replaceIndex, replace);
}
sourceSorted = new ArrayList<>(source);
Collections.sort(sourceSorted);
for (int i = 0; i < source.size(); i++) {
IntWrapper expected = sourceSorted.get(i);
IntWrapper actual = binding.get(i);
Assert.assertEquals("Elements not equal in expected sorted lists | Expected: " +
expected.value + ", Actual: " + actual.value,
expected.value, actual.value);
}
System.out.println("Sorted Elements Replace: Complete.");
// Remove random chunks from the source list
bindingRemoved.clear();
sourceRemoved.clear();
Set<IntWrapper> sourceRemovedSet =
Collections.newSetFromMap(new IdentityHashMap<>()); // set for speed
while (source.size() > 0) {
int index = (int) (Math.random() * source.size());
int toRemove = (int) (Math.random() * removeSize);
toRemove = Math.min(toRemove, source.size() - index);
List<IntWrapper> removed = source.subList(index, index + toRemove);
sourceRemovedSet.addAll(new ArrayList<>(removed));
removed.clear(); // triggers list change update to binding
}
Assert.assertEquals(bindingRemoved.size(), sourceRemovedSet.size());
// The binding removed will not necessarily be placed in the same order
// since the change listener on the binding will make sure that the final
// order of the change from the binding is in the same order as the binding
// element sequence. We therefore must do a contains() to test.
for (int i = 0; i < bindingRemoved.size(); i++) {
IntWrapper expected = bindingRemoved.get(i);
Assert.assertTrue("Binding Removed Did Not Contain Source Removed",
sourceRemovedSet.contains(expected));
}
System.out.println("Sorted Removed Multiple Elements: Complete.");
}
JUNIT 基准测试
@Test
public void sortBindingBenchmark() {
ObservableList<IntWrapper> source = FXCollections.observableArrayList();
ObservableList<IntWrapper> binding =
(ListContentSortBinding<IntWrapper>) CollectionBindings.createListBinding(source).sortElements();
int size = 200000;
Set<IntWrapper> toAdd = new TreeSet<>();
while (toAdd.size() < size) {
int index = (int) (Math.random() * size * 20);
toAdd.add(new IntWrapper(index));
}
// Randomize the order
toAdd = new HashSet<>(toAdd);
System.out.println("Sorted Binding Benchmark Setup: Complete.");
long time = System.currentTimeMillis();
for (IntWrapper w : toAdd) {
source.add(w);
}
long bindingTime = System.currentTimeMillis() - time;
System.out.println("Sorted Binding Time: Complete.");
source.clear(); // clear the list and re-add
ObservableList<IntWrapper> sortedList = new SortedList<>(source);
time = System.currentTimeMillis();
for (IntWrapper w : toAdd) {
source.add(w);
}
long sortedListTime = System.currentTimeMillis() - time;
System.out.println("JavaFX Sorted List Time: Complete.");
// Make the test "fair" by adding a listener to an observable
// set that populates the sorted set
ObservableSet<IntWrapper> obsSet = FXCollections.observableSet(new HashSet<>());
Set<IntWrapper> sortedSet = new TreeSet<>();
obsSet.addListener((SetChangeListener<IntWrapper>) change -> {
sortedSet.add(change.getElementAdded());
});
time = System.currentTimeMillis();
for (IntWrapper w : toAdd) {
obsSet.add(w);
}
long setTime = System.currentTimeMillis() - time;
System.out.println("Sorted Binding Benchmark Time: Complete");
Assert.assertEquals(sortedSet.size(), binding.size());
System.out.println("Binding: " + bindingTime + " ms, " +
"JavaFX Sorted List: " + sortedListTime + " ms, " +
"TreeSet: " + setTime + " ms");
}
仅用于测试的包装类
/**
* Wrapper class for testing sort bindings. Verifies that duplicates were sorted
* and removed correctly based on the object instance.
*/
private static class IntWrapper implements Comparable<IntWrapper> {
static int counter = Integer.MIN_VALUE;
final int value;
final int id;
IntWrapper(int value) {
this.value = value;
this.id = counter++;
}
我还发现 Java 标准库中不存在这令人难以置信。（但祝你好运，提议向 JDK 团队添加任何新类！我从来没有运气。）
假设您的compareTo函数是适当的传递关系，那么最快的算法（假设列表被读取的次数大约与写入的次数相同）是List.add使用执行二进制搜索以找到新的插入点的方法覆盖插入之前的项目。这是添加元素数量的 O(log(N))。
The best way to do this would be to override the add implementation of a list. I'm going to use a LinkedList to demonstrate it, as it allows for efficient insertion.
public boolean add(Integer e)
{
int i = 0;
for (Iterator<Integer> it = this.iterator(); it.hasNext();)
{
int current = it.next();
if(current > e)
{
super.add(i, e);
return true;
}
i++;
}
return super.add(e);
}
The above code creates a sorted list of integers, that is always sorted. It can easily be modified to work with any other datatype. However here you will have to avoid using the add(index, value) function, as that would obviously break the sorting.
Although people above suggested using Arrays.sort(), I would avoid that, as it can be a significantly less efficient approach, especially since the sort method must be called with every addition to the list.
ListIterator 接口的约定使它有点麻烦，但是此方法将使用列表的单次扫描（直到插入点）来执行插入：
private void add(Integer value) {
ListIterator<Integer> listIterator = list.listIterator();
Integer next = null;
while (listIterator.hasNext()) {
next = listIterator.next();
if (next.compareTo(value) > 0) {
break;
}
}
if (next == null || next.compareTo(value) < 0) {
listIterator.add(value);
} else {
listIterator.set(value);
listIterator.add(next);
}
}
SortedSet接口的任何实现都SortedSet带有您想要的行为。
默认情况下，添加的对象按其自然顺序排序，即基于它们对Comparable::compareTo接口方法的实现。
或者，您可以传递一个Comparator实现来确定排序。
TreeSetTreeSet是一种常用的植入物SortedSet。你也可以找其他人。
Lista和 a之间的主要区别在于SortedSet重复，即比较相等的对象。AList允许重复，而 aSortedSet与 any 一样Set，不允许重复。
另一个区别是 aSet不能通过索引访问。您无法通过对象在集合中的位置编号来定位对象。
如果您在构建后需要这样的访问权限SortedSet，请创建一个List. 有多种方法可以做到这一点，例如SortedSet将ArrayList. List从 Java 10 开始，最近的一种方法是通过将 to 传递SortedSet给umodifiable List.copyOf。
我相信优先队列会完成这项工作。
警告（来自同一个文档页面）：
此类及其迭代器实现了和 Iterator 接口的所有可选方法 。
Collection提供的Iteratorin 方法iterator()不能保证以任何特定顺序遍历优先级队列的元素。如果您需要有序遍历，请考虑使用Arrays.sort(pq.toArray()).