универсальное программирование, общие структуры данных

Я пытаюсь реализовать двоичное дерево поиска, и если я использую общее программирование в java, то это дерево должно иметь возможность хранить любые данные, например. int, Strings или любой другой объект. Но проблема с таким классом заключается в кодировании функций, например. если я кодирую функцию addToTree, то оператор «‹» можно использовать для сравнения int, и он успешно вставит int в дерево, но не будет вставлять строки или другие объекты, потому что сравнение строк и других объектов с использованием оператора «‹» может не допускать.

Эта проблема одинакова и для других структур данных.


java generic-programming data-structures
person Ankit Goel    schedule 10.12.2013    source источник
comment
Прежде всего, вы не можете использовать примитивные типы в качестве параметров для дженериков (таким образом, вы не можете использовать '‹', '›' и другие операторы). Во-вторых, вы должны связать свою коллекцию с классами, которые реализуют Comparable, и использовать метод compareTo, который должен помочь.   -  person mkrakhin    schedule 10.12.2013
comment
Вы не можете использовать арифметические операторы для дженериков. Если вам нужно сравнение объектов, ваш универсальный тип должен быть ограничен <T extends Comparable> или любой другой общей базой типов (обычно интерфейсом), которую вы создадите для логики реализации.   -  person Antoniossss    schedule 10.12.2013
comment
Или вам придется делегировать сравнение компаратору, определенному при построении двоичного дерева, как это делает TreeSet. Почему бы вам не посмотреть его документацию и код?   -  person JB Nizet    schedule 10.12.2013

Ответы (3)


arrow_upward
2
arrow_downward

Вы должны ограничить общий тип для вашего BinarySearchTree,

class BinarySearchTree<T extends Comparable<? super T>>

Элемент должен реализовывать интерфейс Comparable, иначе вы не сможете упорядочить элементы.

Изменить: как предлагает @JB Nizet, не используйте необработанные Comparable

person Qiang Jin    schedule 10.12.2013
comment
Должно быть BinarySearchTree<T extends Comparable<? super T>>. Не используйте необработанный тип Comparable. - person JB Nizet; 10.12.2013
comment
@JBNizet просто из любопытства ... почему нельзя использовать необработанные сопоставимые данные? - person Ankit Goel; 10.12.2013
comment
Потому что вы потеряете безопасность типов, которую обеспечивают универсальные типы. Так же, как вы не использовали бы ArrayList для хранения строк, но ArrayList<String>. - person JB Nizet; 10.12.2013

arrow_upward
0
arrow_downward

Думаю, я понимаю, о чем вы говорите. Как правило, хорошо спроектированные классы (вероятно, все стандартные классы, которые вы когда-либо использовали в JDK) реализуют Comparable и переопределяют встроенный метод compareTo, который определяет, как работают операции ‹, > и ==. CompareTo возвращает 1, если больше, 0, если равно, -1, если меньше.

Если вы хотите создать свой собственный класс для размещения в двоичном дереве, тогда да, вам придется реализовать Comparable.

Редактировать: ответ под мной делает очень важный момент: если вы собираетесь использовать сравнения, вы должны ограничить возможные типы классов теми, которые расширяют Comparable!

person AaronB    schedule 10.12.2013
comment
Итак, вы подразумеваете, что java.util.List плохо спроектирован, потому что он не реализует Comparable? Сравнение имеет смысл только для очень ограниченного подмножества классов. - person Vincent van der Weele; 10.12.2013
comment
Вставка @heuster в двоичное дерево поиска требует сортировки, и поэтому элементы необходимо сравнивать ... в случае элементов класса списка не нужно сравнивать для написания базовых функций, таких как addToList, поэтому список все равно не требует сравнения - person Ankit Goel; 10.12.2013
comment
List на самом деле не имеет отношения к сравнению, но я полагаю, что сформулировал его менее точно, чем мог бы. Я хочу сказать, что классы данных обычно реализуют Comparable. - person AaronB; 10.12.2013

arrow_upward
0
arrow_downward

Чтобы выполнить другие ответы:

Реализация интерфейса Comparable имеет смысл только для классов. которые действительно имеют естественный порядок. Кроме того, этот порядок должен соответствовать методу equals. Реализация методов equals и compareTo звучит проще, чем иногда есть на самом деле. Это должно быть хорошо продумано.

Довольно часто объекты класса не имеют реального естественного порядка. Но у вас все равно будут задачи заказать их на конкретный объект. Для таких задач можно реализовать другой интерфейс: Comparator . Затем можно использовать компаратор для упорядочения ваших объектов по мере необходимости.

Взгляните на TreeSet, который является таким дерево поиска. Эта реализация Set предоставляет два конструктора: один предназначен для использования с сопоставимыми объектами. Другой использует компаратор для этой задачи и предназначен для использования с несопоставимыми объектами.

person Seelenvirtuose    schedule 10.12.2013