Java: SortedMap, TreeMap, Comparable? Как использовать?

Question

У меня есть список объектов, которые мне нужно сортировать в соответствии с свойствами одного из их полей. Я слышал, что SortedMap и Comparators - лучший способ сделать это.

1. Я могу выполнить сравнение с классом, который я сортирую, или создать новый класс?
2. Как создать экземпляр SortedMap и передать в Comparator?
3. Как работает сортировка? Будет ли он автоматически сортировать все по мере добавления новых объектов?

EDIT: Этот код дает мне ошибку:

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

(КТР реализует Comparator<Ktr>). Eclipse говорит, что он ожидает что-то вроде TreeMap<K, V>, поэтому количество параметров, которые я поставляю, неверно.

Answer 1

1. Чем проще способ реализовать Comparable с существующими объектами, хотя вы могли бы вместо того, чтобы создать Comparator и передать его на SortedMap.
   Отметьте, что Comparable и Comparator - это две разные вещи; класс, реализующий Comparable, сравнивает this с другим объектом, а класс, реализующий Comparator, сравнивает два других объектов.
2. Если вы реализуете Comparable, вам не нужно передавать ничего особенного в конструктор. Просто позвоните new TreeMap<MyObject>(). (Редактировать: За исключением того, что, конечно, Maps нужны два общих параметра, а не один. Глупо меня!)
   Если вы вместо этого создадите другой класс, реализующий Comparator, передайте экземпляр этого класса в конструктор.
3. Да, согласно TreeMap Javadocs.

---

Edit: На перечитывая этот вопрос, никто из этого не имеет смысла. Если у вас уже есть список, разумная вещь - реализовать Comparable, а затем позвонить Collections.sort. Карты не нужны.

Небольшой код:

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); 

Как с SortedMap, вы могли бы вместо того, чтобы создать Comparator<MyObject> и передать его в Collections.sort(List, Comparator).

Answer 2

Мой ответ предполагает, что вы используете TreeMap исполнение SortedMap.

1.) При использовании TreeMap у вас есть выбор. Вы можете либо реализовать Comparable непосредственно на свой класс, либо передать отдельный конструктор конструктору Comparator.

2.) Пример:

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

3.) Да, это правильно. Внутренне TreeMap использует красно-черное дерево для хранения элементов по мере их вставки; временная стоимость выполнения вставки (или извлечения) равна O (log N).

Answer 3

Вы делаете Comparator<ClassYouWantToSort>. Затем компаратор сравнивает поле, которое вы хотите сортировать.

При создании TreeMap вы создаете TreeMap<ClassYouWantToSort>, и вы передаете в Comparator в качестве аргумента. Затем, когда вы вставляете объекты типа ClassYouWantToSort, TreeMap использует ваш Comparator, чтобы отсортировать их надлежащим образом.

EDIT: Как отмечает Адамски, вы также можете сделать ClassYouWantToSortComparable. Преимущество состоит в том, что у вас меньше классов для работы, код проще, и ClassYouWantToSort получает удобный заказ по умолчанию. Недостаток заключается в том, что ClassYouWantToSort может не иметь единого очевидного заказа, поэтому вам придется реализовать Comparables для других ситуаций. Возможно, вы не сможете изменить ClassYouWantToSort.

EDIT2: Если у вас есть только куча предметов, которые вы бросали в коллекции, и это не Map (т.е. это не отображение из одного набора объектов к другому), то вы хотите TreeSet, не TreeMap.

Answer 4

1.

Это зависит от ситуации. Предположим, что объект A должен сортировать перед объектом B в вашем наборе. Если вообще имеет смысл рассматривать A меньше B, то реализация Comparable имеет смысл. Если порядок имеет смысл только в том контексте, в котором вы используете набор, то вам, вероятно, следует создать Comparator.

2.

new TreeMap(new MyComparator()); 

Или без создания класса MyComparator:

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

3. Да.

Answer 5

Поскольку у вас есть список и получить ошибку, потому что у вас есть один аргумент на карте, я полагаю, вы хотите отсортированный набор:

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

Это будет держать набор отсортированного, т.е. итератор будет возвращать элементы в порядке их сортировки. Существуют также методы, специфичные для SortedSet, которые вы, возможно, захотите использовать. Если вы также хотите вернуться назад, вы можете использовать NavigableSet.