C# 中 SortedList 和 SortedDictionary 的区别

2025年3月17日 | 阅读 7 分钟

在本文中，您将了解 C# 中 SortedList 和 SortedDictionary 之间的区别。但在讨论它们的区别之前，您必须了解 SortedList 和 SortedDictionary。

什么是 SortedList？

C# 集合类 SortedList 表示键/值对的集合，其中条目按键排序。它属于 System.Collections 命名空间。SortedList 使用动态数组来保存其元素。元素根据其键保持排序。二分查找 用于基于键的高效检索元素。

1. 关键特性

排序顺序

根据键保持元素的排序顺序是 SortedList 的主要特性。
二分查找算法可以用于有效搜索。

基于数组的结构

SortedList 内部将键/值对存储在数组中。
必要时，此数组的大小会动态更改。

2. 性能

通过索引快速访问

它类似于常规数组，允许通过索引进行元素的快速访问。
元素通过索引检索的时间复杂度为O(1)。

插入和删除较慢

与 Dictionary 或 SortedDictionary 等其他数据结构相比，插入和删除可能较慢，因为维护排序顺序可能需要移动元素。

3. 内存开销

较低的内存开销

通常，由于其简单的基于数组的实现，它比其他排序数据结构具有更低的内存开销。

4. 用例

频繁的基于索引的访问

它非常适合需要频繁基于索引访问元素的场景。

相对静态的集合

它非常适合集合主要为静态的场景，因为动态调整大小可能会对性能产生负面影响。

示例

让我们通过一个例子来说明 C# 中的 SortedList。

using System;
using System.Collections;
class Program
{
 static void Main()
 {
 // Create a new SortedList
 SortedList sortedList = new SortedList();
 // Add elements to the SortedList
 sortedList.Add(3, "Three");
 sortedList.Add(1, "One");
 sortedList.Add(2, "Two");
 sortedList.Add(4, "Four");
 // Display the elements in sorted order
 Console.WriteLine("Sorted List Elements:");
 foreach (DictionaryEntry entry in sortedList)
 {
 Console.WriteLine($"Key: {entry.Key}, Value: {entry.Value}");
 }
 // Accessing elements by key
 int keyToFind = 2;
 if (sortedList.ContainsKey(keyToFind))
 {
 Console.WriteLine($"Value for Key {keyToFind}: {sortedList[keyToFind]}");
 }
 else
 {
 Console.WriteLine($"Key {keyToFind} not found.");
 }
 }
}

输出

Sorted List Elements:
Key: 1, Value: One
Key: 2, Value: Two
Key: 3, Value: Three
Key: 4, Value: Four
Value for Key 2: Two

说明

1. 命名空间和类声明

代码开头声明了一个命名空间 (System) 和一个类 (Program)。

2. Main 方法

Main 方法是程序的入口点。

3. 创建 SortedList

使用 new SortedList()，创建了一个名为 sortedList 的新 SortedList 实例。

4. 添加元素

使用 Add 方法，将键值对添加到 SortedList。

字符串是值，整数是键。

5. 显示排序后的元素

然后，程序进入一个循环，遍历 SortedList 的元素。

使用以 DictionaryEntry 作为循环变量类型的 foreach 循环访问键值对。

根据键，值和键在控制台上以特定顺序排列。

6. 使用键访问元素

该程序演示了如何使用索引器 ([]) 语法和 ContainsKey 方法按键访问元素。

在这种情况下，它会检查键 2 是否存在于 SortedList 中。

如果找到该键，它将打印相应的值；否则，它将打印一条消息，指示未找到。

7. 输出

控制台输出显示了排序后的键值对以及使用特定键访问元素的结果。

此代码提供了一个使用 C# 中 SortedList 存储、检索和显示排序键值对的基本示例。SortedList 类根据键自动维护排序顺序。

什么是 SortedDictionary？

C# 集合类 SortedDictionary 表示键/值对的集合，其中键对元素进行排序。它属于 System.Collections.Generic 命名空间。SortedDictionary 将键/值对存储在红黑树（一种自平衡二叉搜索树）中。该树结构具有对数时间复杂度，可确保有效的搜索、插入和删除操作。

1. 关键特性

排序顺序

SortedDictionary 的基本特性是其元素根据键保持排序。
红黑树在操作过程中会自动平衡自身，以保持高效的搜索时间。

平衡的树结构

红黑树结构通过确保树的高度保持对数级别，最大化了搜索、插入和删除操作。

2. 性能

快速插入和删除

SortedDictionary 的平衡红黑树允许快速插入和删除操作。
操作的时间复杂度为O(log n)。

通过索引访问较慢

由于需要进行树遍历，因此按索引访问元素比 SortedList 访问要慢。

3. 内存开销

较高的内存开销

通常，由于树结构和额外的节点，它比 SortedList 具有更高的内存开销。

4. 用例

频繁的插入和删除

它非常适合预计会有频繁插入和删除的场景。

动态集合

它适用于集合会频繁更改的场景。

示例

让我们通过一个例子来说明 C# 中的 SortedDictionary。

using System;
using System.Collections.Generic;
class Program
{
 static void Main()
 {
 // Create a new SortedDictionary
 SortedDictionary<int, string> sortedDictionary = new SortedDictionary<int, string>();
 // Add elements to the SortedDictionary
 sortedDictionary.Add(3, "Three");
 sortedDictionary.Add(1, "One");
 sortedDictionary.Add(2, "Two");
 sortedDictionary.Add(4, "Four");
 // Display the elements in sorted order
 Console.WriteLine("Sorted Dictionary Elements:");
 foreach (var kvp in sortedDictionary)
 {
 Console.WriteLine($"Key: {kvp.Key}, Value: {kvp.Value}");
 }
 }
}

输出

Sorted Dictionary Elements:
Key: 1, Value: One
Key: 2, Value: Two
Key: 3, Value: Three
Key: 4, Value: Four

说明

1. 类声明和命名空间

Program 类在代码开头声明。

它包含 System 和 System.Collections.Generic 命名空间。

2. Main 方法

程序的入口点是 Main 方法。

3. 创建 SortedDictionary

SortedDictionary<int, string> 类被生成为新实例。

SortedDictionary 存储类型为 string 的值和类型为 int 的键的键值对。

4. 向 SortedDictionary 添加元素

使用 Add 方法，将键值对添加到 SortedDictionary。

在此示例中，值为字符串（"Three", "One", "Two", "Four"），键为数字（3, 1, 2, 4）。

5. 显示元素

代码使用 foreach 循环遍历 SortedDictionary。

访问 SortedDictionary 中每个键值对(KeyValuePair<int, string>) 的 Key 和 Value 属性，以按排序顺序显示键值对。

6. 输出

该程序生成排序的键值对列表，显示键及其对应的值。

此代码展示了如何在 C# 中创建 SortedDictionary 实例、添加元素以及遍历排序的键值对。SortedDictionary 根据键自动维护排序顺序。