最大容量集合在C＃ [英] Maximum capacity collection in c#

问题描述

在净BCL有类似于列表集合的数据结构，其具有最大容量，说构造为100个项目，其中，当产品101被加入原始第一项被弹出/从集合中删除从而保证了产品数不超过100。

In the .Net BCL is there a collection data structure similar to list that has a maximum capacity, say configured to 100 items, which when item 101 is added the original first item is popped/removed from the collection thus ensuring the item count never exceeds 100.

我使用的是.NET 3.5

I’m using .net 3.5

在此先感谢

推荐答案

你所描述什么是循环缓冲区。我用这些偶然，最近移植一些旧的code到genericised C＃类（附后）。这code是 SharpNeat V2发展的一部分。

What you are describing is a circular buffer. I use these occasionally and recently ported some older code into a genericised C# class (attached). This code is part of SharpNeat V2 development.

这有O（1）提高性能并删除oprations而解决方案发布一个封装列表为O（n）。这是因为删除列表中的第0项将导致所有其他项目要改组的向下填补了国内空白。

This has O(1) performance on add and remove oprations whereas the solution posted that encapsulates a List is O(n). This is because removing the 0th item in a list causes all other items to be shuffled down to fill the gap.

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

这篇关于最大容量集合在C＃的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！