equivalente a un diccionario ordenado que permite claves duplicadas

Question

Necesito una estructura de datos que pueda ordenar objetos por las teclas flotantes a las que están asociados, el más bajo primero. El problema es que las teclas representan el costo, por lo que a menudo hay duplicados, no me importa esto porque si dos tienen el mismo costo, simplemente agarraré el primero ya que no importa, el problema es que el compilador se queja.

¿Hay una estructura de datos que se comporta de la misma manera pero permite duplicar claves?

EDITAR - todavía tengo los duplicados, porque aunque si uno resulta ser un callejón sin salida, me agarra la siguiente (son nodos en una búsqueda *)

tan sólo para ser claros, se necesita permitir claves duplicadas que están ordenadas en orden.

Answer 1

Lo que estás buscando se llama heap o priority queue. Estoy seguro de que si buscas en Google encontrarás uno para C#

Answer 2

Aún puedes utilizar un diccionario. Usted sólo necesita cambiar el tipo de los valores a ser colecciones en lugar de elementos individuales:

Dictionary<float, List<T>> 

Un diccionario sea definición no permite duplicados de las llaves.

Answer 3

Está buscando Lookup. De manera similar a otras soluciones basadas en diccionarios ya propuestas, almacena un IEnumerable debajo de cada clave para manejar duplicados.

var registry = Items.ToLookup(item=>item.Price); 
foreach(var item in registry[desiredPrice]) 
{ 
    //Here you handle items that all have Price == desiredPrice 
} 

Answer 4

escribe:

equivalente a un diccionario que permite duplicados de las llaves

que necesito una estructura de datos que se pueden clasificar objetos por las llaves de flotador que están asociados con los primeros, más bajo.

Un diccionario no mantiene los elementos ordenados por las teclas, por lo que la estructura que está buscando en realidad no es equivalente a un Dictionary en absoluto. Lo que desea es algo similar a SortedList o SortedDictionary, excepto que debe permitir claves duplicadas.

No existe tal clase en .NET. Sin embargo, usted tiene algunas opciones:

• Uso SortedDictionary<double, List<TValue>> si desea almacenar todos los valores asociados a una clave, a pesar de que por lo general sólo es necesario la primera. Al insertar una clave por primera vez, cree una nueva lista y agregue el valor a la lista. Al insertar una clave que ya existe, busque la lista y agregue el valor a la lista.
• _{Su edición significa que este enfoque no se aplica a su situación.} Use SortedDictionary<double, TValue> y verifique si hay duplicados antes de insertar. Solo se almacenará el primer valor para cada clave, por lo que a diferencia del enfoque anterior, no se puede acceder al segundo valor con este método.
• Encuentra una biblioteca de colecciones de terceros que tenga una clase que haga lo que quieras.

relacionada

• What's the difference between SortedList and SortedDictionary?

Answer 5

Lo que estamos hablando es de una bolsa. La diferencia entre un bolsa y un conjunto es que los juegos son únicos, mientras que los bolsos permiten duplicados. {a, b, c} es un conjunto; {a, b, c, a} es una bolsa.

Obtenga una copia del C5 Collections Library. Desea las clases HashBag<T> o TreeBag<T>. La diferencia es que el almacén de datos subyacente en uno es un hash y un árbol rojo-negro en el otro. Externamente, se comportan igual. Cualquiera de los dos debería darle lo que quiere.

Answer 6

Usted puede crear su propia clase que deriva de SortedSet:

public class SortedTupleBag<TKey, TValue> : SortedSet<Tuple<TKey, TValue>> 
    where TKey : IComparable 
{ 
    private class TupleComparer : Comparer<Tuple<TKey, TValue>> 
    { 
     public override int Compare(Tuple<TKey, TValue> x, Tuple<TKey, TValue> y) 
     { 
      if (x == null || y == null) return 0; 

      // If the keys are the same we don't care about the order. 
      // Return 1 so that duplicates are not ignored. 
      return x.Item1.Equals(y.Item1) 
       ? 1 
       : Comparer<TKey>.Default.Compare(x.Item1, y.Item1); 
     } 
    } 

    public SortedTupleBag() : base(new TupleComparer()) { } 

    public void Add(TKey key, TValue value) 
    { 
     Add(new Tuple<TKey, TValue>(key, value)); 
    } 
} 

uso en una aplicación de consola:

private static void Main(string[] args) 
{ 
    var tuples = new SortedTupleBag<decimal, string> 
    { 
     {2.94M, "Item A"}, 
     {9.23M, "Item B"}, 
     {2.94M, "Item C"}, 
     {1.83M, "Item D"} 
    }; 

    foreach (var tuple in tuples) 
    { 
     Console.WriteLine("{0} {1}", tuple.Item1, tuple.Item2); 
    } 

    Console.ReadKey(); 
} 

produce este resultado:

1.83 Item D 
2.94 Item A 
2.94 Item C 
9.23 Item B 

Answer 7

He golpeado este problema varias veces, y siempre uso la licencia pública (es decir, gratis) Power Collections de Win tellect (http://powercollections.codeplex.com). Tienen un OrderedMultiDictionary que es exactamente lo que estás buscando. Permite duplicar claves y te permite iterar a través de todas las entradas de claves duplicadas.

Answer 8

Debería poder utilizar un SortedDictionary con una implementación personalizada de IComparer para evitar colisiones. Por ejemplo:

private class NonCollidingFloatComparer : IComparer<float> 
{ 
    public int Compare(float left, float right) 
    { 
     return (right > left) ? -1 : 1; // no zeroes 
    } 
} 

// silly method for the sake of demonstration 
public void sortNodes(List<Node> nodesToSort) 
{ 
    SortedDictionary<float, Node> nodesByWeight = new SortedDictionary<float, Node>(new NonCollidingFloatComparer()); 
    foreach (Node n in nodesToSort) 
    { 
     nodesByWeight.Add(n.FloatKey, n); 
    } 
    foreach (Node n in nodesByWeight.Values) 
    { 
     Console.WriteLine(n.FloatKey + " : " + n.UniqueID); 
    } 
} 

Answer 9

Puede hacerlo anulando CompareTo fucntion. Cuando agrega un elemento a SortedDictionary, usa CompareTo(), si el resultado es 0, hace una excepción, pero puede cambiar el comportamiento del comparador de la implementación de la clase de clave para que solo sea mayor o menor que (1 o -1)

 public int CompareTo(int key) 
    { 
     if (this.key.CompareTo(key) < 1) 
      return 1; 
     else 
      return -1; 
    }