Внедрение списка, поддерживающее порядок

Ответ 1

Ответ на новое требование. Я вижу два потенциала:

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

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

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

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

• Рассмотрите возможность использования 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(""); }
  }
  

• Используйте Guava 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. Я вижу, что вам также нужен итератор, поэтому это не сработает.

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

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

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

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

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

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

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

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

работ:

• Сообщение в блоге PriorityQueue Итератор не заказывается
• Вопрос SO на PQ упорядоченный итератор

Ответ 2

Вероятно, вы должны использовать TreeSet:

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

Пример:

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

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

Ответ 3

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

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