Keine generische Implementierung von OrderedDictionary?

Es scheint nicht zu sein, eine generische Implementierung von OrderedDictionary (das ist in den System.Collections.Specialized namespace).NET 3.5. Gibt es eine, die mir fehlt?

Habe ich gefunden-Implementierungen gibt, um die Funktionalität, sondern fragte mich, ob/warum es nicht ein generische Implementierung " out-of-the-box und wenn jemand weiß, ob es etwas in .NET 4.0?

InformationsquelleAutor der Frage AdaTheDev | 2010-04-13

.net .net-4.0 c#generics ordereddictionary

54

Du hast Recht. Es gibt keine generische äquivalent von OrderedDictionary im framework selbst.

(Das ist immer noch der Fall ist .NET4 auch, so weit ich bewusst bin.)

BEARBEITEN: Aber Sie können für ihn abstimmen auf Visual Studio UserVoice!

InformationsquelleAutor der Antwort LukeH
29

Für die Aufzeichnung gibt es eine generische KeyedCollectionmit dem Objekte indiziert werden, indem ein int und ein Schlüssel. Der Schlüssel muss eingebettet werden in den Wert.

InformationsquelleAutor der Antwort Guillaume
17

Hier ist eine bizarre finden: das System.Web.Util-namespace in System.Web.Extensions.dll enthält einen generischen OrderedDictionary
```
//Type: System.Web.Util.OrderedDictionary`2
//Assembly: System.Web.Extensions, Version=4.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35
//Assembly location: C:\Windows\Microsoft.NET\Framework\v4.0.30319\System.Web.Extensions.dll

