Implementación de lista que mantiene el pedido

Question

¿Existe una implementación de List en Java que mantenga el orden según Comparator?

Algo que puede ser utilizado de la siguiente manera:

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

modo que someT se inserta de tal manera que el orden de la lista se mantiene de acuerdo a cmp

(En @andersoj sugerencia estoy terminando mi pregunta con una solicitud más)

También quiero poder recorrer la lista en orden ordenado sin eliminar los elementos, es decir:

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

debe pasar.

Todas las sugerencias son bienvenidos (excepto diciéndome utilizar Collections.sort en la lista completa no ordenada), sin embargo, yo preferiría algo en java.* o eventualmente org.apache.* ya que sería difícil introducir nuevas bibliotecas en este momento.

Nota: (Update4) me di cuenta de que las implementaciones de este tipo de lista tendrían un desempeño inadecuado. Hay dos enfoques generales:

1. Uso estructura Vinculado (tipo de) B-árbol o similares
2. Uso matriz y la inserción (con búsqueda binaria)

No 1. tiene un problema con los errores de caché de la CPU No 2. tiene problemas con el desplazamiento de elementos en el conjunto.

Update2: TreeSet no funciona porque utiliza el comparador proporcionado (MyComparator) para comprobar la igualdad y en base a que asume que los elementos son iguales y no ellos. Necesito que comparador sólo para pedidos, no filtrado "singularidad" (ya que los elementos por su orden natural no son iguales)

Update3: PriorityQueue no funciona como List (ya que necesito) porque no hay no hay forma de recorrerlo en el orden en que está "ordenado", para obtener los elementos en el orden ordenado, debe eliminarlos de la colección.

ACTUALIZACIÓN:

Pregunta similar:
A good Sorted List for Java
Sorted array list in Java

Answer 1

Respuesta a un nuevo requisito. Veo dos posibilidades:

• hacer lo que el Javadoc para PriorityQueue dice:

  Esta clase y su iterador implementar todos los métodos opcionales de las interfaces Collection e Iterator. No se garantiza que el iterador provisto en el método iterator() atraviese los elementos de la cola de prioridad en un orden particular. Si necesita un recorrido ordenado, considere usar Arrays.sort(pq.toArray()).

  Sospecho que esto dará el mejor rendimiento según sus necesidades. Si esto no es aceptable, tendrá que explicar mejor lo que está tratando de lograr.

• Genere una lista que simplemente se ordena al agregar nuevos elementos. Esto es un verdadero dolor ... si usó una estructura vinculada, puede hacer una ordenación de inserción eficiente, pero la localidad es mala. Si usó una estructura respaldada por una matriz, la ordenación por inserción es un problema, pero el recorrido es mejor. Si la iteración/recorrido es poco frecuente, puede mantener el contenido de la lista sin clasificar y ordenar solo a pedido.

• considerar el uso de un PriorityQueue como he sugerido, y en el caso de que deba recorrer el fin, escribir un iterador de envoltorio:

  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(""); } 
  } 
  

• Uso de guayaba TreeMultiSet. Probé el siguiente código con Integer y parece hacer lo correcto.

  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); 
      } 
      } 
  } 
  

La continuación aborda el problema de la singularidad/filtrado que tenías cuando se utiliza un SortedSet. Veo que también quieres un iterador, así que esto no funcionará.

Si lo que realmente quiere es una cosa list-like, puede hacer uso de un PriorityQueue.

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

Toma nota de lo que la documentación de la API dice acerca de las propiedades de tiempo de varias operaciones: Nota

Implementación: esta aplicación proporciona O (log (n)) tiempo para la enqueing y dequeing métodos (offer, poll, remove() y add); lineal tiempo para los métodos remove(Object) y contains(Object); y constante tiempo para los métodos de recuperación (peek, element y size).

También debe tener en cuenta que los iteradores producidos por PriorityQueue no se comportan como cabría esperar:

El Iterator proporcionado en el método iterator() no está garantizado para atravesar los elementos de la cola de prioridad en cualquier orden particular. Si necesita un recorrido ordenado, considere usar Arrays.sort(pq.toArray()).

Acabo de notar que la guayaba proporciona un MinMaxPriorityQueue. Esta implementación está respaldada por una matriz, en lugar de la forma enlazada proporcionada en el PriorityQueue del JDK, y es probable que tenga un comportamiento de sincronización diferente. Si está haciendo algo sensible al rendimiento, es posible que desee echar un vistazo. Mientras que las notas dan tiempos de O grandes levemente diferentes (lineales y logarítmicos), todos esos tiempos también deben estar acotados, lo que puede ser útil.

No existe una implementación en List per se que mantenga el orden, pero lo que probablemente busque son implementaciones de SortedSet. A TreeSet es el más común. La otra implementación, un ConcurrentSkipListSet es para usos más específicos. Tenga en cuenta que un SortedSet proporciona pedidos, pero no permite entradas duplicadas, como lo hace un List.

Refs:

• Blog colocar PriorityQueue iterator is not ordered
• pregunta para el PQ ordered iterator

Answer 2

Probablemente debería utilizar un TreeSet:

Los elementos se ordenan utilizando su orden natural, o por un comparador proporcionado en el tiempo de creación del conjunto, dependiendo de qué constructor se use.

Ejemplo:

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

Tenga en cuenta que este es un conjunto, por lo que no se permiten entradas duplicadas. Esto puede o no funcionar para su caso de uso específico.

Answer 3

Tengo un problema similar y estoy pensando en usar un TreeSet. Para evitar excluir elementos "iguales", modificaré el comparador para que en lugar de devolver 0, devuelva un número aleatorio entre (-1,1) o retorne siempre 1.

Si no tiene control sobre el Comparador o Si lo está utilizando para otra cosa diferente a la inserción de esta solución, no funcionará para usted.