c# - 値でソートされたキーと値のペアのリストを維持する最も簡単な方法は何ですか?

Question

各キーはリスト内で一意です。新しいキーと値のペアが到着すると、ペアは値の昇順でリストに挿入されます (キーが既に存在する場合は、値を更新します)。

挿入ごとにリストをソートすることは避けてください。

Answer 1

この動作で組み込みのコンポーネントを取得することはありません。標準ではありません。私は、これらの競合する行動が必要な理由と時期を検討しています。事実上、あなたは代替キーを見ています。リンクリストのいくつかを書くのではなく、頭のてっぺんから、SortedListでその値の部分を調べ、Dictionaryでキーを調べます。例えば

CustomerIDとSortKeyのディクショナリ、およびSortKeyとvalueのSortedList。

両方を維持することは、必要なときに必要な順序で値のリストを返すよりもコストがかかるという根拠に基づいて、それを避けようとします。

Answer 2

SortedDictionary または SortedList をお勧めします

MSDN によると:

SortedList は、SortedDictionary よりも少ないメモリを使用します。

SortedDictionary は、ソートされていないデータの挿入および削除操作が高速です。SortedList の O(n) とは対照的に、O(log n) です。

更新：コメントの後

たとえば、辞書を使用するために、自分で値を注文する必要があります

    var dictionary = new Dictionary<int, string>{ {1, "Z"}, {2, "A"}};
    IOrderedEnumerable<KeyValuePair<int, string>> orderedEnumerable = dictionary.OrderBy(d => d.Value);

Answer 3

すべての列挙の項目の並べ替えが許容される場合は、Dictionary<TKey, TValue>を使用して、列挙時にキーと値のペアを値で並べ替えることができます。

var dict = new Dictionary<MyKey, MyValue>();

// insertion (updates value when key already exists)
dict[key] = value;

// enumeration (ordered by value)
foreach (var keyValuePair in dict.OrderBy(kvp => kvp.Value))
{
    ...
}

Answer 4

次のようなアドホック クラスを作成します (完全にはテストされていません)。

public class DictionarySortedByValue<TKey, TValue> : IDictionary<TKey, TValue>
{
    class ValueWrapper : IComparable, IComparable<ValueWrapper>
    {
        public TKey Key { get; private set; }
        public TValue Value { get; private set; }

        public ValueWrapper(TKey k, TValue v)
        {
            this.Key = k;
            this.Value = v;
        }
        public int CompareTo(object obj)
        {
            if (!(obj is ValueWrapper))
                throw new ArgumentException("obj is not a ValueWrapper type object");
            return this.CompareTo(obj as ValueWrapper);
        }
        public int CompareTo(ValueWrapper other)
        {
            int c = Comparer<TValue>.Default.Compare(this.Value, other.Value);
            if (c == 0)
                c = Comparer<TKey>.Default.Compare(this.Key, other.Key);
            return c;
        }
    }

    private SortedSet<ValueWrapper> orderedElements;
    private SortedDictionary<TKey, TValue> innerDict;

    public DictionarySortedByValue()
    {
        this.orderedElements = new SortedSet<ValueWrapper>();
        this.innerDict = new SortedDictionary<TKey, TValue>();
    }

    public void Add(TKey key, TValue value)
    {
        var wrap = new ValueWrapper(key, value);
        this.innerDict.Add(key, value);
        this.orderedElements.Add(wrap);
    }

    public bool ContainsKey(TKey key)
    {
        return this.innerDict.ContainsKey(key);
    }

    public ICollection<TKey> Keys
    {
        get { return this.innerDict.Keys; }
    }

    public bool Remove(TKey key)
    {
        TValue val;
        if (this.TryGetValue(key, out val))
        {
            var wrap = new ValueWrapper(key, val);
            this.orderedElements.Remove(wrap);
            this.innerDict.Remove(key);
            return true;
        }
        return false;
    }

    public bool TryGetValue(TKey key, out TValue value)
    {
        return this.innerDict.TryGetValue(key, out value);
    }

    public ICollection<TValue> Values
    {
        get { return this.innerDict.Values; }
    }

    public TValue this[TKey key]
    {
        get
        {
            return this.innerDict[key];
        }
        set
        {
            bool removed = this.Remove(key);
            this.Add(key, value);
        }
    }

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

    public void Clear()
    {
        this.innerDict.Clear();
        this.orderedElements.Clear();
    }

    public bool Contains(KeyValuePair<TKey, TValue> item)
    {
        var wrap = new ValueWrapper(item.Key,item.Value);
        return this.orderedElements.Contains(wrap);
    }

    public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
    {
        this.innerDict.CopyTo(array, arrayIndex);
    }

    public int Count
    {
        get { return this.innerDict.Count; }
    }

    public bool IsReadOnly
    {
        get { return false; }
    }

    public bool Remove(KeyValuePair<TKey, TValue> item)
    {
        if (this.Contains(item))
            return this.Remove(item.Key);
        return false;
    }

    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
    {
        foreach (var el in this.orderedElements)
            yield return new KeyValuePair<TKey, TValue>(el.Key, el.Value);
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }
}

ノート ：

• TKey型が IComparable を実装 することも必要です。
• 投稿されたコードは、TKey と TValue の既定の Comparer のみを使用しますが、別のコンストラクターを介してカスタムのものを渡すことができます。