Implementación de lista que mantiene el orden

Question

¿Existe alguna List Implementación en Java que mantiene el orden según lo proporcionado. Comparator?

Algo que se puede utilizar de la siguiente manera:

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

de modo que someT se inserta de manera que el orden en la lista se mantenga de acuerdo con cmp

(Por sugerencia de @andersoj, estoy completando mi pregunta con una solicitud más)

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

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

debería pasar.

Todas las sugerencias son bienvenidas (excepto decirme que use Collections.sort en la lista completa desordenada), sin embargo, preferiría algo en java.* o eventualmente org.apache.* ya que sería difícil introducir nuevas bibliotecas en este momento.

Nota:(ACTUALIZACIÓN4) Me di cuenta de que las implementaciones de este tipo de lista tendrían un rendimiento inadecuado.Hay dos enfoques generales:

1. Utilice una estructura vinculada (una especie de) árbol B o similar
2. Usar matriz e inserción (con búsqueda binaria)

No 1.tiene un problema con la caché de la CPU se pierde el no 2.tiene problemas con el cambio de elementos en una matriz.

ACTUALIZACIÓN2: TreeSet no funciona porque utiliza el comparador proporcionado (MyComparator) para comprobar la igualdad y, en base a ello, supone que los elementos son iguales y los excluye.Necesito ese comparador sólo para ordenar, no para filtrar por "singularidad" (ya que los elementos por su orden natural no son iguales)

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

ACTUALIZAR:

Pregunta similar:
Una buena lista ordenada para Java
Lista de matrices ordenadas en Java

Answer 1

Respuesta a nuevo requerimiento.Veo dos potenciales:

• Haz para qué sirve el JavaDoc PriorityQueue dice:

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

  Sospecho que esto producirá el mejor rendimiento según sus requisitos.Si esto no es aceptable, deberá explicar mejor lo que está tratando de lograr.

• Construir un Lista que simplemente se ordena a sí mismo al agregar nuevos elementos.Esto es un dolor verdadero...Si utilizó una estructura vinculada, puede realizar una ordenación por inserción eficiente, pero la localidad es mala.Si utilizó una estructura respaldada por una matriz, la ordenación por inserción es una molestia, pero el recorrido es mejor.Si la iteración/recorrido es poco frecuente, puede mantener el contenido de la lista sin ordenar y ordenar solo según demanda.

• Considere usar un Cola de prioridad como sugerí, y en caso de que necesite iterar en orden, escriba un iterador contenedor:

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

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

Lo siguiente aborda el problema de unicidad/filtrado que tenía al utilizar un SortedSet.Veo que también quieres un iterador, así que esto no funcionará.

Si lo que realmente quieres es un ordenado en forma de lista cosa, puedes hacer uso de un PriorityQueue.

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

Tome nota de lo que dice la documentación de la API sobre las propiedades de tiempo de varias operaciones:

Nota de implementación:esta implementación proporciona O(log(n)) tiempo para los métodos de enqueing y dequeing (offer, poll, remove() y add); lineal tiempo para el remove(Object) y contains(Object) métodos;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 te comportes como cabría esperar:

El Iterator proporcionado en el método iterator() No se garantiza que atraviese los elementos de la cola de prioridad en ningún 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 matrices, en lugar del formulario vinculado proporcionado en el JDK. PriorityQueue, y, por lo tanto, es probable que tenga un comportamiento de sincronización diferente.Si está haciendo algo sensible al rendimiento, es posible que desee echarle un vistazo.Si bien las notas dan tiempos de O mayor ligeramente diferentes (lineales y logarítmicos), todos esos tiempos también deben estar acotados, lo que puede resultar útil.

No hay un List implementación per se que mantiene el orden, pero lo que probablemente esté buscando son implementaciones de SortedSet.A TreeSet es el más común.La otra implementación, una ConcurrentSkipListSet es para usos más específicos.Tenga en cuenta que un SortedSet proporciona pedidos, pero no permite entradas duplicadas, al igual que un List.

Árbitros:

• Entrada en el blog PriorityQueue el iterador no está ordenado
• Así que pregunta sobre Iterador ordenado PQ

Answer 2

Probablemente deberías estar usando un Conjunto de árboles:

Los elementos se ordenan utilizando su orden natural o mediante un Comparador proporcionado en el momento de la creación establecido, según el constructor que se utilice.

Ejemplo:

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

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

Answer 3

Tengo un problema similar y estoy pensando en usar 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 devuelva siempre 1.

Si no tiene control sobre el Comparador o si lo está usando para algo diferente a insertar, esta solución no funcionará para usted.