我知道由于各种概念上的原因，Java 没有排序列表，但考虑到我需要一个类似于优先级队列但也允许我随机访问（可索引）的集合的情况，换句话说，我需要一个遵循特定顺序的列表。我宁愿不使用Collections.sort()
优选的操作约束：
检索 - O(1)（基于索引的随机访问）
搜索 - O(log n)
插入 - O(log n)
删除 - O(log n)
集合上的迭代器应该给我排序顺序中的所有元素（基于在Comparator数据结构实例化期间提供的预定义）
我更喜欢使用 Java 的内置库来实现这一点，但也可以随意建议外部库。
编辑： TreeSet 不会做，因为基于索引的访问很困难，使用包装器集合也不是我的最佳选择，因为删除意味着我需要从两个集合中删除。
EDIT2：我找不到indexable skip list这似乎有点相关的实现和/或文档，有人可以帮我找到它吗？也欢迎对所提出的数据结构提出任何意见或反对意见。
EDIT3：虽然这可能不是最完美的答案，但我想添加我编写的这段代码，以便任何有类似问题需要排序列表的人都可以在发现它有用时使用它。
检查错误（如果有的话），并提出改进建议（尤其是sortedSubList方法）
import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
public class SortedList<E> extends ArrayList<E> {
private final Comparator<? super E> comparator;
public SortedList(Comparator<? super E> comparator) {
this.comparator = comparator;
}
public SortedList(int initialCapacity, Comparator<? super E> comparator) {
super(initialCapacity);
this.comparator = comparator;
}
@Override
public boolean add(E e) {
if (comparator == null)
return super.add(e);
if (e == null)
throw new NullPointerException();
int start = 0;
int end = size() - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (comparator.compare(get(mid), e) == 0) {
super.add(mid, e);
return true;
}
if (comparator.compare(get(mid), e) < 0) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
super.add(start, e);
return true;
}
@Override
public boolean contains(Object o) {
if (comparator == null)
return super.contains(o);
if (o == null)
return false;
E other = (E) o;
int start = 0;
int end = size() - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (comparator.compare(get(mid), other) == 0) {
return true;
}
if (comparator.compare(get(mid), other) < 0) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
return false;
}
@Override
public int indexOf(Object o) {
if (comparator == null)
return super.indexOf(o);
if (o == null)
throw new NullPointerException();
E other = (E) o;
int start = 0;
int end = size() - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (comparator.compare(get(mid), other) == 0) {
return mid;
}
if (comparator.compare(get(mid), other) < 0) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
return -(start+1);
}
@Override
public void add(int index, E e) {
throw new UnsupportedOperationException();
}
@Override
public boolean addAll(int index, Collection<? extends E> c) {
throw new UnsupportedOperationException();
}
@Override
public E set(int index, E e) {
throw new UnsupportedOperationException();
}
public SortedList<E> sortedSubList(int fromIndex, int toIndex) {
SortedList<E> sl = new SortedList<>(comparator);
for (int i = fromIndex; i < toIndex; i++)
sl.add(get(i));
return sl;
}
}