维护订购的列表实现

Java中是否存在现有的List实现，它基于提供的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）我意识到，这种列表的实施将有不足的表现。有两种常用的方法：

使用联结构（在某种程度上）B树或类似
使用阵列和插入（二进制搜索）

否1.有CPU高速缓存未命中问题否2.移位阵列中的元素存在问题。

UPDATE2： TreeSet不起作用，因为它使用所提供的比较器（MyComparator）来检查平等和基于它假定元素都是平等的，排除它们。我需要一个比较只限于购买，而不是“唯一性”过滤（因为通过其自然顺序的元素是不相等的）

UPDATE3： PriorityQueue不作为List工作（我需要），因为没有办法按照它“排序”的顺序遍历它，为了获得排序顺序的元素，你必须将它们从集合中删除。

UPDATE：

类似的问题：
A good Sorted List for Java
Sorted array list in Java

来源

2012-05-20 Op De Cirkel

这种行为会违反'List'合同，通常是一个坏主意。（番石榴已考虑并拒绝这些功能。） –

“List”合同的哪个部分会被违反？ –

'add（E）'的规范说：“将指定的元素追加到此列表的末尾。”将它添加到列表中的任何其他位置都违反了合同。 –

对新要求的回应。我看到两个电位：

做什么PriorityQueue的JavaDoc说：

此类及其迭代器实现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，poll,remove()和add）; 线性时间为remove(Object)和contains(Object)方法;和常数检索方法的时间（peek,element和size）。

你也应该知道，通过PriorityQueue产生的迭代器行为并不如想象：

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

我刚刚注意到Guava提供了一个MinMaxPriorityQueue。此实现是数组支持的，而不是JDK的PriorityQueue中提供的链接表单，因此可能具有不同的计时行为。如果你对性能敏感，你可以考虑一下。虽然笔记给出了略微不同的（线性和对数）大O时间，但所有这些时间也应该是有界的，这可能是有用的。

本身没有List实现维护排序，但您可能要查找的是SortedSet的实现。 A TreeSet是最常见的。另一个实现，ConcurrentSkipListSet用于更具体的用途。请注意，SortedSet提供了排序，但不允许重复输入，与List一样。

参考文献：

博客文章PriorityQueue iterator is not ordered
上PQ ordered iterator

来源

2012-05-20 17:09:58 andersoj

虽然，这并没有解决我的问题。它很好地解释了情况和可能的选择。 –

根据[Guava文档]（http://guava-libraries.googlecode.com/svn/tags/release02/javadoc/com/google/common/collect/TreeMultiset.html），不能保证'TreeMultiList'来处理'compareTo（）'与equals不一致的用例，就像OP的帖子一样。该文档说：“警告：比较必须与”Comparable“类规范说明的equals相一致，否则，由此产生的multiset将违反”Collection“合同，它是根据Object.equals（java .lang.Object）'。” – Kevin

你或许应该使用一个TreeSet：

的元素使用其自然顺序进行排序，或者通过一个比较在集创建时提供，具体取决于使用哪个构造函数。

例子：

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

注意，这是一个设置，所以没有重复的条目是允许的。这可能会或可能不适用于您的特定用例。

来源

2012-05-20 17:09:20 beerbajay

注意，虽然'List'和'Set'之间有很大的区别：一个允许重复的元素，一个不允许。 – Voo

好点;我已经更新了答案，以确保清楚。 – beerbajay

现在，我可以给良心良好的+1 :) – Voo

-1

SO怀疑我有一个类似的问题，我想用一个TreeSet的。为避免排除“相等”元素，我将修改比较器，使其不返回0，而是返回（-1,1）之间的随机数或它将始终返回1.

如果您无法控制比较器或如果您将其用于与插入此解决方案不同的其他内容，则不适用于您。

来源

2014-02-26 08:29:05 Joan

维护订购的列表实现

回答

相关问题