XIAOSUO 记录个人学习的足迹

一、采用数组保存数据

部分私有成员如下：

public class List<T> : IList<T>, System.Collections.IList   
{
    private const int _defaultCapacity = 4;   //初始list大小
    private T[] _items;                       //list数据项保存的数组
    private int _size;                        //数据项的实际个数
    private int _version;                     //数据项被修改过的次数,主要用户枚举过程中对于数据的修改
    static T[] _emptyArray = new T[0];
    //................其他部分
｝

数据项查找复杂度为O(n)；

public int IndexOf(T item)
{
    return Array.IndexOf(_items, item, 0, _size);
}

下标查找复杂度为O(1)；

二、当数据空间不够时，扩大1倍空间

带来O(n)的数据复制开销。最坏可能带来sizeof(T)*(n-1)的空间浪费（可以使用TrimExcess来缩紧）。

//获取与设置保存数据项数组的长度，注意在设置长度时所带来的开销
public int Capacity
{
	get { return _items.Length; }
	set
	{
		if (value != _items.Length)
		{
			if (value < _size)
			{
				ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
			}

			if (value > 0)
			{
				//注意_size个元素复制开销,与原有对象丢弃后可引起cc启动的开销
				T[] newItems = new T[value];
				if (_size > 0)
				{
					Array.Copy(_items, 0, newItems, 0, _size);
				}
				_items = newItems;
			}
			else
			{
				_items = _emptyArray;
			}
		}
	}
}

//当期望数组容量最小值min大于等于预有数组的容量时,不需任何操作
//否则数组的容量将至少扩充为当前容量的2倍,实际数组要么当前容量的2倍,要么为min
//另外,如果当前数组长度为0,数组容量要么为_defaultCapacity,要么为min,但不会小于_defaultCapacity
//注意,数组扩充时会产生复制和垃圾对象的开销
private void EnsureCapacity(int min)
{
	if (_items.Length < min)
	{
		int newCapacity = _items.Length == 0 ? _defaultCapacity : _items.Length * 2;
		if (newCapacity < min) newCapacity = min;
		Capacity = newCapacity;
	}
}

//只有当数据项的个数小于数据实际长度的0.9倍时,系统才会收索数组
//在收索过程中会创建新的缓冲区数据,涉及到_size个数据项的复制,以及可能会引起cc启动的开销
public void TrimExcess()
{
	int threshold = (int)(((double)_items.Length) * 0.9);
	if (_size < threshold)
	{
		Capacity = _size;
	}
}

三、插入数据时最坏可能会带来n-1次数据复制

小心InsertRange里面的效率陷阱(对于非IColletion​集合的操作)，用Insert插入多个数据可能导致效率低下。

//注意由于空间不足引起的开销，该方法非线性安全
public void Add(T item)
{
	if (_size == _items.Length) EnsureCapacity(_size + 1);
	_items[_size++] = item;
	_version++;
}

public void AddRange(IEnumerable<T> collection)
{
	InsertRange(_size, collection);
}

//注意在插于时会产生(_size-index)次数据复制的开销
//当插于的数据使得原有缓冲空间不足时,会产生(2*_size-index)次复制的开销,同时引起cc启动开销
public void Insert(int index, T item)
{
	if ((uint)index > (uint)_size)
	{
		ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_ListInsert);
	}
	if (_size == _items.Length) EnsureCapacity(_size + 1);
	if (index < _size)
	{
		Array.Copy(_items, index, _items, index + 1, _size - index);
	}
	_items[index] = item;
	_size++;
	_version++;
}

//count为collection中包含元素的数量
//在当数据项容量满足插入后容量时
//1.当collection为System.Collection.Generic.ICollection<T>类型,且Collection不指向自己时
//该操作会涉及到(_size-index+2*count)次数据复制操作
//2.当collection为System.Collection.Generic.ICollection<T>类型,且Collection指向自己时
//该操作会涉及到(2*_size-index)次数据复制操作
//3.当collection不是System.Collection.Generic.ICollection<T>类型,该操作循环调用count次Insert函数

//分析情况1与insert操作之间复杂度的比较
//在这种情况下如果使用insert方式实现相同操作,需要(count*(_size-index))次操作
//要求(_size-index+2*count)>(count*(_size-index))
//有2count>(count-1)*(_size-index)
//当count很多时,及时为count约等于count-1,因此有(_size-index)<2,即index>_size-2;
//由于必然有index<_size,所以只有到index=_size-1时该表达式成了,除此之外都不会有InsertRange效率差于多次使用insert方法;

