c＃中的最大容量收集

在.Net BCL中有一个类似于列表的集合数据结构，具有最大容量，比如配置为100个项目，当添加项目101时，从集合中弹出/删除原始的第一个项目，从而确保项目计数永远不会超过100。

我正在使用.net 3.5

提前致谢

Answer 1

你所描述的是一个循环缓冲区。 我偶尔使用它们，最近将一些旧的代码移植到通用的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 } } 

Answer 2

没有这样的集合可用，但一个很容易写。 执行此操作的最佳方法是创建一个封装现有集合类型的新集合类型。

例如

 public class FixedSizeList : IList { private List _list = new List(); private int _capacity = 100; public void Add(T value) { _list.Add(value); while ( _list.Count > _capacity ) { _list.RemoveAt(0); } } // Rest omitted for brevity } 

一些答案表明inheritance是一种机制。 这肯定不是一个好的途径，特别是如果你是从一个通用集合派生的。 这些集合不是为了inheritance而设计的，并且很容易意外地绕过因添加或删除方法而导致的容量检查。

主要原因是这些方法不是虚拟的，因此无法覆盖它们。 您将被迫声明具有不同名称的Add方法（从而使用户感到困惑）或使用新语法重新声明Add。 后者是非常不安全的，因为只要将类的实例传递给基类型的引用，就不会调用所有方法，并且列表可以超过容量。

编辑

正如评论部分讨论所指出的那样，实现List并不是最好的方法。 原因是它在某些情况下违反了替代原则。 显示问题的最简单方法是想象我的实现是否传递给以下方法。 此代码应该传递给任何IList实现，但如果列表处于容量状态，则会失败。

 public void Example(IList list, T value) { var count = list.Count; list.Add(value); var addedValue = list[count]; } 

可以为指定集合有效实现的唯一集合接口是IEnumerable 。 我把我的实现留在那里作为例子。 但是看看ShuggyCoUk对IEnumerable实现的回答：

• c＃中的最大容量收集

Answer 3

一个非常简单的滚动窗口

 public class RollingWindow : IEnumerable { 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 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(); } } 

Answer 4

没有一个可用，但应该很容易编写一个函数来完成数组或集合。

Answer 5

你也可以覆盖Collection

 public class FixedSizeList : Collection { public int MaxItems {get;set;} protected override void InsertItem(int index, T item){ base.InsertItem(index, item); while (base.Count > MaxItems) { base.RemoveItem(0); } } } 

Answer 6

您可以从最合适的现有集合（Stack，Dequeue，List，CollectionBase等）inheritance并自己实现此function。 只需覆盖或替换Add（）方法即可。

Answer 7

你想要一个循环缓冲区。 这个其他的SO问题已经讨论了这个问题，它可能有助于为您提供一些想法。

Answer 8

ArrayList.FixedSize（）方法。

Answer 9

 public class CircularBuffer : ICollection, IEnumerable, ICollection, IEnumerable { private int capacity; private int size; private int head; private int tail; private T[] buffer; [NonSerialized()] private object syncRoot; public CircularBuffer(int capacity) : this(capacity, false) { } public CircularBuffer(int capacity, bool allowOverflow) { if (capacity < 0) throw new ArgumentException(Properties.Resources.MessageZeroCapacity, "capacity"); this.capacity = capacity; size = 0; head = 0; tail = 0; buffer = new T[capacity]; AllowOverflow = allowOverflow; } public bool AllowOverflow { get; set; } public int Capacity { get { return capacity; } set { if (value == capacity) return; if (value < size) throw new ArgumentOutOfRangeException("value", Properties.Resources.MessageCapacityTooSmall); var dst = new T[value]; if (size > 0) CopyTo(dst); buffer = dst; capacity = value; } } public int Size { get { return size; } } public bool Contains(T item) { int bufferIndex = head; var comparer = EqualityComparer.Default; for (int i = 0; i < size; i++, bufferIndex++) { if (bufferIndex == capacity) bufferIndex = 0; if (item == null && buffer[bufferIndex] == null) return true; else if ((buffer[bufferIndex] != null) && comparer.Equals(buffer[bufferIndex], item)) return true; } return false; } public void Clear() { size = 0; head = 0; tail = 0; } public int Put(T[] src) { return Put(src, 0, src.Length); } public int Put(T[] src, int offset, int count) { if (!AllowOverflow && count > capacity - size) throw new InvalidOperationException(Properties.Resources.MessageBufferOverflow); int srcIndex = offset; for (int i = 0; i < count; i++, tail++, srcIndex++) { if (tail == capacity) tail = 0; buffer[tail] = src[srcIndex]; } size = Math.Min(size + count, capacity); return count; } public void Put(T item) { if (!AllowOverflow && size == capacity) throw new InvalidOperationException(Properties.Resources.MessageBufferOverflow); buffer[tail] = item; if (++tail == capacity) tail = 0; size++; } public void Skip(int count) { head += count; if (head >= capacity) head -= capacity; } public T[] Get(int count) { var dst = new T[count]; Get(dst); return dst; } public int Get(T[] dst) { return Get(dst, 0, dst.Length); } public int Get(T[] dst, int offset, int count) { int realCount = Math.Min(count, size); int dstIndex = offset; for (int i = 0; i < realCount; i++, head++, dstIndex++) { if (head == capacity) head = 0; dst[dstIndex] = buffer[head]; } size -= realCount; return realCount; } public T Get() { if (size == 0) throw new InvalidOperationException(Properties.Resources.MessageBufferEmpty); var item = buffer[head]; if (++head == capacity) head = 0; size--; return item; } public void CopyTo(T[] array) { CopyTo(array, 0); } public void CopyTo(T[] array, int arrayIndex) { CopyTo(0, array, arrayIndex, size); } public void CopyTo(int index, T[] array, int arrayIndex, int count) { if (count > size) throw new ArgumentOutOfRangeException("count", Properties.Resources.MessageReadCountTooLarge); int bufferIndex = head; for (int i = 0; i < count; i++, bufferIndex++, arrayIndex++) { if (bufferIndex == capacity) bufferIndex = 0; array[arrayIndex] = buffer[bufferIndex]; } } public IEnumerator GetEnumerator() { int bufferIndex = head; for (int i = 0; i < size; i++, bufferIndex++) { if (bufferIndex == capacity) bufferIndex = 0; yield return buffer[bufferIndex]; } } public T[] GetBuffer() { return buffer; } public T[] ToArray() { var dst = new T[size]; CopyTo(dst); return dst; } #region ICollection Members int ICollection.Count { get { return Size; } } bool ICollection.IsReadOnly { get { return false; } } void ICollection.Add(T item) { Put(item); } bool ICollection.Remove(T item) { if (size == 0) return false; Get(); return true; } #endregion #region IEnumerable Members IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } #endregion #region ICollection Members int ICollection.Count { get { return Size; } } bool ICollection.IsSynchronized { get { return false; } } object ICollection.SyncRoot { get { if (syncRoot == null) Interlocked.CompareExchange(ref syncRoot, new object(), null); return syncRoot; } } void ICollection.CopyTo(Array array, int arrayIndex) { CopyTo((T[])array, arrayIndex); } #endregion #region IEnumerable Members IEnumerator IEnumerable.GetEnumerator() { return (IEnumerator)GetEnumerator(); } #endregion } 

您可以在此处找到循环缓冲区的实现： http ： //circularbuffer.codeplex.com