C#常用容器源码浅析

2022-04-18 03:20:47

C#常用容器源码浅析

[x] List

private static readonly T[] _emptyArray = new T[0]; //默认数组
private const int _defaultCapacity = 4;//如果没给出指定长度默认的列表长度，但是我不得不吐槽一点，定义出来没用这是最骚的，过会你们就看到了
private T[] _items;//存储列表元素的数组
private int _size;//当前列表元素个数
private int _version;//版本，防止迭代时再对容器操作
//------------------------------创建--------------------------------------
public List()
{
  this._items = List<T>._emptyArray;
}

public List(int capacity)
{
  if (capacity < 0)
    //抛异常
  if (capacity == 0)
    this._items = List<T>._emptyArray;
  else
    this._items = new T[capacity];
}
//声明一个默认大小，没啥好说的
//------------------------------Add--------------------------------------
public void Add(T item)
{
  if (this._size == this._items.Length)
    this.EnsureCapacity(this._size + 1);//如果列表的元素大小和容器大小一致了，就要扩容自己的内部容器
  this._items[this._size++] = item;//正常的添加
  ++this._version;//更新版本
}

private void EnsureCapacity(int min)
{
  if (this._items.Length >= min)
    return;
  int num = this._items.Length == 0 ? 4 : this._items.Length * 2;//重点在这里，如果没指定长度，创建的时候默认为0，当第一次添加元素的时候，指定的大小为4，对，就上面那个_defaultCapacity的值，最骚的就是他写了_defaultCapacity然后用的时候自己写了个4，666。不然就是扩容长度*2,每次进行2倍扩容
  if ((uint) num > 2146435071U)//为啥这函数叫安全扩容就是因为这里做了个安全性校验，防止*2以后的容量溢出uint范围
    num = 2146435071;
  if (num < min)
    num = min;
  this.Capacity = num;//设置新的大小
}

public int Capacity
{
  get
  {
    return this._items.Length;
  }
  set
  {
    if (value < this._size)
      //如果设置的值比已有的元素容量还小肯定是要抛异常的拉
    if (value == this._items.Length)
      return;
    if (value > 0)
    {
      T[] objArray = new T[value];//新创建一个数组
      if (this._size > 0)
        Array.Copy((Array) this._items, 0, (Array) objArray, 0, this._size);//吧当前容器的内容全部搬移到新的数组里，就是逐个拷贝，所以这里的开销需要自己考量，比如你初始数组是0，一开始就插入100w个元素，其中扩容了n次，实际上你的开销是远远大于100w次的，这就是为啥上面给你个指定容量大小的new，指定以后就是100w次，没有搬移的开销
      this._items = objArray;
    }
    else
      this._items = List<T>._emptyArray;
  }
}
//------------------------------Remove--------------------------------------
public bool Remove(T item)
{
  int index = this.IndexOf(item);//先找到要移除的item下标，所以如果要移除指定元素且你知道具体位置的话，直接调用RemoveAt会更高效
  if (index < 0)
    return false;
  this.RemoveAt(index);//移除
  return true;
}

public void RemoveAt(int index)
{
  if ((uint) index >= (uint) this._size)
    ThrowHelper.ThrowArgumentOutOfRangeException();
  --this._size;
  if (index < this._size)
    Array.Copy((Array) this._items, index + 1, (Array) this._items, index, this._size - index);//吧当前移除的下标+1后面的值全部搬运到index的位置
  this._items[this._size] = default (T);//然后把最后一个值清空咯
  ++this._version;
}
//所以其实remove的时候不会根据元素个数把之前扩容的空间再缩回来，如果你先加了100w个元素，再删99w个元素，实际上list的占用容量空间还是100w+的容量空间，那能怎么办呢，别急，下面那个方法可以让你快速瘦身
public void TrimExcess()
{
  if (this._size >= (int) ((double) this._items.Length * 0.9))//如果你的当前的元素个数大于容器空间的百分90那还是别缩了
    return;
  this.Capacity = this._size;//缩
}
//------------------------------迭代--------------------------------------
public bool MoveNext()
{
    List<T> list = this.list;
    if (this.version != list._version || (uint) this.index >= (uint) list._size) 
      return this.MoveNextRare();
    this.current = list._items[this.index];
    ++this.index;
    return true;
}
private bool MoveNextRare()
{
    if (this.version != this.list._version)
      //版本就是这里用的,防止有人在迭代的时候再去把元素增删这种骚操作，一抓到就报异常
    this.index = this.list._size + 1;
    this.current = default (T);
    return false;
}

//总结：list底层就是用array实现的一个可变长数组，存储形式是顺序存储，so，他具有顺序存储的数据结构的优点和缺点，查询快，增删开销大。
//----------END 其他没啥好说的了，下一个--------

