Реализация списка, поддерживающая заказ

Question

Есть ли существующая реализация List на Java, которая поддерживает заказ на основе предоставленных Comparator?

Что-то, что может быть использовано следующим образом:

Comparator<T> cmp = new MyComparator<T>(); 
List<T> l = new OrderedList<T>(cmp); 
l.add(someT); 

так, что someT получает вставляется таким образом, что порядок в списке осуществляется в соответствии с cmp

(На @andersoj внушения я завершаю мой вопрос с еще одним запросом)

Также я хочу, чтобы иметь возможность перемещать список в отсортированном порядке без удаления элементов, то есть:

T min = Const.SMALLEST_T; 
for (T e: l) { 
    assertTrue(cmp.compare(min, e) >= 0); 
    min = e; 
} 

должно пройти.

Все предложения приветствуются (кроме говоря мне использовать Collections.sort на неупорядоченный полный список), хотя я предпочел бы что-то в java.* или в конце концов org.apache.*, так как это было бы трудно представить новые библиотеки в данный момент.

Примечание: (UPDATE4) я понял, что реализация такого рода списка будет иметь недостаточную производительность. Там два общих подхода:

1. Использование Linked структура (вид) B-дерево или аналогичные
2. Использование массива и вставки (с двоичным поиском)

Нет 1. имеет проблемы с промахов кэша процессора Нет 2. проблема с перемещением элементов в массиве.

UPDATE2: TreeSet не работает, потому что он использует прилагаемый компаратор (MyComparator) для проверки равенства и основанного на нем предполагается, что они равны, и исключить их. Мне нужна, что компаратор только для заказа, а не «уникальности» фильтрация (поскольку элементы по их естественному порядку не равны)

Update3: PriorityQueue не работает, как List (как мне нужен), потому что есть никоим образом не перемещать его в порядке «сортировка», чтобы получить элементы в отсортированном порядке, которые вы должны удалить из коллекции.

UPDATE:

Похожий вопрос:
A good Sorted List for Java
Sorted array list in Java

Answer 1

Реакция на новые требования. Я вижу два потенциала:

• делать то, что JavaDoc для PriorityQueue говорит:

  Этот класс и его итератора реализации всех дополнительных методов интерфейсов Collection и Iterator. Итератору, предоставленному в методе iterator(), не гарантируется пересечение элементов очереди приоритетов в любом конкретном порядке. Если вам требуется упорядоченный обход, подумайте об использовании Arrays.sort(pq.toArray()).

  Я подозреваю, что это даст наилучшую производительность, учитывая ваши требования. Если это неприемлемо, вам нужно лучше объяснить, что вы пытаетесь выполнить.

• Построение a Список, который просто сортирует себя при добавлении новых элементов. Это настоящая боль ... если вы использовали связанную структуру, вы можете сделать эффективную сортировку вставки, но местность плохая. Если вы использовали структуру с поддержкой массива, сортировка вставки - боль, но обход лучше. Если итерация/обход нечастая, вы можете сохранить содержимое списка несортированным и отсортировать только по требованию.

• Рассмотрите возможность использования PriorityQueue как я предложил, и в том случае, вам нужно перебирать по порядку, написать обертку итератора:

  class PqIter implements Iterator<T> 
  { 
      final PriorityQueue<T> pq; 
      public PqIter(PriorityQueue <T> source) 
      { 
      pq = new PriorityQueue(source); 
      } 
  
      @Override 
      public boolean hasNext() 
      { 
      return pq.peek() != null 
      } 
  
      @Override 
      public T next() 
      { return pq.poll(); } 
  
      @Override 
      public void remove() 
      { throw new UnsupportedOperationException(""); } 
  } 
  

• Использование гуавы-х TreeMultiSet. Я проверил следующий код с Integer, и он, кажется, поступает правильно.

  import com.google.common.collect.TreeMultiset; 
  
  public class TreeMultiSetTest { 
      public static void main(String[] args) { 
      TreeMultiset<Integer> ts = TreeMultiset.create(); 
      ts.add(1); ts.add(0); ts.add(2); 
      ts.add(-1); ts.add(5); ts.add(2); 
  
      for (Integer i : ts) { 
       System.out.println(i); 
      } 
      } 
  } 
  

Ниже рассматриваются проблемы уникальности/фильтрации вы имели при использовании SortedSet. Я вижу, что вам тоже нужен итератор, так что это не сработает.

Если вы действительно хотите заказать list-like вещь, вы можете использовать PriorityQueue.

Comparator<T> cmp = new MyComparator<T>(); 
PriorityQueue<T> pq = new PriorityQueue<T>(cmp); 
pq.add(someT); 

Обратите внимание на то, что сказано в документации API о временных свойствах различных операций: Примечание

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

Вы также должны знать, что итераторы, полученные PriorityQueue не ведут себя, как можно было бы ожидать:

Iterator предусмотрено в методе iterator() не гарантируется для обхода элементов приоритетной очереди в любой определенный порядок. Если вам требуется упорядоченный обход, подумайте об использовании Arrays.sort(pq.toArray()).

Я только что заметил, что Гуава предоставляет MinMaxPriorityQueue. Эта реализация поддерживает массив, а не связанную форму, представленную в JDK PriorityQueue, и, вероятно, имеет разные временные характеристики. Если вы делаете что-то чувствительное к производительности, вы можете взглянуть. В то время как заметки дают немного разные (линейные и логарифмические) времена больших O, все эти времена также должны быть ограничены, что может быть полезно.

Реализация List сама по себе, которая поддерживает заказы, но то, что вы, скорее всего, ищете, является реализациями SortedSet. A TreeSet является наиболее распространенным. Другая реализация, ConcurrentSkipListSet предназначена для более конкретных целей. Обратите внимание, что SortedSet обеспечивает упорядочение, но не позволяет дублировать записи, как и List.

Refs:

• Запись в блоге PriorityQueue iterator is not ordered
• SO вопрос о PQ ordered iterator

Answer 2

Вы, вероятно, следует с помощью TreeSet:

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

Пример:

Comparator<T> cmp = new MyComparator<T>(); 
TreeSet<T> t = new TreeSet<T>(cmp); 
l.add(someT); 

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

Answer 3

У меня аналогичная проблема, и я имею в виду, используя TreeSet. Чтобы избежать исключения «равных» элементов, я буду модифицировать компаратор, поэтому вместо возврата 0 он вернет случайное число между (-1,1) или будет всегда возвращаться 1.

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