C#中的最大容量集合

Question

C#中的最大容量集合

c#.net

16

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

我正在使用 .net 3.5

提前感谢

- SuperSuperDev1234

9个回答

9

您所描述的是一个循环缓冲区。我偶尔使用这些，并最近将一些旧代码移植到了通用化的C#类中（附加）。此代码是SharpNeat V2开发的一部分。

这种方法在添加和删除操作上具有O(1)的性能，而封装List的解决方案则为O(n)。这是因为从列表中删除第0项会导致所有其他项向下移动以填补空缺。


使用System;
使用System.Collections.Generic;
使用System.Text;
命名空间SharpNeat.Utility
{
    /// 
    /// 这是一个类型为T的通用循环缓冲区。必须在构造时分配循环缓冲区的容量。可以无限制地将项目加入队列，但是当缓冲区的容量达到时，缓冲区中最旧的值将被覆盖，因此最好将缓冲区视为循环数组或缓冲区。
    /// 
    public class CircularBuffer
    {
        /// 
        /// 存储循环缓冲区值的内部数组。
        /// 
        protected T[] _buff;
/// 
        /// 先前加入队列的项目的索引。如果缓冲区为空，则为-1。
        /// 
        protected int _headIdx;
/// 
        /// 要出队的下一个项目的索引。如果缓冲区为空，则为-1。
        /// 
        protected int _tailIdx;
#region Constructors
/// 
        /// 构造具有指定容量的循环缓冲区。
        /// 
        /// 
        public CircularBuffer(int capacity)
        {
            _buff = new T[capacity];
            _headIdx = _tailIdx = -1;
        }
#endregion
#region Properties
/// 
        /// 获取缓冲区中的项目数。如果已满，则返回缓冲区的容量。
        /// 
        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
/// 
        /// 清除缓冲区。
        /// 
        public virtual void Clear()
        {
            _headIdx = _tailIdx = -1;
        }
/// 
        /// 将新项目加入队列。如果缓冲区已达到容量，则覆盖缓冲区中最旧的项目。
        /// 
        /// 
        public virtual void Enqueue(T item)
        {
            if(_headIdx == -1)
            {   // 缓冲区当前为空。
                _headIdx = _tailIdx = 0;
                _buff[0] = item;
                return;
            }
// 确定要写入的索引。
            if(++_headIdx == _buff.Length)
            {   // 围绕。
                _headIdx = 0;
            }
if(_headIdx == _tailIdx)
            {   // 缓冲区溢出。递增tailIdx。
                if(++_tailIdx == _buff.Length) 
                {   // 围绕。
                    _tailIdx=0;
                }
                _buff[_headIdx] = item;
                return;
            }
_buff[_headIdx] = item;
            return;
        }
/// 
        /// 从缓冲区的后端删除最旧的项目并将其返回。
        /// 
        /// 
        public virtual T Dequeue()
        {
            if(_tailIdx == -1)
            {   // 缓冲区当前为空。
                throw new InvalidOperationException("buffer is empty.");
            }
T item = _buff[_tailIdx];
if(_tailIdx == _headIdx)
            {   // 缓冲区现在为空。
                _headIdx=_tailIdx=-1;
                return item;
            }
if(++_tailIdx == _buff.Length)
            {   // 围绕。
                _tailIdx = 0;
            }
return item;
        }
/// 
        /// 从缓冲区的前端弹出最近添加的项目并将其返回。
        /// 
        /// 
        public virtual T Pop()
        {
            if(_tailIdx == -1)
            {   // 缓冲区当前为空。
                throw new InvalidOperationException("buffer is empty.");
            }
T item = _buff[_headIdx];
if(_

- redcalx

8

一个非常简单的滚动窗口

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();
    }
}

- ShuggyCoUk

2

您也可以只覆盖 Collection

public class FixedSizeList<T> : Collection<T>
{
    public int MaxItems {get;set;}

    protected override void InsertItem(int index, T item){
        base.InsertItem(index, item);

        while (base.Count > MaxItems) {
            base.RemoveItem(0);
        }
    }
}

- Russ Bradberry

2

目前没有现成的方法，但是可以很容易地通过数组或集合编写一个函数来实现此功能。

- xpda

1

你可以继承最合适的现有集合（如Stack、Dequeue、List、CollectionBase等），并自己实现此功能。只需覆盖或替换Add()方法即可。

- John Fisher

1

大多数类不允许您重写Add()，因为它不是虚拟的。 - Dan Diplo

你可能无法覆盖它们，但是你可以在自己的集合实现中使用它们，避免大部分的工作。 - John Fisher

1

你需要一个循环缓冲区。这个SO问题已经讨论了这个问题，可能会为你提供一些想法。

- Erich Mirabal

0

public class CircularBuffer<T> : ICollection<T>, IEnumerable<T>, 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<T>.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<T> 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<T> Members

    int ICollection<T>.Count
    {
        get { return Size; }
    }

    bool ICollection<T>.IsReadOnly
    {
        get { return false; }
    }

    void ICollection<T>.Add(T item)
    {
        Put(item);
    }

    bool ICollection<T>.Remove(T item)
    {
        if (size == 0)
            return false;

        Get();
        return true;
    }

    #endregion

    #region IEnumerable<T> Members

    IEnumerator<T> IEnumerable<T>.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

- Beachwalker

0

ArrayList.FixedSize() 方法。

- user142350

4

我不认为这符合他的需求。他想要添加新项目并删除旧项目，而 ArrayList.FixedSize() 会防止在列表中进行添加。 - John Fisher

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- JaredPar · Accepted Answer

目前没有这样的集合可用，但是编写一个相当容易。最好的方法是创建一个新的集合类型来封装现有的集合类型。

例如：

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或Remove方法的结果会影响容量。

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

编辑部分：正如评论讨论所示，在这里实现List并不是最佳方法。原因是它在几个情况下违反了替换原则。显示问题的最简单方法是想象一下，如果我的实现被传递到以下方法中，这段代码应该对任何IList实现都有效，但如果列表已满，则在此情况下将失败。

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#中最大容量的集合