[x] Stack

private object[] _array; //内部容器
private int _size;//元素个数
private int _version;
[NonSerialized]
private object _syncRoot;
private const int _defaultCapacity = 10;

//------------------------------new--------------------------------------
public Stack()
{
  this._array = new object[10];//stack默认大小是10
  this._size = 0;
  this._version = 0;
}
public Stack(int initialCapacity)
{
  if (initialCapacity < 0)
    //抛异常
  if (initialCapacity < 10)
    initialCapacity = 10;
  this._array = new object[initialCapacity];
  this._size = 0;
  this._version = 0;
}
//------------------------------Push--------------------------------------
public virtual void Push(object obj)
{
  if (this._size == this._array.Length)
  {
    object[] objArray = new object[2 * this._array.Length]; //直接两倍扩容，和list一样，为啥不安全扩容，嗯，好问题，我也不知道。
    Array.Copy((Array) this._array, 0, (Array) objArray, 0, this._size);//其他都和List一样
    this._array = objArray;
  }
  this._array[this._size++] = obj;
  ++this._version;
}
//------------------------------Pop Peek--------------------------------------
//和list一样，也没缩减
public virtual object Pop()
{
  if (this._size == 0)
    throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyStack"));
  ++this._version;
  object obj = this._array[--this._size];
  this._array[this._size] = (object) null;
  return obj;
}

public virtual object Peek()
{
  if (this._size == 0)
    throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyStack"));
  return this._array[this._size - 1];
}
//总结C#的Stack底层就是用数组模拟的栈，细节就是扩容的数据大小不会在缩回来了(所以我个人认为还是链表容器适合作stack，不会有开辟后搬移的开销，至于查嘛，stack本身就不允许随机访问，所以简直不要太完美，不懂为啥用arr)

[x] Queue

private object[] _array; //容器对象数组
private int _head;//头指针
private int _tail;//尾指针,指向下一个可用的空节点
private int _size;//实际大小
private int _growFactor;//增长因子，就每次扩容多少，默认2倍扩容
private int _version;//版本

//------------------------------new--------------------------------------
public Queue(): this(32, 2f) { }//默认扩容2，一开始大小32
public Queue(int capacity) : this(capacity, 2f) { }
public Queue(int capacity, float growFactor)
{
  if (capacity < 0)
    //容量是负数，抛出异常
  if ((double) growFactor < 1.0 || (double) growFactor > 10.0)
    //增长因子高于指定范围，抛出异常
  this._array = new object[capacity];
  this._head = 0;
  this._tail = 0;
  this._size = 0;
  this._growFactor = (int) ((double) growFactor * 100.0);
}
//------------------------------入队--------------------------------------
public virtual void Enqueue(object obj)//尾插
{
  if (this._size == this._array.Length)
  {//扩容
    int capacity = (int) ((long) this._array.Length * (long) this._growFactor / 100L);//扩容大小
    if (capacity < this._array.Length + 4)
      capacity = this._array.Length + 4;//扩容得太小还不行，至少要扩4个
    this.SetCapacity(capacity);
  }
  this._array[this._tail] = obj;
  this._tail = (this._tail + 1) % this._array.Length;//这里有个细节，他的容器是环状实现，尾是往后插的，当头是往尾巴部分回收的，所以数组前段的空间是可以被重复利用的，所以这里用了取余来去拿复用的回收后的空节点
  ++this._size;
  ++this._version;
}

private void SetCapacity(int capacity)
{
  object[] objArray = new object[capacity];
  if (this._size > 0)
  {
    if (this._head < this._tail)//当头<尾时就是正常的拷贝，将当前内容从当前头的位置开始全部拷贝到新数组
    {
      Array.Copy((Array) this._array, this._head, (Array) objArray, 0, this._size);
    }
    else//当头>=尾,先吧头到容器屁股的那段拷完再去吧0-尾巴的那段都拷了
    {
      Array.Copy((Array) this._array, this._head, (Array) objArray, 0, this._array.Length - this._head);
      Array.Copy((Array) this._array, 0, (Array) objArray, this._array.Length - this._head, this._tail);
    }
  }
  this._array = objArray;
  this._head = 0;
  this._tail = this._size == capacity ? 0 : this._size;
  ++this._version;
}
//------------------------------Dequeue Peek--------------------------------------
 public virtual object Dequeue()
{
  if (this.Count == 0)
    throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyQueue"));
  object obj = this._array[this._head];
  this._array[this._head] = (object) null;
  this._head = (this._head + 1) % this._array.Length;//环状容器，所以要跟着尾链表一样动态取余
  --this._size;
  ++this._version;
  return obj;
}

