【c# .net】排序字典（SortedDictionary）
排序字典（SortedDictionary）
1.简介
SortedDictionary<TKey,TValue> 类是 检索运算复杂度为 O(log n) 的二叉搜索树 ，其中 n 是字典中的元素数。
它与 SortedList<T> 泛型类相似。这两个类具有相似的对象模型，并且都具有 O(log n) 的检索运算复杂度。
这两个类的区别在于内存的使用以及插入和移除元素的速度：
1）SortedList 使用的内存比 SortedDictionary 少。
2）SortedDictionary 可对未排序的数据执行更快的插入和移除操作：它的时间复杂度为 O(log n)，而SortedList 为 O(n)。
3）如果使用排序数据一次性填充列表，则 SortedList 比 SortedDictionary 快。
2.特性介绍
1) key(键) 是 唯一 的， 不可重复 ，同时 key 区分大小写 ；
2) 只能通过 key(键) 查询对应 的 value(值) ，因为元素的存储与顺序无关，同时 不能在指定位置插入元素 ，增减元素都会根据规则 自动排序
3） key(键) 不能为 null ，但 value(值) 可以 。
4）容量是字典最大包含的元素数，会根据元素增减而 动态调整容量 。
SortedDictionary<TKey,TValue> 类的方法和属性
1）下表列出了 SortedDictionary<TKey,TValue> 类的一些常用的 属性 :
| 属性 | 描述 |
|---|---|
| IComparer Comparer { get; } | 获取元素的排序类型 |
| int Count { get; } | 获取键/值对的数目 |
| TValue item[TKey key] { get; set; } | 获取或设置指定键的值 |
| KeyCollection Keys { get; } | 获取键的集合 |
| ValueCollection Values { get; } | 获取值的集合 |
2）下表列出了 SortedDictionary<TKey,TValue> 类的一些常用的 方法 ：
| 方法 | 描述 |
|---|---|
| void Add (TKey key, TValue value); | 添加指定键值对元素 |
| void Clear (); | 移除所有元素 |
| bool ContainsKey (TKey key); | 判断是否包含指定键 |
| bool ContainsValue (TValue value); | 判断是否包含指定值 |
| bool Remove (TKey key); | 移除包含指定键的元素并返回布尔值表示执行情况 |
| bool TryGetValue (TKey key, out TValue value); | 判断是否包含指定键，如果有，返回它的值 |
| void CopyTo (KeyValuePair[] array, int index); | 复制所有元素到 KeyValuePair 数组的指定索引处 |
代码演示
注意：为了方便阅读，以下将代码拆分为多段进行演示，实际运行可以把代码直接拼接起来
using System;
using System.Collections;
using System.Collections.Generic;
namespace SortedDictionaryTest
class Program
static void Main(string[] args)
SortedDictionaryTest();
Console.ReadKey();
//为了方便后续验证结果，先封装两个简单方法
/// <summary>
/// 分隔线
/// </summary>
static void 分割线()
Console.WriteLine("\n ------------------------------------------- \n");
/// <summary>
/// 遍历 SortedDictionary 中的所有元素
/// </summary>
static void FSDictionary<K, V>(SortedDictionary<K, V> sdictionary)
Console.WriteLine(" 元素：");
foreach (var item in sdictionary)
Console.WriteLine(" Key = {0}, Value = {1}", item.Key, item.Value);
分割线();
static void SortedDictionaryTest()
//new 时必须为泛型，可以指定比较器（如果你知道怎么使用比较器的话），不可指定容量
SortedDictionary<int, string> sd = new SortedDictionary<int, string>();
sd.Add(9, "九");
sd.Add(8, "八");
sd.Add(7, "七");
sd.Add(6, "六");
sd.Add(1, "一");
sd.Add(5, "五");
sd.Add(3, "三");
sd.Add(2, "二");
Console.WriteLine("\n 遍历排序字典: ");
FSDictionary(sd);
Console.WriteLine("\n 获取元素的排序类型: \n {0}", sd.Comparer);
//Count 指的是字典的实际元素个数而不是指容量
Console.WriteLine("\n 获取键/值对的数目: \n {0}", sd.Count);
//item 可以为 key 赋值，如果已经赋值过，则修改它的值，如果 key 不存在则会报错
Console.WriteLine("\n 获取或设置指定键的值: \n item[6]:{0}", sd[6]);
Console.WriteLine("\n 获取键的集合: Keys ");
foreach (var item in sd.Keys) Console.Write(" " + item);
分割线();
Console.WriteLine("\n 获取值的集合: Values ");
foreach (var item in sd.Values) Console.Write(" " + item);
分割线();
运行结果：
Console.WriteLine("\n 1.添加指定键值对元素: 10, 十\n");
//无法添加带有相同 Key 的元素，运行时会报错
//sd.Add(2, "二");
sd.Add(10, "十");
FSDictionary(sd);
Console.WriteLine("\n 2.判断是否包含指定键: 8：{0}\n", sd.ContainsKey(8));
分割线();
Console.WriteLine("\n 3.判断是否包含指定值: 八：{0}\n", sd.ContainsValue("八"));
分割线();
运行结果：
Console.WriteLine("\n 4.移除元素并返回布尔值: 10：{0}\n", sd.Remove(10));
FSDictionary(sd);
Console.WriteLine("\n 5.判断是否包含指定键，如果有，返回它的值: \n");
//如果没有该键，则返回该类型的默认值，不会报错
string values;
Console.WriteLine(" {0},{1}",sd.TryGetValue(10,out values),values);
Console.WriteLine("\n 6.复制所有元素到 KeyValuePair 的指定索引处: \n");
////复制时，需要注意容器数组长度，长度不足会越界报错,且数据类型必须一致
KeyValuePair<int, string>[] keyValue = new KeyValuePair<int, string>[sd.Count*2];