Java：SortedMap、TreeMap、Comparable？如何使用？

Java: SortedMap, TreeMap, Comparable? How to use?

提问by Nick Heiner

I have a list of objects I need to sort according to properties of one of their fields. I've heard that SortedMap and Comparators are the best way to do this.

我有一个对象列表，我需要根据其中一个字段的属性进行排序。我听说 SortedMap 和 Comparator 是最好的方法。

1. Do I implement Comparable with the class I'm sorting, or do I create a new class?
2. How do I instantiate the SortedMap and pass in the Comparator?
3. How does the sorting work? Will it automatically sort everything as new objects are inserted?

1. 我是对我正在排序的类实现 Comparable 还是创建一个新类？
2. 如何实例化 SortedMap 并传入 Comparator？
3. 排序是如何工作的？它会在插入新对象时自动对所有内容进行排序吗？

EDIT:This code is giving me an error:

编辑：这段代码给了我一个错误：

private TreeMap<Ktr> collection = new TreeMap<Ktr>();

(Ktr implements Comparator<Ktr>). Eclipse says it is expecting something like TreeMap<K, V>, so the number of parameters I'm supplying is incorrect.

（Ktr 实现Comparator<Ktr>）。Eclipse 说它期待类似的东西TreeMap<K, V>，所以我提供的参数数量不正确。

采纳答案by Michael Myers

1. The simpler way is to implement Comparablewith your existing objects, although you could instead create a Comparatorand pass it to the SortedMap.
   Note that Comparableand Comparatorare two different things; a class implementing Comparablecompares thisto another object, while a class implementing Comparatorcompares two otherobjects.
2. If you implement Comparable, you don't need to pass anything special into the constructor. Just call new TreeMap<MyObject>(). (Edit:Except that of course Mapsneed two generic parameters, not one. Silly me!)
   If you instead create another class implementing Comparator, pass an instance of that class into the constructor.
3. Yes, according to the TreeMapJavadocs.

1. 更简单的方法是Comparable使用您现有的对象来实现，尽管您可以改为创建 aComparator并将其传递给SortedMap.
   请注意，Comparable和Comparator是两个不同的东西；一个实现类与另一个对象Comparable进行比较this，而一个类实现Comparator比较两个其他对象。
2. 如果您实现Comparable，则不需要将任何特殊内容传递给构造函数。就打电话new TreeMap<MyObject>()。（编辑：除了当然Maps需要两个泛型参数，而不是一个。我太傻了！）
   如果您改为创建另一个实现 的类Comparator，则将该类的一个实例传递给构造函数。
3. 是的，根据TreeMapJavadocs。

---

---

Edit:On re-reading the question, none of this makes sense. If you already have a list, the sensible thing to do is implement Comparableand then call Collections.sorton it. No maps are necessary.

编辑：在重新阅读问题时，这些都没有意义。如果你已经有了一个清单，明智的做法是实施Comparable然后调用Collections.sort它。不需要地图。

A little code:

一点代码：

public class MyObject implements Comparable<MyObject> {
    // ... your existing code here ...
    @Override
    public int compareTo(MyObject other) {
        // do smart things here
    }
}

// Elsewhere:
List<MyObject> list = ...;
Collections.sort(list);

As with the SortedMap, you could instead create a Comparator<MyObject>and pass it to Collections.sort(List, Comparator).

与 一样SortedMap，您可以改为创建 aComparator<MyObject>并将其传递给Collections.sort(List, Comparator)。

回答by Adamski

My answer assumes you are using the TreeMapimplementation of SortedMap.

我的回答假设你正在使用TreeMap的实现SortedMap。

1.) If using TreeMap, you have a choice. You can either implement Comparabledirectly on your class or pass a separate Comparatorto the constructor.

1.) 如果使用TreeMap，您有一个选择。您可以Comparable直接在您的类上实现，也可以将单独的参数传递Comparator给构造函数。

2.) Example:

2.) 示例：

Comparator<A> cmp = new MyComparator();
Map<A,B> map = new TreeMap<A,B>(myComparator);

3.) Yes that's correct. Internally TreeMapuses a red-black tree to store elements in order as they are inserted; the time cost of performing an insert (or retrieval) is O(log N).

3.) 是的，这是正确的。TreeMap内部使用红黑树来按插入顺序存储元素；执行插入（或检索）的时间成本是 O(log N)。

回答by jprete

You make a Comparator<ClassYouWantToSort>. Then the Comparator compares the field that you want to sort on.

你做一个Comparator<ClassYouWantToSort>. 然后比较器比较您要排序的字段。

When you create the TreeMap, you create a TreeMap<ClassYouWantToSort>, and you pass in the Comparatoras an argument. Then, as you insert objects of type ClassYouWantToSort, the TreeMapuses your Comparatorto sort them properly.

当您创建 时TreeMap，您将创建一个TreeMap<ClassYouWantToSort>，并将Comparator作为参数传入。然后，当您插入类型为 的对象时ClassYouWantToSort，它会TreeMap使用您Comparator对它们进行正确排序。

EDIT: As Adamski notes, you can also make ClassYouWantToSortitself Comparable. The advantage is that you have fewer classes to deal with, the code is simpler, and ClassYouWantToSortgets a convenient default ordering. The disadvantage is that ClassYouWantToSortmay not have a single obvious ordering, and so you'll have to implement Comparablesfor other situations anyway. You also may not be able to change ClassYouWantToSort.

编辑：正如 Adamski 所指出的，你也可以 makeClassYouWantToSort自己Comparable。优点是你需要处理的类更少，代码更简单，并ClassYouWantToSort获得方便的默认排序。缺点是ClassYouWantToSort可能没有一个明显的顺序，因此Comparables无论如何您都必须针对其他情况实施。你也可能无法改变ClassYouWantToSort。

EDIT2: If you only have a bunch of objects that you're throwing into the collection, and it's not a Map(i.e. it's not a mapping from one set of objects to another) then you want a TreeSet, not a TreeMap.

EDIT2：如果您只有一堆要放入集合中的对象，并且它不是 a Map（即它不是从一组对象到另一组对象的映射），那么您需要的是TreeSet，而不是TreeMap。

回答by sepp2k

1.

1.

That depends on the situation. Let's say the object A should sort before the object B in your set. If it generally makes sense to consider A less than B, then implementing Comparable would make sense. If the order only makes sense in the context in which you use the set, then you should probably create a Comparator.

那要看情况了。假设对象 A 应该在集合中的对象 B 之前排序。如果通常认为 A 小于 B 是有意义的，那么实现 Comparable 就会有意义。如果顺序仅在您使用集合的上下文中有意义，那么您可能应该创建一个比较器。

2.

2.

new TreeMap(new MyComparator());

Or without creating a MyComparator class:

或者不创建 MyComparator 类：

new TreeMap(new Comparator<MyClass>() {
    int compare(MyClass o1, MyClass o2) { ... }
});

3. Yes.

3. 是的。

回答by starblue

Since you have a list and get an error because you have one argument on the map I suppose you want a sorted set:

由于您有一个列表并得到一个错误，因为您在地图上有一个参数，我想您想要一个排序集：

SortedSet<Ktr> set = new TreeSet<Ktr>(comparator);

This will keep the set sorted, i.e. an iterator will return the elements in their sort order. There are also methods specific to SortedSetwhich you might want to use. If you also want to go backwards you can use NavigableSet.

这将使集合保持排序，即迭代器将按元素的排序顺序返回元素。还有一些您可能想要使用的特定于SortedSet 的方法。如果您还想倒退，可以使用NavigableSet。