public virtual object Peek()
{
  if (this.Count == 0)
    throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyQueue"));
  return this._array[this._head];
}

//总结C#的Queue底层就是用数组模拟的队列，两个细节
//1.是环状容器实现，保证空间复用
//2.细节就是扩容的数据大小不会在缩回来了

[x] LinkedList

internal LinkedListNode<T> head;//头节点
internal int count;//容量
internal int version;//版本

//------------------------------new--------------------------------------
public LinkedList()//是的没错，啥都不干
{
}
//------------------------------插入--------------------------------------
public void AddLast(T value)
{
  LinkedListNode<T> newNode = new LinkedListNode<T>(this, value);//封装成一个节点
  if (this.head == null)
    this.InternalInsertNodeToEmptyList(newNode);//插入第一个
  else
    this.InternalInsertNodeBefore(this.head, newNode);//头插法
  node.list = this;//细节吧自己记下来了
}
private void InternalInsertNodeToEmptyList(LinkedListNode<T> newNode)
{
  newNode.next = newNode;//指向自己
  newNode.prev = newNode;//指向自己
  this.head = newNode;//指向第一个节点
  ++this.version;
  ++this.count;
}
private void InternalInsertNodeBefore(LinkedListNode<T> node, LinkedListNode<T> newNode)
{
    //头插法基本操作
  newNode.next = node; 
  newNode.prev = node.prev;
  node.prev.next = newNode;
  node.prev = newNode;
  ++this.version;
  ++this.count;
}
/*
原理类似不列举了，都是操作列表移动前后指针齐活，开销就是new这个节点的开销
AddAfter
AddBefore
AddFirst
*/
//------------------------------Remove--------------------------------------
 public bool Remove(T value)
{
  LinkedListNode<T> node = this.Find(value);//这个要先找到是哪个节点，find本身就是一个链表结构里很大的开销，所以建议少用这种方式而是直接指定，要指定不了又要频繁查询，顺序结构香的一批啊
  if (node == null)
    return false;
  this.InternalRemoveNode(node);
  return true;
}
public void Remove(LinkedListNode<T> node)
{
  this.ValidateNode(node);//检查节点可用性
  this.InternalRemoveNode(node);//remove
}
internal void InternalRemoveNode(LinkedListNode<T> node)
{
  if (node.next == node)
  {
    this.head = (LinkedListNode<T>) null;//是最后一个，那直接置空
  }
  else
  {
      //前的后等于我的后
      //后的前等于我的前
    node.next.prev = node.prev;
    node.prev.next = node.next;
    if (this.head == node)//如果是头节点再改下头指针
      this.head = node.next;
  }
  node.Invalidate();//这个内部就是置空,没做缓存，所以优化的话可以考虑做个空节点回收缓存池
  --this.count;
  ++this.version;
}
//node的Invalidate()
internal void Invalidate()
{
  this.list = (LinkedList<T>) null;
  this.next = (LinkedListNode<T>) null;
  this.prev = (LinkedListNode<T>) null;
}
//--------------------------Find--------------------------
public LinkedListNode<T> Find(T value)
{
  LinkedListNode<T> linkedListNode = this.head;
  EqualityComparer<T> equalityComparer = EqualityComparer<T>.Default;
  if (linkedListNode != null)
  {
    if ((object) value != null)
    {
      while (!equalityComparer.Equals(linkedListNode.item, value))
      {
        linkedListNode = linkedListNode.next;//从头结点开始往后遍历
        if (linkedListNode == this.head)//没找到（还记得这是个环状链表吗，一开始head的prev和next都是指向自己，所以最后还会指到自己）
          goto label_8;
      }
      return linkedListNode;
    }
    while ((object) linkedListNode.item != null)
    {
      linkedListNode = linkedListNode.next;
      if (linkedListNode == this.head)
        goto label_8;
    }
    return linkedListNode;
  }
label_8:
  return (LinkedListNode<T>) null;
}
//总结：linked是个双向链表，所以基本可以应付大部分需求，但是如果从优化角度的话可以考虑下将linked的释放重写下，变成缓存的，这样还就可以省去一部分new的开销，根据自己的使用场景来确定是用顺序列表（增删开销大，查询快）还是链表（增删开销小，查询快）。

[x] Dictionary
- 我另一篇帖子深入讲了，就不再写一遍了，快速定位就ctrl+F搜：字典的实现原理
- C#知识树整理——C#基础
[ ] ...如果还有想了解的容器欢迎评论留言

C#常用容器源码浅析

码农公寓

C#常用容器源码浅析

相关文章