//对于情况2,略

//情况3,实际等于count次调用insert方法

//当数据容量不满足插于后容量后
//1.当collection为System.Collection.Generic.ICollection<T>类型,且Collection不指向自己时
//该操作会涉及到(2*_size-index+2*count)次数据复制操作
//2.当collection为System.Collection.Generic.ICollection<T>类型,且Collection指向自己时
//该操作会涉及到(3*_size-index次数据复制操作

//结论:对于大量差于数据时,尽量使用InsertRange方法,而不是Insert
//另外尽量保证插于的数据为System.Collection.Generic.ICollection<T>类型
public void InsertRange(int index, IEnumerable<T> collection)
{
	if (collection == null)
	{
		ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
	}

	if ((uint)index > (uint)_size)
	{
		ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
	}

	ICollection<T> c = collection as ICollection<T>;
	if (c != null)
	{   
		int count = c.Count;
		if (count > 0)
		{
			EnsureCapacity(_size + count);
			if (index < _size)
			{
				Array.Copy(_items, index, _items, index + count, _size - index);
			}

			if (this == c)
			{
				Array.Copy(_items, 0, _items, index, index);
				Array.Copy(_items, index + count, _items, index * 2, _size - index);
			}
			else
			{
				T[] itemsToInsert = new T[count];
				c.CopyTo(itemsToInsert, 0);
				itemsToInsert.CopyTo(_items, index);
			}
			_size += count;
		}
	}
	else
	{
		using (IEnumerator<T> en = collection.GetEnumerator())
		{
			while (en.MoveNext())
			{
				Insert(index++, en.Current);
			}
		}
	}
	_version++;
}

四、当删除数据时最坏可能带来n-1次数据复制

RemoveAt、RemoveRange、RemoveAll（Predict​ match）的复杂度在同一个数量级上。对于一组数据的删除循环调用RemoveAt效率低下。

public bool Remove(T item)
{
	int index = IndexOf(item);
	if (index >= 0)
	{
		RemoveAt(index);
		return true;
	}

	return false;
}

//该方法时间复杂度为O(n),并且不会涉及到创建新的缓冲区和大量数据项在缓冲区的复制操作
public int RemoveAll(Predicate<T> match)
{
	if (match == null)
	{
		ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
	}

	int freeIndex = 0;  

	while (freeIndex < _size && !match(_items[freeIndex])) freeIndex++;
	if (freeIndex >= _size) return 0;

	int current = freeIndex + 1;
	while (current < _size)
	{
		while (current < _size && match(_items[current])) current++;

		if (current < _size)
		{
			_items[freeIndex++] = _items[current++];
		}
	}

	Array.Clear(_items, freeIndex, _size - freeIndex);
	int result = _size - freeIndex;
	_size = freeIndex;
	_version++;
	return result;
}

//该操作涉及到(_size-index)次数据移动开销
//注意!数据删除后,保存数据的数据容量并没有缩减,如果不对数据的数据容量进行缩减,可能出现数组中大量单元空闲,进而对内存的使用产生浪费
public void RemoveAt(int index)
{
	if ((uint)index >= (uint)_size)
	{
		ThrowHelper.ThrowArgumentOutOfRangeException();
	}
	_size--;
	if (index < _size)
	{
		Array.Copy(_items, index + 1, _items, index, _size - index);
	}
	_items[_size] = default(T);
	_version++;
}

//该操作涉及到(_size-index)次数据移动开销
//对于多个数据的删除,单次调用RemoveRange优于count次调用RemoveAt
//注意!数据删除后,保存数据的数据容量并没有缩减,如果不对数据的数据容量进行缩减,可能出现数组中大量单元空闲,进而对内存的使用产生浪费
public void RemoveRange(int index, int count)
{
	if (index < 0 || count < 0)
	{
		ThrowHelper.ThrowArgumentOutOfRangeException((index < 0 ? ExceptionArgument.index : ExceptionArgument.count), ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
	}

	if (_size - index < count)
		ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);

	if (count > 0)
	{
		int i = _size;
		_size -= count;
		if (index < _size)
		{
			Array.Copy(_items, index + count, _items, index, _size - index);
		}
		Array.Clear(_items, _size, count);
		_version++;
	}
}

五、提供QuickSort排序和二分查找方法