Bộ sưu tập cặp khóa/giá trị chung trong đó giữ lại thứ tự chèn?

Question

Tôi đang tìm một cái gì đó như một từ điển < K, V > tuy nhiên với một đảm bảo rằng nó giữ trật tự chèn. Kể từ khi từ điển là một hashtable, tôi không nghĩ rằng nó.

Có bộ sưu tập chung cho việc này hay không hoặc tôi có cần sử dụng một trong các bộ sưu tập .NET 1.1 cũ không?

Answer 1

Không có. Tuy nhiên, System.Collections.Specialized.OrderedDictionary cần giải quyết hầu hết nhu cầu về nó.

CHỈNH SỬA: Một tùy chọn khác là biến tùy chọn này thành Chung. Tôi đã không thử nghiệm nó nhưng nó biên dịch (C# 6) và nên làm việc. Tuy nhiên, nó vẫn sẽ có những hạn chế tương tự mà Ondrej Petrzilka đề cập trong phần bình luận dưới đây.

public class OrderdDictionary<T, K> 
    { 
     public OrderedDictionary UnderlyingCollection { get; } = new OrderedDictionary(); 

     public K this[T key] 
     { 
      get 
      { 
       return (K)UnderlyingCollection[key]; 
      } 
      set 
      { 
       UnderlyingCollection[key] = value; 
      } 
     } 

     public K this[int index] 
     { 
      get 
      { 
       return (K)UnderlyingCollection[index]; 
      } 
      set 
      { 
       UnderlyingCollection[index] = value; 
      } 
     } 
     public ICollection<T> Keys => UnderlyingCollection.Keys.OfType<T>().ToList(); 
     public ICollection<K> Values => UnderlyingCollection.Values.OfType<K>().ToList(); 
     public bool IsReadOnly => UnderlyingCollection.IsReadOnly; 
     public int Count => UnderlyingCollection.Count; 
     public IDictionaryEnumerator GetEnumerator() => UnderlyingCollection.GetEnumerator(); 
     public void Insert(int index, T key, K value) => UnderlyingCollection.Insert(index, key, value); 
     public void RemoveAt(int index) => UnderlyingCollection.RemoveAt(index); 
     public bool Contains(T key) => UnderlyingCollection.Contains(key); 
     public void Add(T key, K value) => UnderlyingCollection.Add(key, value); 
     public void Clear() => UnderlyingCollection.Clear(); 
     public void Remove(T key) => UnderlyingCollection.Remove(key); 
     public void CopyTo(Array array, int index) => UnderlyingCollection.CopyTo(array, index); 
    } 

Answer 2

Vâng, bạn có thể sử dụng List<KeyValuePair<K,V>>, thứ sẽ giữ nguyên thứ tự ... tuy nhiên bạn sẽ mất chức năng tra cứu của từ điển. Tại sao bạn cần lệnh bảo tồn?

Answer 3

Có một lớp OrderedDictionary đó là một cuốn từ điển nhưng có thể được lập chỉ mục theo thứ tự chèn, nhưng nó không được generified. Hiện tại không có một cái mở rộng trong khuôn khổ .Net.

Tôi đã đọc ở đâu đó một lời nhận xét từ một ai đó trong nhóm Net mà nói rằng họ có thể thực hiện một phiên bản generified trong tương lai, nhưng nếu như vậy nó sẽ rất có thể được gọi là thay vì OrderedDictionary để làm cho hành vi của nó hơn hiển nhiên.

EDIT: tìm thấy báo giá. Đó là trên trang MSDN cho OrderedDictionary, do David M. Kean từ Microsoft:

Loại này thực sự bị đặt tên sai; nó không phải là một từ điển 'đặt hàng' như vậy, mà là một từ điển 'được lập chỉ mục'. Mặc dù, hôm nay không có phiên bản chung loại tương đương của loại này, nếu chúng ta thêm một cái trong tương lai, có khả năng chúng ta sẽ đặt tên như kiểu 'IndexedDictionary'.

Answer 4

Có triển khai chung trên code project đi kèm với số lượng hợp lý các trường hợp kiểm tra.

Tác giả đã chọn một cái tên khá buồn cười (KeyedList) khiến bạn khó tìm thấy nó.

Answer 5

Tôi biết bạn đang viết C#, nhưng Java có một lớp gọi là LinkedHashMap sử dụng LinkedList riêng để duy trì thứ tự chèn khóa. Nếu bạn không thể tìm thấy một giải pháp chung phù hợp, có lẽ đó sẽ là một khởi đầu để thực hiện của riêng bạn.

Answer 6

Thực sự là một cái chung chung và đã có từ đó .net 2.0. Nó được gọi là KeyedCollection<TKey, TItem>. Tuy nhiên, nó có hạn chế rằng nó muốn xây dựng các khóa từ các giá trị, do đó, nó không phải là một bộ sưu tập cặp khóa/giá trị chung.

Nếu bạn cần nó như là một IDictionary<TKey, TItem>, nó có thuộc tính .Dictionary.

Một vấn đề hơi nhỏ mà tôi có với nó là nó là một lớp trừu tượng và bạn phải phân lớp nó và thực hiện:

protected abstract TKey GetKeyForItem(TItem item) 

tôi chỉ muốn vượt qua một lambda vào constructor cho mục đích này , nhưng sau đó một lần nữa, tôi đoán một phương pháp ảo là hơi nhanh hơn một lambda (bất kỳ ý kiến ​​về đánh giá này).

Answer 7

Code:

//A SortedDictionary is sorted on the key (not value) 
System.Collections.Generic.SortedDictionary<string, string> testSortDic = new SortedDictionary<string, string>(); 

//Add some values with the keys out of order 
testSortDic.Add("key5", "value 1"); 
testSortDic.Add("key3", "value 2"); 
testSortDic.Add("key2", "value 3"); 
testSortDic.Add("key4", "value 4"); 
testSortDic.Add("key1", "value 5"); 

//Display the elements. 
foreach (KeyValuePair<string, string> kvp in testSortDic) 
{ 
    Console.WriteLine("Key = {0}, value = {1}", kvp.Key, kvp.Value); 
} 

Output:

Key = key1, value = value 5 
Key = key2, value = value 3 
Key = key3, value = value 2 
Key = key4, value = value 4 
Key = key5, value = value 1  

Answer 8

Một tùy chọn khác cho một cặp/Giá trị Generic chính là bảo tồn chèn là sử dụng cái gì đó như:

Queue<KeyValuePair<string, string>> 

Đây sẽ là một danh sách đã được bảo đảm. Bạn có thể en-queue và dequeue trong một phe mệnh lệnh tương tự như Add/Remove của từ điển trái ngược với việc thay đổi kích thước một Array. Nó thường có thể phục vụ như là một nền tảng trung gian giữa một mảng không được định lại kích thước (bằng cách chèn) và một danh sách tự động sắp xếp thứ tự (bằng cách chèn).

Answer 9

Nếu bạn cần độ phức tạp liên tục của Add, Remove, ContainsKey và bảo quản trật tự, thì không có chung trong .NET Framework 4.5.

Nếu bạn đang okay với mã bên thứ 3, hãy nhìn vào kho lưu trữ của tôi (giấy phép MIT dễ dãi): https://github.com/OndrejPetrzilka/Rock.Collections

Có OrderedDictionary<K,V> bộ sưu tập:

mã nguồn

• dựa trên cổ điển Dictionary<K,V> (từ .NET Core)
• bảo tồn thứ tự chèn vào và cho phép chỉnh sửa thủ công
• tính năng đảo ngược liệt kê
• có phức tạp hoạt động tương tự như Dictionary<K,V>
• Add và Remove hoạt động chậm hơn ~ 20% so với Dictionary<K,V>
• tiêu thụ hơn 8 byte bộ nhớ cho mỗi mục

Answer 10

Dưới đây là trình bao bọc cho loại không chung loạiSystems.Collections.Specialized.OrderedDictionary .

Loại này sẽ trả về chuỗi khóa/giá trị/cặp trong thứ tự chèn, giống như băm Ruby 2.0.

Nó không yêu cầu phép thuật C# 6, phù hợp với IDictionary<TKey,TValue> (cũng có nghĩa là truy cập vào khóa không được gán ném ngoại lệ) và phải được tuần tự hóa.

Nó được đặt tên 'IndexedDictionary' cho mỗi ghi chú trên câu trả lời của Adrian.

YMMV.

using System; 
using System.Collections; 
using System.Collections.Generic; 
using System.Collections.Specialized; 
using System.Linq; 

/// <summary> 
/// A dictionary that maintains insertion ordering of keys. 
/// 
/// This is useful for emitting JSON where it is preferable to keep the key ordering 
/// for various human-friendlier reasons. 
/// 
/// There is no support to manually re-order keys or to access keys 
/// by index without using Keys/Values or the Enumerator (eg). 
/// </summary> 
[Serializable] 
public sealed class IndexedDictionary<TKey, TValue> : IDictionary<TKey, TValue> 
{ 
    // Non-generic version only in .NET 4.5 
    private readonly OrderedDictionary _backing = new OrderedDictionary(); 

    private IEnumerable<KeyValuePair<TKey, TValue>> KeyValuePairs 
    { 
     get 
     { 
      return _backing.OfType<DictionaryEntry>() 
       .Select(e => new KeyValuePair<TKey, TValue>((TKey)e.Key, (TValue)e.Value)); 
     } 
    } 

    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator() 
    { 
     return KeyValuePairs.GetEnumerator(); 
    } 

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

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

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

    public bool Contains(KeyValuePair<TKey, TValue> item) 
    { 
     return _backing.Contains(item.Key); 
    } 

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

    public bool Remove(KeyValuePair<TKey, TValue> item) 
    { 
     TValue value; 
     if (TryGetValue(item.Key, out value) 
      && Equals(value, item.Value)) 
     { 
      Remove(item.Key); 
      return true; 
     } 
     return false; 
    } 

    public int Count 
    { 
     get { return _backing.Count; } 
    } 

    public bool IsReadOnly 
    { 
     get { return _backing.IsReadOnly; } 
    } 

    public bool ContainsKey(TKey key) 
    { 
     return _backing.Contains(key); 
    } 

    public void Add(TKey key, TValue value) 
    { 
     _backing.Add(key, value); 
    } 

    public bool Remove(TKey key) 
    { 
     var result = _backing.Contains(key); 
     if (result) { 
      _backing.Remove(key); 
     } 
     return result; 
    } 

    public bool TryGetValue(TKey key, out TValue value) 
    { 
     object foundValue; 
     if ((foundValue = _backing[key]) != null 
      || _backing.Contains(key)) 
     { 
      // Either found with a non-null value, or contained value is null. 
      value = (TValue)foundValue; 
      return true; 
     } 
     value = default(TValue); 
     return false; 
    } 

    public TValue this[TKey key] 
    { 
     get 
     { 
      TValue value; 
      if (TryGetValue(key, out value)) 
       return value; 
      throw new KeyNotFoundException(); 
     } 
     set { _backing[key] = value; } 
    } 

    public ICollection<TKey> Keys 
    { 
     get { return _backing.Keys.OfType<TKey>().ToList(); } 
    } 

    public ICollection<TValue> Values 
    { 
     get { return _backing.Values.OfType<TValue>().ToList(); } 
    } 
}