Java中的排序集合

我是Java的初学者.请建议可以/应该使用哪些集合来维护Java中的排序列表.我曾尝试Map和Set,但他们不是我所期待的.

1> Martin Probs..：

---

这来得很晚,但JDK中有一个类只是为了有一个排序列表.它被命名(与其他Sorted*接口有点不正常)" java.util.PriorityQueue".它可以对Comparables进行排序或使用a Comparator.

与使用List排序的差异Collections.sort(...)在于,这将通过使用堆数据结构始终保持部分顺序,具有O(log(n))插入性能,而在排序中插入ArrayList将是O(n)(即,使用二进制搜索和移动).

但是,与a不同List,PriorityQueue不支持索引访问(get(5)),访问堆中项目的唯一方法是将它们一次一个地取出(因此名称PriorityQueue).

---

来自Javadoc:"方法迭代器()中提供的迭代器不保证以任何特定顺序遍历PriorityQueue的元素."

---

@giraff:优先级队列就是这样一种数据结构,它在保持优先级队列方面非常有效.您可以从前面轮询并按排序顺序获取数据项.但是,堆内部不保持元素的总顺序(这就是它们如此高效的原因),因此无法在不执行轮询操作的情况下按顺序访问元素.

---

因为它指出了唯一具有JDK功能的Collection,所以这个答案值得更多的赞成

---

@MartinProbst请纠正您的答案,清楚地表明该集合不能按预期顺序进行迭代.正如许多人所说,这极具误导性!

---

但与List不同,没有随机访问,对吧？

---

@chrispy它取决于你想要用你的数据结构实现什么.堆是一种有效的方式来维护项目列表并在以后以有序的方式检索它们 - 使用迭代器不起作用,但如果您从它进行轮询,您将按顺序获取数据.检索是破坏性的,但在许多情况下仍然可以.所以我觉得这个答案很好.

2> Michael Borg..：

---

TreeMap和TreeSet将按排序顺序对内容进行迭代.或者您可以使用ArrayList并使用Collections.sort()对其进行排序.所有这些类都在java.util中

---

这有两个主要的缺点,第一个是Set不能有重复.第二个是如果你使用一个列表和Collections.sort(),你往往会不断地排序大量的列表并且性能很差.当然你可以使用"脏"标志,但它并不完全相同.

3> Neil Coffey..：

---

如果你想维护一个你经常修改的排序列表(即除了排序之外,还允许重复并且索引可以有效引用其元素的结构),那么使用ArrayList但是当你需要插入一个元素时,始终使用Collections.binarySearch()来确定添加给定元素的索引.后一种方法告诉您需要插入的索引,以使列表按排序顺序排列.

---

n个插入将是O(n ^ 2).TreeSet将为您提供更清晰的代码和O(n log n).OTOH,对于不经常*修改的数组二进制搜索将更快并且使用更少的内存(因此更少的GC开销).

4> jtb..：

---

使用Google Guava的TreeMultiset类.番石榴有一个壮观的收藏API.

提供维护排序顺序的List实现的一个问题是在add()方法的JavaDocs中做出的承诺.

---

+1提及"List"总是在末尾添加的要求.

---

请注意,TreeMultiSet仍然不允许重复元素(compareTo()返回0的元素,而不是equals()check).如果你倾向于添加多个具有相同优先级的项目,它只会增加第一个添加的项目的数量,丢弃其他项目并有效地成为一个好的Counting Bag实现.

5> cletus..：

---

您需要SortedSet实现,即TreeSet.

---

不必要; 集合不能有重复的值.这取决于OP的要求.

6> BenM..：

---

有几个选择.如果你不想重复,我建议使用TreeSet,你插入的对象是可比较的.

您还可以使用Collections类的静态方法执行此操作.

有关详细信息,请参阅集合#sort(java.util.List)和TreeSet.

7> Guillaume..：

---

如果您只想对列表进行排序,请使用任何类型的List并使用Collections.sort().如果要确保列表中的元素是唯一的并且始终排序,请使用SortedSet.

8> Carlos Verde..：

---

我所做的是实现具有委托所有方法的内部实例的List.

 public class ContactList implements List, Serializable {
    private static final long serialVersionUID = -1862666454644475565L;
    private final List list;

public ContactList() {
    super();
    this.list = new ArrayList();
}

public ContactList(List list) {
    super();
    //copy and order list
    Listaux= new ArrayList(list);
    Collections.sort(aux);

    this.list = aux;
}

public void clear() {
    list.clear();
}

public boolean contains(Object object) {
    return list.contains(object);
}

之后,我实现了一个新的方法"putOrdered",如果元素不存在则插入到正确的位置,或者只在它存在的情况下替换.

public void putOrdered(Contact contact) {
    int index=Collections.binarySearch(this.list,contact);
    if(index<0){
        index= -(index+1);
        list.add(index, contact);
    }else{
        list.set(index, contact);
    }
}

如果要允许重复元素,只需实现addOrdered(或两者).

public void addOrdered(Contact contact) {
    int index=Collections.binarySearch(this.list,contact);
    if(index<0){
        index= -(index+1);
    }
    list.add(index, contact);
}

如果要避免插入,还可以在"add"和"set"方法上抛出和不支持的操作异常.

public boolean add(Contact object) {
    throw new UnsupportedOperationException("Use putOrdered instead");
}

...而且你必须小心ListIterator方法,因为他们可以修改你的内部列表.在这种情况下,您可以返回内部列表的副本或再次抛出异常.

public ListIterator listIterator() {
    return (new ArrayList(list)).listIterator();
}

9> vladich..：

---

实现所需排序列表的最有效方法是实现可索引的跳转列表，如下所示：Wikipedia：Indexable skiplist。这将允许在O（log（n））中进行插入/删除操作，并允许同时进行索引访问。而且它也允许重复。

跳过列表非常有趣，我想说的是低估的数据结构。不幸的是，Java基库中没有索引的跳过列表实现，但是您可以使用一种开源实现，也可以自己实现。有常规的Skiplist实现，例如ConcurrentSkipListSet和ConcurrentSkipListMap