列出维护排序的实现

Question

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. 使用链接结构(种类)B树或类似物
2. 使用数组和插入(使用二进制搜索)

没有1. CPU缓存未命中问题No 2.在数组中移位元素有问题.

UPDATE2: TreeSet不起作用,因为它使用提供的比较器(MyComparator)来检查是否相等,并基于它假设元素相等并排除它们.我需要那个比较器只用于排序,而不是"唯一性"过滤(因为元素按其自然顺序不相等)

UPDATE3: PriorityQueue不能正常工作List(因为我需要),因为没有办法按照"排序"的顺序遍历它,要按排序顺序获取元素,你必须从集合中删除它们.

更新:

类似的问题:
Java中Java 排序数组列表的良好排序列表

Answer 1

您可能应该使用TreeSet:

元素按照其自然顺序排序,或者在创建时创建时提供的比较器,具体取决于使用的构造函数.

例:

Comparator<T> cmp = new MyComparator<T>();
TreeSet<T> t = new TreeSet<T>(cmp);
l.add(someT);

请注意,这是一个集合,因此不允许重复的条目.这可能适用于您的特定用例,也可能不适用.

Answer 2

对新要求的回应.我看到两个潜力:

• 做JavaDoc PriorityQueue所说的:

  该类及其迭代器实现了Collection和Iterator接口的所有可选方法.方法中提供的迭代器iterator()不保证以任何特定顺序遍历优先级队列的元素.如果您需要有序遍历,请考虑使用Arrays.sort(pq.toArray()).

  我怀疑根据您的要求,这将产生最佳性能.如果这是不可接受的,你需要更好地解释你想要完成的事情.

• 构建一个列表,只需添加新元素即可自行排序.这是一个真正的痛苦...如果您使用链接结构,您可以进行有效的插入排序,但局部性很差.如果您使用了数组支持的结构,插入排序很痛苦,但遍历更好.如果迭代/遍历不常见,您可以保持列表内容未排序并仅按需排序.

• 考虑使用我建议的PriorityQueue,如果你需要按顺序迭代,编写一个包装器迭代器:

  class PqIter implements Iterator<T>
  {
     final PriorityQueue<T> pq;
     public PqIter(PriorityQueue <T> source)
     {
       pq = new PriorityQueue(source); 
     }
  
     @Override
     public boolean hasNext()
     {
       return pq.peek() != null
     }
  
     @Override
     public T next()
     { return pq.poll(); }
  
     @Override
     public void remove()
     { throw new UnsupportedOperationException(""); }
  }
  

• 使用番石榴TreeMultiSet.我测试了以下代码,Integer似乎做了正确的事情.

  import com.google.common.collect.TreeMultiset;
  
  public class TreeMultiSetTest { 
    public static void main(String[] args) {
      TreeMultiset<Integer> ts = TreeMultiset.create();
      ts.add(1);  ts.add(0); ts.add(2);
      ts.add(-1); ts.add(5); ts.add(2);
  
      for (Integer i : ts) {
        System.out.println(i);
      } 
    } 
  }
  

下面解决了使用时遇到的唯一性/过滤问题SortedSet.我看到你也想要一个迭代器,所以这不行.

如果你真正想要的是一个有序列表的东西,你可以使用一个PriorityQueue.

Comparator<T> cmp = new MyComparator<T>();
PriorityQueue<T> pq = new PriorityQueue<T>(cmp);
pq.add(someT);

请注意API文档中有关各种操作的时间属性的内容:

实现注意事项:此实现提供了O(日志(n))的时间和入队方法dequeing( ,,offer 和); 和方法的线性时间; 和恒定时间检索方法(,,和).pollremove()addremove(Object)contains(Object)peekelementsize

您还应该知道生成的迭代器PriorityQueue不会像预期的那样表现:

的Iterator提供在方法iterator()不能保证遍历优先级队列中的元素的任何特定顺序.如果您需要有序遍历,请考虑使用Arrays.sort(pq.toArray()).

我刚注意到Guava提供了一个MinMaxPriorityQueue.此实现是由数组支持的,而不是JDK中提供的链接表单PriorityQueue,因此可能具有不同的计时行为.如果你正在做一些表现敏感的事情,你可能希望看一看.虽然音符给出了稍微不同(线性和对数)的大O次,但所有这些时间也应该是有界的,这可能是有用的.

没有一个List实现本身维护排序,但你可能正在寻找的是实现SortedSet.A TreeSet是最常见的.另一个实现,a ConcurrentSkipListSet用于更具体的用途.请注意,a SortedSet提供排序,但不允许重复输入,如a List.

参考文献:

• 博客帖子PriorityQueue迭代器没有订购
• 关于PQ订购迭代器的问题