tương đương với từ điển được sắp xếp cho phép các phím trùng lặp

Question

Tôi cần một cấu trúc dữ liệu có thể sắp xếp các đối tượng bằng các phím nổi mà chúng được liên kết với, thấp nhất trước tiên. Vấn đề là các phím đại diện cho chi phí vì vậy thường có bản sao, tôi không quan tâm về điều này bởi vì nếu hai có cùng một chi phí tôi sẽ chỉ lấy đầu tiên vì nó làm cho không có sự khác biệt, vấn đề là trình biên dịch phàn nàn.

Có cấu trúc dữ liệu hoạt động theo cùng một cách nhưng cho phép các khóa trùng lặp không?

EDIT - Tôi vẫn cần các bản sao mặc dù bởi vì nếu một hóa ra là một ngõ cụt, tôi lấy tiếp theo (họ đang nút trong một tìm kiếm *)

vì vậy chỉ cần phải rõ ràng, nó cần cho phép các khóa trùng lặp được sắp xếp theo thứ tự.

Answer 1

Điều bạn đang tìm kiếm được gọi là heap hoặc priority queue. Tôi chắc chắn nếu bạn google, bạn sẽ tìm thấy một cho C#

Answer 2

Bạn vẫn có thể sử dụng từ điển. Bạn chỉ cần thay đổi loại giá trị thành bộ sưu tập chứ không phải là các mục đơn lẻ:

Dictionary<float, List<T>> 

Định nghĩa từ điển không cho phép khóa trùng lặp.

Answer 3

Bạn đang tìm kiếm Lookup. Tương tự như các giải pháp dựa trên từ điển khác được đề xuất, nó lưu trữ một IEnumerable dưới mỗi khóa để xử lý các bản sao.

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

Answer 4

Bạn viết:

tương đương với một cuốn từ điển cho phép khóa trùng lặp

Tôi cần một cấu trúc dữ liệu mà có thể sắp xếp các vật thể bằng các phím phao họ đang liên kết với, thấp nhất đầu tiên.

Từ điển không giữ các mục được sắp xếp theo các khóa, vì vậy cấu trúc bạn đang tìm kiếm thực sự không tương đương với Dictionary. Những gì bạn muốn là một cái gì đó tương tự như một SortedList hoặc SortedDictionary ngoại trừ việc nó sẽ cho phép các khóa trùng lặp.

Không có lớp nào tồn tại trong .NET. Tuy nhiên bạn có một vài lựa chọn:

• Sử dụng SortedDictionary<double, List<TValue>> nếu bạn muốn lưu trữ tất cả các giá trị liên quan cho một chìa khóa, ngay cả khi bạn thường chỉ cần là người đầu tiên. Khi chèn một khóa lần đầu tiên, hãy tạo danh sách mới và thêm giá trị vào danh sách. Khi chèn một khóa đã tồn tại, hãy tìm nạp danh sách và nối thêm giá trị vào danh sách.
• _{Chỉnh sửa của bạn có nghĩa là phương pháp này không áp dụng cho trường hợp của bạn.} Sử dụng SortedDictionary<double, TValue> và kiểm tra các mục trùng lặp trước khi chèn. Chỉ giá trị đầu tiên cho mỗi khóa sẽ được lưu trữ, vì vậy không giống như cách tiếp cận trên, bạn không thể truy cập giá trị thứ hai nào cả với phương pháp này.
• Tìm thư viện bộ sưu tập của bên thứ ba có lớp học thực hiện những gì bạn muốn.

liên quan

• What's the difference between SortedList and SortedDictionary?

Answer 5

gì bạn đang nói về là một túi . Sự khác biệt giữa một túi và đặt là các bộ là duy nhất trong khi túi cho phép trùng lặp. {a, b, c} là một tập hợp; {a, b, c, a} là một cái túi.

Lấy một bản sao của C5 Collections Library. Bạn muốn các lớp học HashBag<T> hoặc TreeBag<T>. Sự khác biệt là lưu trữ dữ liệu cơ bản trong một là một băm và một cây màu đỏ-đen trong khác. Bên ngoài, họ cư xử giống nhau. Hoặc là cung cấp cho bạn những gì bạn muốn.

Answer 6

Bạn có thể tạo lớp của riêng bạn mà xuất phát từ 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)); 
    } 
} 

Cách sử dụng trong một ứng dụng giao diện điều khiển:

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(); 
} 

sản xuất kết quả này:

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

Answer 7

Tôi đã trúng vấn đề này một số lần, và tôi luôn luôn sử dụng giấy phép công cộng (tức là miễn phí) Bộ sưu tập điện từ Win tellect (http://powercollections.codeplex.com). Họ có một OrderedMultiDictionary đó là chính xác những gì bạn đang tìm kiếm. Nó cho phép các khóa trùng lặp và nó cho phép bạn lặp qua tất cả các mục nhập khóa trùng lặp.

Answer 8

Bạn sẽ có thể sử dụng SortedDictionary với triển khai tùy chỉnh IComparer để tránh va chạm. Ví dụ:

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

Bạn có thể làm điều đó bằng cách ghi đè tính năng CompareTo fucntion. Khi bạn thêm một aelement vào một SortedDictionary, nó sử dụng CompareTo(), nếu kết quả là 0 trows một ngoại lệ, nhưng bạn có thể thay đổi hành vi so sánh thực hiện lớp quan trọng của bạn để trở về chỉ lớn hơn hoặc thấp hơn (1 hoặc -1)

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