C# 中的通用循环缓冲区

• 下载源代码 - 14.4 KB

引言

Microsoft .NET 提供了几个基本的通用数据结构，例如 Stack<T>、Queue<T> 和 LinkedList<T>，但没有循环缓冲区或 DEque（“双端”队列）。这个类旨在填补这一空白。

概念化这个混乱的局面

循环缓冲区允许从容器的前端和后端快速地推送和弹出元素。这些操作是 O(1)，而其他插入和删除操作是 O(n)，假设没有重新分配内存。

这使得缓冲区适合用作通用的堆栈或队列。尽管 Microsoft 提供了堆栈或队列，但使用此类的一个原因是，此类允许通过索引访问，并完全实现了 IList<T>。

使用这个烂摊子

该类的使用相对简单。大多数 IList<T> 和 ICollection<T> 接口成员都是显式的，因为它们的大多数操作是 O(n) 而不是 O(1)。这意味着您需要将对象转换为适当的接口才能完全访问其列表或集合成员。这是为了防止随意滥用该数据结构 - 它主要不打算用作列表类，但可以用作列表类。访问修饰符反映了这一点。

主要 API 包括 PushBack()/PopBack() 和 PushFront()/PopFront()，它们分别从容器的后端或前端添加和删除项目。还有一些更标准的列表/集合成员，例如 Contains()、IndexOf()、this[] 和 Clear()

以下是来自演示/测试代码的摘录

Console.WriteLine("Adding 10 items");
for (var i = 0; i < 10; ++i)
    list.PushBack(i + 1);

Console.Write("Enumerating "+ list.Count+" items:");
foreach (var item in list)
    Console.Write(" " + item.ToString());
Console.WriteLine();

Console.WriteLine("Removing 1 item");
list.PopFront();

所有代码都有文档注释，并且非常简单明了。

关注点

我实在无法忍受实现 Insert()，尤其是在循环缓冲区上，如果存在错误，很可能是在 Insert() 代码中。我不确定是否可以简化该例程。有很多边界情况。

历史

• 2020 年 2 月 6 日 - 初始提交