Maximale Kapazität Sammlung in C#

Question

In der. NET BCL gibt es eine Sammlung Datenstruktur ähnlich wie eine Liste, die eine maximale Kapazität hat, sagen konfiguriert auf 100 Elemente, die, wenn Element 101 hinzugefügt wird das ursprüngliche erste Element aus dem Popup/entfernt Sammlung wodurch sichergestellt wird die Elementanzahl übersteigt nie 100.

ich verwende .net 3.5

Vielen Dank im Voraus

Answer 1

Was Sie beschreiben, ist ein Ringpuffer. Ich benutze diese gelegentlich und habe vor kurzem älteren Code in eine generische C# -Klasse (angehängt) portiert. Dieser Code ist Teil von SharpNeat V2 development.

Dies hat O (1) -Leistung beim Hinzufügen und Entfernen von Operationen, während die veröffentlichte Lösung, die eine Liste einkapselt, ist O (n). Dies liegt daran, dass das Entfernen des 0. Elements in einer Liste bewirkt, dass alle anderen Elemente neu gemischt werden, um die Lücke zu füllen.

 

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

es gibt nicht ein zur Verfügung, aber es sollte einfach sein, eine Funktion zu schreiben, dies zu tun mit ein Array oder eine Sammlung.

Answer 3

ArrayList.FixedSize() Methode.

Answer 4

Sie können von jeder vorhandenen Sammlung übernehmen (Stack, Dequeue, List, CollectionBase usw.) und diese Funktion selbst implementieren. Überschreiben oder ersetzen Sie einfach die Add() - Methode.

Answer 5

Es gibt keine solche Sammlung verfügbar, aber eine ist ziemlich einfach zu schreiben. Der beste Weg, dies zu tun, ist einen neuen Sammlertyp zu erstellen, der einen vorhandenen Sammlertyp einkapselt.

Zum Beispiel

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 
} 

Ein paar Antworten vorgeschlagen Vererbung als Mechanismus. Dies ist sicherlich keine gute Route, besonders wenn Sie von einer der generischen Sammlungen ableiten. Diese Sammlungen sind nicht darauf ausgelegt, vererbt zu werden, und es ist sehr einfach, versehentlich alle Prüfungen zu umgehen, die Sie als Ergebnis einer Add- oder Remove-Methode durchführen.

Der Hauptgrund ist, dass diese Methoden nicht virtuell sind und daher nicht überschrieben werden können. Sie wären gezwungen, entweder eine Add-Methode mit einem anderen Namen zu deklarieren (und damit Ihre Benutzer zu verwirren) oder Add mit der neuen Syntax erneut zu deklarieren. Letzteres ist sehr unsicher, da sobald eine Instanz Ihrer Klasse an eine Referenz des Basistyps übergeben wird, alle Ihre Methoden nicht aufgerufen werden und die Liste die Kapazität überschreiten kann.

EDIT

Als Abschnitt Diskussion Kommentar wurde, angegeben hier List<T> ist nicht der beste Ansatz zu implementieren. Der Grund dafür ist, dass es in mehreren Fällen gegen das Substitutionsprinzip verstößt. Die einfachste Möglichkeit, das Problem anzuzeigen, stellen Sie sich vor, wenn meine Implementierung an die folgende Methode übergeben wurde. Dieser Code sollte für jede IList<T> Implementierung übergeben werden, würde aber in diesem Fall fehlschlagen, wenn die Liste ausgelastet wäre.

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

Die einzige Sammlung Schnittstelle, die für die angegebene Sammlung durchgeführt werden kann, ist rechtsgültig IEnumerable<T>. Ich habe meine Implementierung als Beispiel dort oben gelassen. Aber sehen ShuggyCoUk Antwort für eine IEnumerable<T> Umsetzung:

• Maximum capacity collection in c#

Answer 6

Sie einen Ringpuffer wollen. Diese andere SO question spricht bereits darüber und es könnte helfen, einige Ideen für Sie bereitzustellen.

Answer 7

Sie können auch außer Kraft setzen gerade Sammlung

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

Ein wirklich einfaches Rollfenster

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 
} 

Sie diese Implementierung eines Ringpuffers finden Sie hier: http://circularbuffer.codeplex.com