Colección de capacidad máxima en C#

Question

En .Net BCL hay una estructura de datos de recopilación similar a la lista que tiene una capacidad máxima, por ejemplo configurada para 100 elementos, que cuando se agrega el elemento 101, el primer elemento original se extrae o se quita de la colección garantizando así la cuenta de artículos nunca excede 100.

estoy usando .NET 3.5

Gracias de antemano

Answer 1

Lo que está describiendo es un búfer circular. Los uso de forma ocasional y recientemente porté algún código anterior en una clase C# genérica (adjunta). Este código es parte de SharpNeat V2 development.

Esto tiene un rendimiento O (1) en agregar y eliminar opraciones, mientras que la solución publicada que encapsula una lista es O (n). Esto se debe a que al eliminar el 0 ° elemento de una lista, todos los demás elementos se mezclan para llenar el espacio.

 

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

no hay uno disponible, pero debe ser fácil de escribir una función para lograr esto con una matriz o colección.

Answer 3

ArrayList.FixedSize() method.

Answer 4

Puede heredar de cualquier colección existente que sea más apropiada (Pila, Dequeue, Lista, CollectionBase, etc.) e implementar esta característica usted mismo. Simplemente anule o reemplace el método Add().

Answer 5

No existe tal colección disponible pero es bastante fácil de escribir. La mejor forma de hacerlo es crear un nuevo tipo de colección que encapsule un tipo de colección existente.

Por ejemplo

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 
} 

Un par de respuestas sugeridas herencia como un mecanismo. Esta ciertamente no es una buena ruta, especialmente si proviene de una de las colecciones genéricas. Estas colecciones no están diseñadas para ser heredadas y es muy fácil evitar accidentalmente cualquier verificación que realice una capacidad como resultado de un método Agregar o Eliminar.

La razón principal es que estos métodos no son virtuales, por lo que no se pueden anular. Te verás obligado a declarar un método Add con un nombre diferente (confundiendo así a tus usuarios) o volver a declarar Add con la nueva sintaxis. Esto último es muy inseguro porque tan pronto como una instancia de su clase pasa a una referencia del tipo base, no se invocarán todos sus métodos y la lista podrá crecer más allá de su capacidad.

EDITAR

Como la sección de comentarios discusión se ha indicado, la implementación de List<T> no es el mejor enfoque aquí. La razón es que viola el principio de sustitución en varios casos. La forma más sencilla de mostrar el problema es imaginar si mi implementación pasó al siguiente método. Este código debería pasar por cualquier implementación IList<T> pero fallaría en este caso si la lista estuviera en capacidad.

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

La única interfaz de recogida que puede ser implementado de forma válida para la colección especificada es IEnumerable<T>. Dejé mi implementación allí como un ejemplo. Pero véase la respuesta de ShuggyCoUk para una aplicación IEnumerable<T>:

• Maximum capacity collection in c#

Answer 6

¿Quieres un buffer circular. Este otro SO question ya habla de eso y podría ayudar a proporcionar algunas ideas para usted.

Answer 7

también puede simplemente anular Colección

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

una ventana de rodadura muy simple

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 
} 

Usted puede encontrar esta aplicación de un buffer circular aquí: http://circularbuffer.codeplex.com