Nel BCL .Net esiste una struttura di dati di raccolta simile all'elenco con una capacità massima, ad esempio configurata a 100 elementi, che quando viene aggiunto l'elemento 101 il primo oggetto originale viene estratto/rimosso dal raccolta garantendo in tal modo il numero di voce non supera mai i 100Raccolta di capacità massima in C#
sto usando NET 3.5
Grazie in anticipo
Quello che stai descrivendo è un buffer circolare. Uso questi di tanto in tanto e di recente ho convertito alcuni vecchi codici in una classe C# generica (allegata). Questo codice è parte di SharpNeat V2 development.
Questo ha prestazioni O (1) su aggiungere e rimuovere oprazioni mentre la soluzione pubblicata che incapsula un elenco è O (n). Questo perché rimuovere il 0 ° elemento in una lista fa sì che tutti gli altri elementi vengano mischiati verso il basso per riempire il vuoto.
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
}
}
non ce n'è uno disponibile, ma dovrebbe essere facile scrivere una funzione per ottenere questo risultato con una matrice o collezione.
metodo ArrayList.FixedSize().
È possibile ereditare da qualsiasi raccolta esistente fosse più appropriata (Stack, Dequeue, List, CollectionBase, ecc.) E implementare questa funzionalità da soli. Basta eseguire l'override o sostituire il metodo Add().
La maggior parte di queste classi non consente di eseguire l'override di Add() poiché non è virtuale. –
Potrebbe non essere possibile sovrascriverli, ma è possibile utilizzarli nell'implementazione della propria raccolta, evitando la maggior parte del lavoro. –
Non esiste una raccolta di questo tipo, ma uno è abbastanza semplice da scrivere. Il modo migliore per farlo è creare un nuovo tipo di raccolta che incapsuli un tipo di raccolta esistente.
Per esempio
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 paio di risposte suggerito eredità come un meccanismo. Questo non è certamente un buon percorso, specialmente se si proviene da una delle raccolte generiche. Queste raccolte non sono progettate per essere ereditate da ed è molto facile aggirare accidentalmente qualsiasi controllo effettuato come risultato di un metodo Aggiungi o Rimuovi.
Il motivo principale è che questi metodi non sono virtuali, quindi non possono essere sovrascritti. Saresti costretto a dichiarare un metodo Add con un nome diverso (confondendo così i tuoi utenti) o ripetere nuovamente Aggiungi con la nuova sintassi. Quest'ultimo è molto pericoloso perché non appena un'istanza della classe viene passata a un riferimento del tipo di base, tutti i tuoi metodi non verranno chiamati e l'elenco può superare la capacità.
EDIT
Mentre la discussione commento sezione è indicato, attuando List<T> non è l'approccio migliore qui. La ragione per cui è che viola il principio di sostituzione in diversi casi. Il modo più semplice per visualizzare il problema è immaginare se la mia implementazione è stata passata al seguente metodo. Questo codice dovrebbe passare per qualsiasi implementazione IList<T> ma fallirebbe in questo caso se l'elenco fosse a capacità.
public void Example<T>(IList<T> list, T value) {
var count = list.Count;
list.Add(value);
var addedValue = list[count];
}
L'unica interfaccia per la raccolta che può essere implementata validamente per la raccolta specificata è IEnumerable<T>. Ho lasciato la mia implementazione lassù come esempio. Ma vedere la risposta di ShuggyCoUk per IEnumerable<T> implementazione:
+1 Questa è una risposta _excellent_! È bello ascoltare una spiegazione così lucida del perché si è scelto di implementare 'IList
@Andrew Grazie! – JaredPar
Il tuo concetto è giusto, ma questa è una struttura dati incredibilmente inefficiente, in cui ogni inserto una volta che la lista è piena è O (n) piuttosto che la tipica O (1) per una lista. Un'implementazione del mondo reale dovrebbe probabilmente utilizzare un buffer circolare. –
Volete un buffer circolare. Questo altro SO question parla già di questo e potrebbe aiutare a fornire alcune idee per voi.
si può anche semplicemente ignorare 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);
}
}
}
Che funziona fino a quando non viene passato a una funzione che accetta un elenco
annotato e modificato –
Non si vorrebbe ancora fare "nuovo vuoto Aggiungi", ma è solo una ricetta per il disastro. Dovresti eseguire l'override di InsertItem per eseguire i controlli. –
Davvero un semplice finestra di rotolamento
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();
}
}
Questa è una soluzione molto migliore per le prestazioni. – FlappySocks
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
}
Potete trovare questa implementazione di un buffer circolare qui: http://circularbuffer.codeplex.com
Non ci credo questo soddisfa i suoi bisogni. Voleva che il nuovo elemento aggiunto e uno vecchio caduto, mentre ArrayList.FixedSize() impedirà aggiunte alla lista. –