在.Net BCL中有一个类似于列表的集合数据结构,具有最大容量,比如说配置为100个项目,当添加项目101时,从集合中弹出/删除原始的第一个项目,从而确保项目计数永远不会超过100.
我正在使用.net 3.5
提前致谢
Jar*_*Par 19
没有这样的集合可用,但一个很容易写.执行此操作的最佳方法是创建一个封装现有集合类型的新集合类型.
例如
public class FixedSizeList<T> : IList<T> {
private List<T> _list = new List<T>();
private int _capacity = 100;
public void Add(T value) {
_list.Add(value);
while ( _list.Count > _capacity ) {
_list.RemoveAt(0);
}
}
// Rest omitted for brevity
}
一些答案表明继承是一种机制.这肯定不是一个好的途径,特别是如果你从一个通用集合派生.这些集合不是为了继承而设计的,并且很容易意外地绕过因添加或删除方法而导致的容量检查.
主要原因是这些方法不是虚拟的,因此无法覆盖它们.您将被迫声明具有不同名称的Add方法(从而使用户感到困惑)或使用新语法重新声明Add.后者是非常不安全的,因为只要将类的实例传递给基类型的引用,就不会调用所有方法,并且列表可以超过容量.
编辑
正如评论部分讨论所指出的那样,实施List<T>并不是最好的方法.原因是它在某些情况下违反了替代原则.显示问题的最简单方法是想象我的实现是否传递给以下方法.此代码应该通过任何IList<T>实现,但如果列表处于容量状态,则会失败.
public void Example<T>(IList<T> list, T value) {
var count = list.Count;
list.Add(value);
var addedValue = list[count];
}
可以为指定集合有效实现的唯一集合接口是IEnumerable<T>.我把我的实现留在那里作为例子.但请参阅ShuggyCoUk的IEnumerable<T>实施答案:
你所描述的是一个循环缓冲区.我偶尔使用这些,最近将一些旧的代码移植到通用的C#类(附加)中.此代码是SharpNeat V2开发的一部分.
这在添加和删除操作时具有O(1)性能,而封装List的解决方案是O(n).这是因为删除列表中的第0个项会导致所有其他项目被混洗以填补空白.
using System;
using System.Collections.Generic;
using System.Text;
namespace SharpNeat.Utility
{
///
/// This is a generic circular buffer of items of type T. A circular buffer must be assigned
/// a capacity at construction time. Items can be enqueued indefintely, but when the buffer's
/// capacity is reached the oldest values in the buffer are overwritten, thus the buffer is best
/// thought of as a circular array or buffer.
///
public class CircularBuffer
{
///
/// Internal array that stores the circular buffer's values.
///
protected T[] _buff;
///
/// The index of the previously enqueued item. -1 if buffer is empty.
///
protected int _headIdx;
///
/// The index of the next item to be dequeued. -1 if buffer is empty.
///
protected int _tailIdx;
#region Constructors
///
/// Constructs a circular buffer with the specified capacity.
///
///
public CircularBuffer(int capacity)
{
_buff = new T[capacity];
_headIdx = _tailIdx = -1;
}
#endregion
#region Properties
///
/// Gets the number of items in the buffer. Returns the buffer's capacity
/// if it is full.
///
public int Length
{
get
{
if(_headIdx == -1)
return 0;
if(_headIdx > _tailIdx)
return (_headIdx - _tailIdx) + 1;
if(_tailIdx > _headIdx)
return (_buff.Length - _tailIdx) + _headIdx + 1;
return 1;
}
}
#endregion
#region Public Methods
///
/// Clear the buffer.
///
public virtual void Clear()
{
_headIdx = _tailIdx = -1;
}
///
/// Enqueue a new item. This overwrites the oldest item in the buffer if the buffer
/// has reached capacity.
///
///
public virtual void Enqueue(T item)
{
if(_headIdx == -1)
{ // buffer is currently empty.
_headIdx = _tailIdx = 0;
_buff[0] = item;
return;
}
// Determine the index to write to.
if(++_headIdx == _buff.Length)
{ // Wrap around.
_headIdx = 0;
}
if(_headIdx == _tailIdx)
{ // Buffer overflow. Increment tailIdx.
if(++_tailIdx == _buff.Length)
{ // Wrap around.
_tailIdx=0;
}
_buff[_headIdx] = item;
return;
}
_buff[_headIdx] = item;
return;
}
///
/// Remove the oldest item from the back end of the buffer and return it.
///
///
public virtual T Dequeue()
{
if(_tailIdx == -1)
{ // buffer is currently empty.
throw new InvalidOperationException("buffer is empty.");
}
T item = _buff[_tailIdx];
if(_tailIdx == _headIdx)
{ // The buffer is now empty.
_headIdx=_tailIdx=-1;
return item;
}
if(++_tailIdx == _buff.Length)
{ // Wrap around.
_tailIdx = 0;
}
return item;
}
///
/// Pop the most recently added item from the front end of the buffer and return it.
///
///
public virtual T Pop()
{
if(_tailIdx == -1)
{ // buffer is currently empty.
throw new InvalidOperationException("buffer is empty.");
}
T item = _buff[_headIdx];
if(_tailIdx == _headIdx)
{ // The buffer is now empty.
_headIdx = _tailIdx =- 1;
return item;
}
if(--_headIdx==-1)
{ // Wrap around.
_headIdx=_buff.Length-1;
}
return item;
}
#endregion
}
}
一个非常简单的滚动窗口
public class RollingWindow<T> : IEnumerable<T>
{
private readonly T[] data;
private int head;
private int nextInsert = 0;
public RollingWindow(int size)
{
if (size < 1)
throw new Exception();
this.data = new T[size];
this.head = -size;
}
public void Add(T t)
{
data[nextInsert] = t;
nextInsert = (nextInsert + 1) % data.Length;
if (head < 0)
head++;
}
public IEnumerator<T> GetEnumerator()
{
if (head < 0)
{
for (int i = 0; i < nextInsert; i++)
yield return data[i];
}
else
{
for(int i = 0; i < data.Length; i++)
yield return data[(nextInsert + i) % data.Length];
}
}
System.Collections.IEnumerator
System.Collections.IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
}