Java: SortedMap, TreeMap, сопоставимый? Как пользоваться? - PullRequest
Новая
       38

Java: SortedMap, TreeMap, сопоставимый? Как пользоваться?

5 голосов
/ 17 сентября 2009

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

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

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

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

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

Ответы [ 5 ]

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

Редактировать: Перечитывая вопрос, ничего из этого не имеет смысла. Если у вас уже есть список, разумно выполнить 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).

2 голосов
/ 17 сентября 2009

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. Да.

1 голос
/ 17 сентября 2009

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

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

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

0 голосов
/ 17 сентября 2009

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

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

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

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

0 голосов
/ 17 сентября 2009

В моем ответе предполагается, что вы используете 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).

...