namespace System.Web.Util
{
    internal class OrderedDictionary<TKey, TValue> : IDictionary<TKey, TValue>, ICollection<KeyValuePair<TKey, TValue>>, IEnumerable<KeyValuePair<TKey, TValue>>, IEnumerable
```
Nicht sicher, warum MS es dort abgelegt, anstatt das System.Sammlungen.Generisches Paket, aber ich nehme an, Sie können einfach kopieren Sie den code und verwenden Sie es (es ist intern, also kann es nicht verwenden, direkt). Sieht aus wie die Implementierung verwendet ein standard-Wörterbuch und getrennte Schlüssel/Wert-Listen. Ziemlich einfach...

InformationsquelleAutor der Antwort Ismail Degani

Für was es Wert ist, hier ist, wie ich es gelöst (bearbeitet um zu verbessern mein Erster Versuch):

   public class PairList<TKey, TValue> : List<KeyValuePair<TKey, TValue>> {
        Dictionary<TKey, int> itsIndex = new Dictionary<TKey, int>();

        public void Add(TKey key, TValue value) {
            Add(new KeyValuePair<TKey, TValue>(key, value));
            itsIndex.Add(key, Count-1);
        }

        public TValue Get(TKey key) {
            var idx = itsIndex[key];
            return this[idx].Value;
        }
    }

Es kann initialisiert werden, wie diese:

var pairList = new PairList<string, string>
    {
        { "pitcher", "Ken" },
        { "catcher", "Brad"},
        { "left fielder", "Stan"},
    };

zugänglich und so:

foreach (var pair in pairList)
{
    Console.WriteLine("position: {0}, player: {1}",
        pair.Key, pair.Value);            
}

//guaranteed to print in the order of initialization

InformationsquelleAutor der Antwort JoelFan

14

Einem großen konzeptionellen problem mit einer generischen version von OrderedDictionary ist, dass Nutzer einer OrderedDictionary<TKey,TValue> würde erwarten, erwarten zu können, zu indizieren, entweder numerisch mit einem int oder durch lookup über eine TKey. Wenn der Typ nur der Schlüssel war Objectwie war der Fall mit nicht-generischen OrderedDictionaryden Typ des übergebenen Arguments zu der indexer würde ausreichen, um zu unterscheiden, ob welche Art von Indizierungs-Vorgang durchgeführt werden soll. Wie es ist, aber es ist unklar, wie der indexer einer OrderedDictionary<int, TValue> sich Verhalten sollte.

Wenn Klassen wie Drawing.Point empfohlen hatte, und folgte einer Regel, die stückweise-veränderlichen Strukturen aussetzen sollte Ihre veränderliche Elemente wie Felder anstelle von Eigenschaften, und es unterlassen, mithilfe von property-setter das ändern thisdann ein OrderedDictionary<TKey,TValue> konnte effizient über eine ByIndex Eigenschaft, dass wieder ein Indexer struct, die einen Verweis auf das Wörterbuch, und hatte eine indizierte Eigenschaft, deren getter-und setter-aufrufen würde GetByIndex und SetByIndex auf. So könnte man sagen, so etwas wie MyDict.ByIndex[5] += 3; hinzufügen 3 auf das 6. element des Wörterbuchs. Leider, für den compiler zu akzeptieren ist so eine Sache, es würde erforderlich sein, um das ByIndex Eigentum zurück eine neue Instanz der Klasse eher als eine Struktur, die jedes mal, wenn er aufgerufen wird, die Beseitigung der Vorteile, die man erhalten würde, durch die Vermeidung von Boxen. In vb.net könnte man umgehen das Problem, indem Sie einen Namen indiziert-Eigenschaft (also MyDict.ByIndex[int] würde ein Mitglied MyDictanstatt dass MyDict.ByIndex Mitglied MyDict umfasst einen indexer), aber in C# nicht erlaubt, solche Dinge.

Könnte es sich gelohnt haben, eine OrderedDictionary<TKey,TValue> where TKey:classaber viel von der Grund für die Bereitstellung von Generika in den ersten Platz war, erlauben Ihre Verwendung mit Wert-Typen.

InformationsquelleAutor der Antwort supercat
6

Für viele Zwecke habe ich eine gefunden, kann man mit einem List<KeyValuePair<K, V>>. (Nicht, wenn Sie es brauchen zu verlängern Dictionary offensichtlich, und nicht wenn Sie müssen besser als O(n) Schlüssel-Wert-Suche.

InformationsquelleAutor der Antwort David Moles
5

Es ist SortedDictionary<TKey, TValue>. Obwohl es semantisch nahe, ich bin nicht fordern, es ist das gleiche wie OrderedDictionary einfach, weil Sie es nicht sind. Auch aus performance-Eigenschaften. Jedoch die sehr interessante und durchaus wichtige Unterschied zwischen Dictionary<TKey, TValue> (und insofern OrderedDictionary und Implementierungen in Antworten) und SortedDictionary ist, dass die letztere ist die Benutzung mit Binär-Baum unter. Dieses ist der kritische Unterschied, weil es macht die Klasse der immun-Gedächtnis-Einschränkungen angewandt, um generische Klasse. Siehe diesen thread über OutOfMemoryExceptions geworfen, wenn die generische Klasse für den Umgang mit großen Menge von Schlüssel-Wert-Paare.

Wie die Figur aus den max-Wert für die Kapazität parameter übergeben Wörterbuch-Konstruktor zu vermeiden OutOfMemoryException?

InformationsquelleAutor der Antwort Schultz9999

Recht, es ist eine bedauerliche Unterlassung. Ich vermisse Python ' s OrderedDict

Wörterbuch, das merkt sich die Reihenfolge, die Schlüssel wurden bei der ersten eingefügt. Wenn ein neuer Eintrag überschreibt einen bereits bestehenden Eintrag, der original-Einfügung-position ist unverändert. Eintrag löschen und erneute einfügen, verschieben Sie es bis zum Ende.

Also schrieb ich meine eigenen OrderedDictionary<K,V> Klasse in C#. Wie funktioniert es? Es unterhält zwei Sammlungen - eine Vanille-ungeordnete-Lexikon sowie eine sortierte Liste von Schlüsseln. Mit dieser Lösung werden die standard dictionary-Operationen halten Ihren schnellen Komplexität und nachschlagen-index ist schnell zu.

https://gist.github.com/hickford/5137384

Hier ist die Schnittstelle

///<summary>
///A dictionary that remembers the order that keys were first inserted. If a new entry overwrites an existing entry, the original insertion position is left unchanged. Deleting an entry and reinserting it will move it to the end.
///</summary>
///<typeparam name="TKey">The type of keys</typeparam>
///<typeparam name="TValue">The type of values</typeparam>
public interface IOrderedDictionary<TKey, TValue> : IDictionary<TKey, TValue>
{
    ///<summary>
    ///The value of the element at the given index.
    ///</summary>
    TValue this[int index] { get; set; }

    ///<summary>
    ///Find the position of an element by key. Returns -1 if the dictionary does not contain an element with the given key.
    ///</summary>
    int IndexOf(TKey key);

    ///<summary>
    ///Insert an element at the given index.
    ///</summary>
    void Insert(int index, TKey key, TValue value);

    ///<summary>
    ///Remove the element at the given index.
    ///</summary>
    void RemoveAt(int index);
}

InformationsquelleAutor der Antwort Colonel Panic

Als follow-up auf den Kommentar von @V. B. hier ist eine Barrierefreie Umsetzung der System.- Laufzeit.Sammlungen.OrderedDictionary<,>. Eigentlich wollte ich darauf zugreifen, indem Reflexion und geben es über eine Fabrik, aber die dll ist dieses nicht zu sein scheinen sehr zugänglich, überhaupt, so dass ich zog die Quelle selbst.

Eine Sache zu beachten ist der indexer hier wird nicht werfen KeyNotFoundException. Ich absolut hasse es, dass übereinkommen und das war der 1 liberty ich nahm in dieser Implementierung. Wenn das für Sie wichtig ist, einfach ersetzen Sie die Zeile für return default(TValue);. Verwendet C# 6 (kompatibel mit Visual Studio 2013)

///<summary>
///    System.Collections.Specialized.OrderedDictionary is NOT generic.
///    This class is essentially a generic wrapper for OrderedDictionary.
///</summary>
///<remarks>
///    Indexer here will NOT throw KeyNotFoundException
///</remarks>
public class OrderedDictionary<TKey, TValue> : IDictionary<TKey, TValue>, IDictionary
{
    private readonly OrderedDictionary _privateDictionary;

    public OrderedDictionary()
    {
        _privateDictionary = new OrderedDictionary();
    }

    public OrderedDictionary(IDictionary<TKey, TValue> dictionary)
    {
        if (dictionary == null) return;

        _privateDictionary = new OrderedDictionary();

        foreach (var pair in dictionary)
        {
            _privateDictionary.Add(pair.Key, pair.Value);
        }
    }

    public bool IsReadOnly => false;
    public int Count => _privateDictionary.Count;
    int ICollection.Count => _privateDictionary.Count;
    object ICollection.SyncRoot => ((ICollection)_privateDictionary).SyncRoot;
    bool ICollection.IsSynchronized => ((ICollection)_privateDictionary).IsSynchronized;

    bool IDictionary.IsFixedSize => ((IDictionary)_privateDictionary).IsFixedSize;
    bool IDictionary.IsReadOnly => _privateDictionary.IsReadOnly;
    ICollection IDictionary.Keys => _privateDictionary.Keys;
    ICollection IDictionary.Values => _privateDictionary.Values;

    void IDictionary.Add(object key, object value)
    {
        _privateDictionary.Add(key, value);
    }

    void IDictionary.Clear()
    {
        _privateDictionary.Clear();
    }

    bool IDictionary.Contains(object key)
    {
        return _privateDictionary.Contains(key);
    }

    IDictionaryEnumerator IDictionary.GetEnumerator()
    {
        return _privateDictionary.GetEnumerator();
    }

    void IDictionary.Remove(object key)
    {
        _privateDictionary.Remove(key);
    }

    object IDictionary.this[object key]
    {
        get { return _privateDictionary[key]; }
        set { _privateDictionary[key] = value; }
    }

    void ICollection.CopyTo(Array array, int index)
    {
        _privateDictionary.CopyTo(array, index);
    }

    public TValue this[TKey key]
    {
        get
        {
            if (key == null) throw new ArgumentNullException(nameof(key));

            if (_privateDictionary.Contains(key))
            {
                return (TValue) _privateDictionary[key];
            }

            return default(TValue);
        }
        set
        {
            if (key == null) throw new ArgumentNullException(nameof(key));

            _privateDictionary[key] = value;
        }
    }

    public ICollection<TKey> Keys
    {
        get
        {
            var keys = new List<TKey>(_privateDictionary.Count);

            keys.AddRange(_privateDictionary.Keys.Cast<TKey>());

            return keys.AsReadOnly();
        }
    }

    public ICollection<TValue> Values
    {
        get
        {
            var values = new List<TValue>(_privateDictionary.Count);

            values.AddRange(_privateDictionary.Values.Cast<TValue>());

            return values.AsReadOnly();
        }
    }

    public void Add(KeyValuePair<TKey, TValue> item)
    {
        Add(item.Key, item.Value);
    }

    public void Add(TKey key, TValue value)
    {
        if (key == null) throw new ArgumentNullException(nameof(key));

        _privateDictionary.Add(key, value);
    }

    public void Clear()
    {
        _privateDictionary.Clear();
    }

    public bool Contains(KeyValuePair<TKey, TValue> item)
    {
        if (item.Key == null || !_privateDictionary.Contains(item.Key))
        {
            return false;
        }

        return _privateDictionary[item.Key].Equals(item.Value);
    }

    public bool ContainsKey(TKey key)
    {
        if (key == null) throw new ArgumentNullException(nameof(key));

        return _privateDictionary.Contains(key);
    }

    public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
    {
        if (array == null) throw new ArgumentNullException(nameof(array));
        if (arrayIndex < 0) throw new ArgumentOutOfRangeException(nameof(arrayIndex));
        if (array.Rank > 1 || arrayIndex >= array.Length
                           || array.Length - arrayIndex < _privateDictionary.Count)
            throw new ArgumentException("Bad Copy ToArray", nameof(array));

        var index = arrayIndex;
        foreach (DictionaryEntry entry in _privateDictionary)
        {
            array[index] = 
                new KeyValuePair<TKey, TValue>((TKey) entry.Key, (TValue) entry.Value);
            index++;
        }
    }

    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
    {
        foreach (DictionaryEntry entry in _privateDictionary)
        {
            yield return 
                new KeyValuePair<TKey, TValue>((TKey) entry.Key, (TValue) entry.Value);
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    public bool Remove(KeyValuePair<TKey, TValue> item)
    {
        if (false == Contains(item)) return false;

        _privateDictionary.Remove(item.Key);

        return true;
    }

    public bool Remove(TKey key)
    {
        if (key == null) throw new ArgumentNullException(nameof(key));

        if (false == _privateDictionary.Contains(key)) return false;

        _privateDictionary.Remove(key);

        return true;
    }

    public bool TryGetValue(TKey key, out TValue value)
    {
        if (key == null) throw new ArgumentNullException(nameof(key));

        var keyExists = _privateDictionary.Contains(key);
        value = keyExists ? (TValue) _privateDictionary[key] : default(TValue);

        return keyExists;
    }
}

Pull-Anfragen/Diskussion auf GitHub angenommen

InformationsquelleAutor der Antwort Chris Marisic

Ich implementiert generische OrderedDictionary<TKey, TValue> durch wraping around SortedList<TKey, TValue> hinzufügen und privaten Dictionary<TKey, int> _order. Dann erstellte ich die interne Umsetzung von Comparer<TKey> Verweis auf die _order-Wörterbuch. Dann benutze ich dieses Programm für den internen SortedList. Diese Klasse sorgt für Ordnung der Elemente übergeben an den Konstruktor und die Reihenfolge der Ergänzungen.

Diese Umsetzung hat fast die gleiche BigO Eigenschaften wie SortedList<TKey, TValue> da das Hinzufügen und Entfernen zu _order ist O(1). Jedes element (nach dem Buch "C# von 4 in einer Nussschale', S. 292, Tabelle 7-1), zusätzlichen Speicherplatz von 22 (overhead) + 4 (int order) + TKey-Größe (lassen vermuten 8) = 34. Zusammen mit SortedList<TKey, TValue> overhead von 2 Byte der Gesamt-overhead von 36 bytes, während das gleiche Buch sagt, dass nicht-generische OrderedDictionary hat, overhead, 59 bytes.

Wenn ich pass sorted=true an den Konstruktor, dann _order ist überhaupt nicht verwendet, die OrderedDictionary<TKey, TValue> ist genau SortedList<TKey, TValue> mit geringen Aufwand für die Verpackung, wenn überhaupt sinnvoll.

Ich werde store-nicht-so-viele große Referenz-Objekte in der OrderedDictionary<TKey, TValue>also für mich.c.36 bytes Aufwand ist erträglich.

Den Haupt-code ist unten. Die kompletten aktualisierten code ist auf dieser gist.

public class OrderedList<TKey, TValue> : IDictionary<TKey, TValue>, IDictionary
{
    private readonly Dictionary<TKey, int> _order;
    private readonly SortedList<TKey, TValue> _internalList;

    private readonly bool _sorted;
    private readonly OrderComparer _comparer;

    public OrderedList(IDictionary<TKey, TValue> dictionary, bool sorted = false)
    {
        _sorted = sorted;

        if (dictionary == null) dictionary = new Dictionary<TKey, TValue>();

        if (_sorted)
        {
            _internalList = new SortedList<TKey, TValue>(dictionary);
        }
        else
        {
            _order = new Dictionary<TKey, int>();
            _comparer = new OrderComparer(ref _order);
            _internalList = new SortedList<TKey, TValue>(_comparer);
            //keep prder of the IDictionary
            foreach (var kvp in dictionary)
            {
                Add(kvp);
            }
        }
    }

    public OrderedList(bool sorted = false)
        : this(null, sorted)
    {
    }

    private class OrderComparer : Comparer<TKey>
    {
        public Dictionary<TKey, int> Order { get; set; }

        public OrderComparer(ref Dictionary<TKey, int> order)
        {
            Order = order;
        }

        public override int Compare(TKey x, TKey y)
        {
            var xo = Order[x];
            var yo = Order[y];
            return xo.CompareTo(yo);
        }
    }

    private void ReOrder()
    {
        var i = 0;
        _order = _order.OrderBy(kvp => kvp.Value).ToDictionary(kvp => kvp.Key, kvp => i++);
        _comparer.Order = _order;
        _lastOrder = _order.Values.Max() + 1;
    }

    public void Add(TKey key, TValue value)
    {
        if (!_sorted)
        {
            _order.Add(key, _lastOrder);
            _lastOrder++;
            //very rare event
            if (_lastOrder == int.MaxValue) ReOrder();
        }

        _internalList.Add(key, value);
    }

    public bool Remove(TKey key)
    {
        var result = _internalList.Remove(key);
        if (!_sorted) _order.Remove(key);
        return result;
    }

    //Other IDictionary<> + IDictionary members implementation wrapping around _internalList
    //...
}

InformationsquelleAutor der Antwort V.B.

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.