前言

最近需要在C#中实现一个功能
有一个容器，该容器能自动对里面的元素进行排序，类似C++的优先队列，也就是堆。
但是查询了C#提供的一些容器，只有 SortedSet 和我们的需求很符合。

SortedSet

其实就是一个可以自动排序的容器

我们在Unity下使用看看

C#自带类型

using System.Collections;
using System.Collections.Generic;
using UnityEngine;public class SortedSetTest : MonoBehaviour
{private void Awake(){SortedSet<int> ssi = new SortedSet<int>();ssi.Add(10);ssi.Add(1);ssi.Add(5);ssi.Add(-1);foreach (var item in ssi){print(item);}}
}

自定义类

public class Student : IComparable<Student>
{private int id;public Student(int id_in){id = id_in;}public int CompareTo(Student other){return id.CompareTo(other.id);}public override string ToString(){return $"Student ID {id}";}
}

using System.Collections;
using System.Collections.Generic;
using UnityEngine;public class SortedSetTest : MonoBehaviour
{private void Awake(){SortedSet<Student> sss = new SortedSet<Student>();sss.Add(new Student(10));sss.Add(new Student(1));sss.Add(new Student(5));sss.Add(new Student(-1));foreach (var item in sss){print(item);}}
}

SortedSet权值重复

我们能看出来它可以自动进行排序

但是如果权值重复了该怎么办？我们来试试看

using System.Collections;
using System.Collections.Generic;
using UnityEngine;public class SortedSetTest : MonoBehaviour
{private void Awake(){SortedSet<int> ssi = new SortedSet<int>();ssi.Add(10);ssi.Add(1);ssi.Add(1);ssi.Add(-1);foreach (var item in ssi){print(item);}}
}

我们发现相同的 1 并没有被加入到集合中，这也算是 SortedSet 的特性，毕竟是 Set 嘛。

需求

但是我们现在需要的是重复的权值也可以保存下来，并且进行排序。那该怎么办呢？
这里我并没有找到C#自带的符合需求的容器（C++有优先队列），所以我们这里自定义一个容器来实现。

自定义容器 – MultiplySortedSet

多说无益，直接上代码。

using System;
using System.Collections;
using System.Collections.Generic;namespace Util
{//排序方法public enum MultiplySortedType{Ascending,      //升序Descending,     //降序}public class MultiplySortedSet<T> : IEnumerable<T> where T : IComparable<T>{private SortedSet<KeyValuePair<T, Guid>> _elements;private Dictionary<T, Guid> _elementIds;public MultiplySortedSet(IComparer<KeyValuePair<T, Guid>> comparer = null){//默认为升序if(comparer == null){comparer = new ComparerAscending();}_elements = new SortedSet<KeyValuePair<T, Guid>>(comparer);_elementIds = new Dictionary<T, Guid>();}public MultiplySortedSet(MultiplySortedType sortedType){IComparer<KeyValuePair<T, Guid>> comparer = null;switch (sortedType){case MultiplySortedType.Ascending:comparer = new ComparerAscending();break;case MultiplySortedType.Descending:comparer = new ComparerDescending();break;}_elements = new SortedSet<KeyValuePair<T, Guid>>(comparer);_elementIds = new Dictionary<T, Guid>();}public void Add(T element){Guid guid = Guid.NewGuid();_elements.Add(new KeyValuePair<T, Guid>(element, guid));_elementIds[element] = guid;}public void Remove(T element){//如果Ids存在，则说明_elements里面肯定有该元素//RemoveWhere是为了删除单一元素//因为不同T对象的Compare可能相同，但是Guid肯定不同if (_elementIds.ContainsKey(element)){_elements.RemoveWhere(x => x.Key.CompareTo(element) == 0 && x.Value.CompareTo(_elementIds[element]) == 0);_elementIds.Remove(element);}}public bool Contains(T element){return _elementIds.ContainsKey(element);}public int Count{get { return _elements.Count; }}public IEnumerator<T> GetEnumerator(){foreach (var element in _elements){yield return element.Key;}}IEnumerator IEnumerable.GetEnumerator(){return GetEnumerator();}private class ComparerAscending : IComparer<KeyValuePair<T, Guid>>{public int Compare(KeyValuePair<T, Guid> x, KeyValuePair<T, Guid> y){//先调用T的Compare，如果相等就比较Guidint result = x.Key.CompareTo(y.Key);if (result == 0){result = x.Value.CompareTo(y.Value);}return result;}}private class ComparerDescending : IComparer<KeyValuePair<T, Guid>>{public int Compare(KeyValuePair<T, Guid> x, KeyValuePair<T, Guid> y){//先调用T的Compare，如果相等就比较Guidint result = y.Key.CompareTo(x.Key);if (result == 0){result = x.Value.CompareTo(y.Value);}return result;}}}
}

核心实现思路

其实核心思路就一点，多做一层封装，当对象权重相等时，比较另外一个值。

1. 首先 SortedSet 不可以存储相同权重，所以我们这里使用 KeyValuePair 来封装一层。

Key为排序的对象，这里就拿泛型T替代。
Value存在的意义就是，当某些T对象权重相等时，拿Value的值来作比较。也就是说每一个相等权重的对象T的Value一定要不一样。所以这里Value可以拿System.Guid来做。

2. 自定义一个 Comparer ，如果Key值相等，那么就比较Value值。

MultiplySortedSet 使用

C#自带类型

using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using Victor_Util;public class Test : MonoBehaviour
{private void Awake(){MultiplySortedSet<int> vs = new MultiplySortedSet<int>();vs.Add(9);vs.Add(1);vs.Add(1);vs.Add(1);vs.Add(-5);vs.Add(100);foreach (var item in vs){print(item);}}
}

自定义类

using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using Victor_Util;public class Test : MonoBehaviour
{private void Awake(){MultiplySortedSet<Student> vs2 = new MultiplySortedSet<Student>();vs2.Add(new Student(9));vs2.Add(new Student(1));vs2.Add(new Student(1));vs2.Add(new Student(1));vs2.Add(new Student(-5));vs2.Add(new Student(100));foreach (var item in vs2){print(item);}}
}