Реализована отсортированная коллекция Java, которая допускает множество одинаковых значений

Я пытался использовать TreeSet:

Comparator<Product> pc = (p1, p2) -> ((Double) p1.getPrice()).compareTo(p2.getPrice());
Set<Product> products = new TreeSet<>(pc);
products.add(new Product(10));
products.add(new Product(10));

но проблема в том, что он не может содержать более одного равного значения с точки зрения компаратора, поэтому только один продукт будет в наборе products.

Мне нужна некоторая реализация коллекции, которая упорядочивает вновь вставленное значение, допускает множество равных (с точки зрения компаратора) значений и имеет сложность вставки log(n) (возможно, реализация на основе дерева)


java collections
person Kysil Ivan    schedule 08.02.2017    source источник
comment
У ваших продуктов есть что-то уникальное, например, productId?   -  person assylias    schedule 08.02.2017
comment
Возможный дубликат реализации списка, который поддерживает порядок   -  person shmosel    schedule 08.02.2017
comment
assyliad: нет, мне не нужен ID Кажется, Guava TreeMultiset мне подходит, но мне интересно, смогу ли я сделать это, просто используя Java Collection API.   -  person Kysil Ivan    schedule 08.02.2017
comment
Когда вы говорите на основе дерева, вы действительно имеете в виду отсортированный? Внутренняя реализация коллекции не должна иметь для вас большого значения.   -  person Andy Turner    schedule 08.02.2017
comment
Вы можете найти что-то интересное в Почему в Java нет SortedList?.   -  person Andy Turner    schedule 08.02.2017
comment
Например, для сравнения сложности по времени см. infotechgems.blogspot.de/ 2011/11/.   -  person René Scheibe    schedule 08.02.2017

Ответы (3)


arrow_upward
4
arrow_downward

class в JDK, который точно соответствует вашим требованиям, называется PriorityQueue . Из документации:

Очередь с неограниченным приоритетом, основанная на куче приоритетов. Элементы приоритетной очереди упорядочиваются в соответствии с их естественным порядком или с помощью Comparator, предоставленного во время построения очереди, в зависимости от того, какой конструктор используется.

А также

Примечание реализации: эта реализация обеспечивает O(log(n)) времени для методов постановки в очередь и удаления из очереди (offer, poll, remove() и add); линейное время для методов remove(Object) и contains(Object); и постоянное время для методов поиска (peek, element и size).

Вы также можете продолжить использовать TreeSet, но указать Comparator, который дает уникальный ответ. Например, если ваш Product имеет уникальный name:

Comparator<Product> pc = Comparator.comparing(Product::getPrice)
                         .thenComparing(Comparator.comparing(Product::getName));

Обратите внимание на использование Comparator.comparing вместо вашей лямбды - это аккуратнее и надежнее.

person Boris the Spider    schedule 08.02.2017
comment
Спасибо, я только что попробовал JDK PriorityOueue, и меня это устраивает. - person Kysil Ivan; 08.02.2017

arrow_upward
2
arrow_downward

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

person René Scheibe    schedule 08.02.2017

arrow_upward
0
arrow_downward

Итак,
PriorityQueue работала для меня.

TreeMultiset сделал нет. Когда я добавляю два разных объекта:
products.add(new Product(10)); products.add(new Product(10));
он содержит две ссылки для первого экземпляра и ни одной для второго()

person Kysil Ivan    schedule 08.02.2017