Сбор максимальной емкости в C#

Question

В .Net BCL есть структура данных коллекции, аналогичная списку, которая имеет максимальную емкость, например, сконфигурирована на 100 элементов, что при добавлении элемента 101 исходный первый элемент выгружается/удаляется из Таким образом, коллекция обеспечивая количество элементов не превышает 100.

Я использую .NET 3.5

заранее спасибо

Answer 1

Что вы описываете, это круговой буфер. Я иногда использовал это, и недавно портировал некоторый старый код в обобщенный класс C# (прилагается). Этот код является частью SharpNeat V2 development.

Это имеет производительность O (1) при добавлении и удалении отпечатков, тогда как решение отправлено, что инкапсулирует список 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

Там не один доступный, но это должно быть легко написать функцию, чтобы выполнить это с массив или коллекция.

Answer 3

ArrayList.FixedSize() способ.

Answer 4

Вы можете унаследовать любую имеющуюся коллекцию (Stack, Dequeue, List, CollectionBase и т. Д.) И реализовать эту функцию самостоятельно. Просто переопределите или замените метод Add().

Answer 5

Нет такой коллекции, но ее довольно легко написать. Лучший способ сделать это - создать новый тип коллекции, который инкапсулирует существующий тип коллекции.

Например

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 с новым синтаксисом. Последнее очень опасно, поскольку, как только экземпляр вашего класса передается в ссылку базового типа, все ваши методы не будут вызываться, а список может увеличиться.

EDIT

В обсуждении комментарий раздела указал, внедрение 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> реализации:

• Maximum capacity collection in c#

Answer 6

Вы хотите кольцевой буфер. Этот другой SO question уже говорит об этом, и это может помочь вам представить некоторые идеи.

Answer 7

вы также можете просто переопределить Коллекция

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

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

Answer 9

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