¿Existe una cola ordenada en .NET?

Question

Necesito una colección .NET bastante especializada, y no creo que el BCL me pueda ayudar, pero pensé que podría tirarlo si alguien sabía algo similar.

Básicamente, mis requisitos son por lo tanto:

• tengo una lista de pares de valores, tales como: (3, 10), (5, 10), (3, 7), (5, 5)
• El pedido es importante, es decir. (3, 10)! = (10, 3)
• Los duplicados de valores individuales son correctos, pero los pares duplicados deben descartarse (preferiblemente en silencio).
• El truco es, necesito esta lista ordenada todo el tiempo. Solo me interesa el primer valor de la lista según lo define el algoritmo de ordenación en cualquier momento.

Por lo tanto, un código de ejemplo de lo que quiero ser capaz de hacer (como yo imaginar que probablemente se llevaría a cabo, otras implementaciones que se ajustan a la anterior son bien a):

public class Pair 
{ 
    public Pair(int first, int second) 
    { First = first; Second = second; } 
    public int First { get; set; } 
    public int Second { get; set; } 
} 

SortedQueue<Pair> foo = new SortedQueue<Pair>((left, right) => { 
    return right.First - left.First; 
}); 

foo.Add(new Pair(10, 3)); 
foo.Add(new Pair(4, 6)); 
foo.Add(new Pair(6, 15)); 
foo.Add(new Pair(6, 13)); // This shouldn't cause a problem 

Pair current = foo.Shift(); // current = (4, 6) 

Answer 1

cito:

necesito esta lista ordenada todo el tiempo. Solo me interesa el primer valor en la lista según lo definido por el algoritmo de ordenación en cualquier momento.

esto suena como lo hace no quieren una cola Ordenado sino un Priority Queue. Si el rendimiento es un problema, entonces un PQ sin duda será más rápido, O (log n) vs O (n). Pero el problema de los duplicados también requerirá que guardes un HashSet paralelo <>.

Answer 2

usted tiene miró SortedDictionary o SortedList?

Answer 3

SortedList sería lo mejor, todo lo que tienes que hacer entonces es implementar IComparable en tu clase Pair, y los ordenaría automáticamente. En cuanto a eliminar duplicados, no creo que la lista ordenada maneje eso, pero podría heredar de él y agregar esta funcionalidad.

Answer 4

lo más probable es que use una clase de búsqueda como The Skeet menciona en his answer. A continuación, se construye y acceder a ella con algo como esto:

List<Lookup<int, int>> yourList = new List<Lookup<int, int>>(); 
yourList.Add(new Lookup(3,5)); 
//... 
var list = from item in yourList 
      orderby list.Key //or whatever sort criteria you want here 
      select item; 
//use list 

La sintaxis puede ser un poco apagado en 1 ó 2 puntos, pero se debe trabajar.

Answer 5

No hay nada integrado en .NET en este momento que cumpla con todos sus requisitos. En .NET 4.0 hay una clase SortedSet. Me doy cuenta de que probablemente ya no te sirva de mucho.

SortedList se acerca si implementa IComparable. Simplemente usaría el par como la clave y el valor. Solo almacenaría la referencia a su par dos veces para que no sea una gran sobrecarga de memoria. Pero esto no se ocupará de duplicados.

Existen numerosas formas de escribirlo usted mismo, pero nada incorporado que coincida completamente con lo que necesita. Hay algunas implementaciones de código abierto SortedSet (hay una en Spring.Net por ejemplo). Esa podría ser tu mejor apuesta en este momento.

Answer 6

Eche un vistazo a C5 Generic Collections Library que ya tiene una implementación como la que está buscando, llamada IntervalHeap o Priority Queue. Aquí hay algo de documentación del libro C5: IPriorityQueue<T>