Steven Blogs

C# 中的 数组[]、ArrayList、List

数组open in new window

在 C# 中，数组实际上是对象，而不只是如在 C 和 C++ 中的连续内存的可寻址区域。

属性：

  • 数组可以是一维、多维或交错的。
  • 创建数组实例时，将建立纬度数量和每个纬度的长度。 这些值在实例的生存期内无法更改。
  • 数值数组元素的默认值设置为零，而引用元素设置为 null。
  • 交错数组是数组的数组，因此其元素为引用类型且被初始化为 null。
  • 数组从零开始编制索引：包含 n 元素的数组从 0 索引到 n-1。
  • 数组元素可以是任何类型，其中包括数组类型。
  • 数组类型是从抽象的基类型 Array 派生的引用类型。 所有数组都会实现 IList 和 IEnumerable。 可在 C# 中使用 foreach 迭代数组。 原因是单维数组还实现了 IList<T> 和 IEnumerable<T>。

  1. 命名空间： System;

  2. 特点
    内存连续存储；索引速度快；赋值修改元素简单

  3. 缺点
    插入数据麻烦(连续内存，插入后续的元素都需要移动)；声明数组需指定长度(长了没用完浪费内存，短了可能不够用)；

  4. 分类

    • 单维数组 eg: int[] array = new int[5];
    • 多维数组 eg:
    int[,] array = new int[4, 2]; // 四行两列的二维数组
int[,,] array3Da = new int[2, 2, 3] { 
    { { 1, 2, 3 }, {  4,  5,  6 } },
    { { 7, 8, 9 }, { 10, 11, 12 } }
}; // 三个维度（2、2 和 3）的数组
    • 交错数组 eg：
    // 声明一个具有三个元素的一维数组，其中每个元素都是一维整数数组
int[][] jaggedArray = new int[3][];

// 必须初始化的元素后才可使用它
jaggedArray[0] = new int[5];
jaggedArray[1] = new int[4];
jaggedArray[2] = new int[2];
    • 隐式类型的数组
      通常用于查询表达式、匿名类型、对象和集合初始值设定项.
    var a = new[] { 1, 10, 100, 1000 }; // int[]
var b = new[] { "hello", null, "world" }; // string[]

Arrayopen in new window

数组类型([])是从抽象的基类型 Array 派生的引用类型。

Array 类提供一些方法，用于创建、处理、搜索数组并对数组进行排序，从而充当公共语言运行时中所有数组的基类。

Array的用法与数组[]几乎一样，可以看做是数组。在定义的时候需要指定长度。

Array 的 公共静态成员(public static)是线程安全的。但不保证所有实例成员都是线程安全的。

Array.SyncRoot 属性，用于同步对 Array 的访问的对象。

下面的代码示例演示如何使用属性在整个枚举过程中锁定数组 SyncRoot

Array myArray = new int[] { 1, 2, 4 };
lock(myArray.SyncRoot)
{
    foreach (Object item in myArray)
        Console.WriteLine(item);
}

ArrayListopen in new window

为了解决数组的一些短板,ArrayList 继承了 IList 接口，提供了数据存储和检索。 ArrayList 对象的大小是按照其中存储的数据来动态扩充与收缩的。在声明 ArrayList 对象时并不需要指定它的长度。

  1. 命名空间： System.Collections;
  2. 特点
    允许插入不同类型的数据(插入object)，无需指定长度；只有一个维度
  3. 缺点
    处理数据可能会报类型不匹配的错误；在存储或检索值类型时通常发生装箱和取消装箱open in new window操作，性能耗损较大

装箱：就是将值类型的数据打包到引用类型的实例中
拆箱：就是从引用数据中提取值类型

一些方法：
public virtual int Add(object? value);:将对象添加到 ArrayList 的结尾处，返回已添加 value 的 ArrayList 索引

public virtual void Remove (object? obj);:从 ArrayList 中移除特定对象的第一个匹配项

ArrayList 是使用 object 数组 实现的，它涉及拆箱和装箱。默认容量 4

public class ArrayList : IList, ICloneable
{
    private object?[] _items; // Do not rename (binary serialization)
    private int _size; // Do not rename (binary serialization)
    private int _version; // Do not rename (binary serialization)

    private const int _defaultCapacity = 4;

    // Constructs a ArrayList. The list is initially empty and has a capacity
    // of zero. Upon adding the first element to the list the capacity is
    // increased to _defaultCapacity, and then increased in multiples of two as required.
    public ArrayList()
    {
        _items = Array.Empty<object>();
    }

    // Constructs a ArrayList with a given initial capacity. The list is
    // initially empty, but will have room for the given number of elements
    // before any reallocations are required.
    //
    public ArrayList(int capacity)
    {
        if (capacity < 0) throw new ArgumentOutOfRangeException(nameof(capacity), SR.Format(SR.ArgumentOutOfRange_MustBeNonNegNum, nameof(capacity)));

        if (capacity == 0)
            _items = Array.Empty<object>();
        else
            _items = new object[capacity];
    }
}

扩容：

ArrayList<T> 在内部有一个存放数据的数组，当新增数据时候，如果该数组有可用，则会将数据放入数组，并将下标向后移动，如果没有足够的数组，则会进行扩容，如果创建的时候没有给定容量，第一次扩容则会使用默认的容量，如果当前有元素，则会扩容至当前容量的两倍。 可以看到扩容 是将原数组的数据拷贝到新创建的数组中

// Adds the given object to the end of this list. The size of the list is
// increased by one. If required, the capacity of the list is doubled
// before adding the new element.
public virtual int Add(object? value)
{
    if (_size == _items.Length) EnsureCapacity(_size + 1);
    _items[_size] = value;
    _version++;
    return _size++;
}

// Ensures that the capacity of this list is at least the given minimum
// value. If the current capacity of the list is less than min, the
// capacity is increased to twice the current capacity or to min,
// whichever is larger.
private void EnsureCapacity(int min)
{
    if (_items.Length < min)
    {
        int newCapacity = _items.Length == 0 ? _defaultCapacity : _items.Length * 2;
        // Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow.
        // Note that this check works even when _items.Length overflowed thanks to the (uint) cast
        if ((uint)newCapacity > Array.MaxLength) newCapacity = Array.MaxLength;
        if (newCapacity < min) newCapacity = min;
        Capacity = newCapacity;
    }
}

// Gets and sets the capacity of this list.  The capacity is the size of
// the internal array used to hold items.  When set, the internal
// array of the list is reallocated to the given capacity.
public virtual int Capacity
{
    get => _items.Length;
    set
    {
        if (value < _size)
        {
            throw new ArgumentOutOfRangeException(nameof(value), SR.ArgumentOutOfRange_SmallCapacity);
        }

        // We don't want to update the version number when we change the capacity.
        // Some existing applications have dependency on this.
        if (value != _items.Length)
        {
            if (value > 0)
            {
                object[] newItems = new object[value];
                if (_size > 0)
                {
                    Array.Copy(_items, newItems, _size);
                }
                _items = newItems;
            }
            else
            {
                _items = new object[_defaultCapacity];
            }
        }
    }
}

ArrayList源码open in new window

List<T>open in new window

通过使用大小根据需要动态增加的数组来实现泛型接口。

相比于ArrayList，List<T>不存在装箱拆箱的缺点，List类是ArrayList类的泛型等效类，它的大部分用法都与ArrayList相似，因为List类也继承了IList接口。最关键的区别在于，在声明List集合时，需要为其声明List集合内数据的对象类型。

  1. 命名空间 System.Collections.Generic
  2. 特点
    插入类型固定(泛型)；无需指定长度，只有一个维度，允许重复元素

List底层实现使用 泛型数组(Array)，默认容量 4，初始化时候可以指定初始化容量，如果不指定则会给定一个空的泛型数组。

public class List<T>:IList<T>,IList,IReadOnlyList<T>
{
    private const int DefaultCapacity = 4;
    internal T[] _items;
    internal int _size;
    private int _version;

    public List()
    {
        _items = s_emptyArray;
    }

    public List(int capacity)
    {
        if (capacity < 0)
            ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);

        if (capacity == 0)
            _items = s_emptyArray;
        else
            _items = new T[capacity];
    }
}

扩容： List<T> 在内部有一个存放数据的数组，当新增数据时候，如果该数组有可用，则会将数据放入数组，并将下标向后移动，如果没有足够的数组，则会进行扩容，如果创建的时候没有给定容量，第一次扩容则会使用默认的容量，如果当前有元素，则会扩容至当前容量的两倍。 可以看到扩容 是将原数组的数据拷贝到新创建的数组中

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void Add(T item)
{
    _version++;
    T[] array = _items;
    int size = _size;
    if ((uint)size < (uint)array.Length)
    {
        _size = size + 1;
        array[size] = item;
    }
    else
    {
        AddWithResize(item);
    }
}
 
// Non-inline from List.Add to improve its code quality as uncommon path
[MethodImpl(MethodImplOptions.NoInlining)]
private void AddWithResize(T item)
{
    Debug.Assert(_size == _items.Length);
    int size = _size;
    Grow(size + 1);  // 扩容
    _size = size + 1;
    _items[size] = item;
}

private void Grow(int capacity)
{
    Debug.Assert(_items.Length < capacity);

    int newcapacity = _items.Length == 0 ? DefaultCapacity : 2 * _items.Length;

    // Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow.
    // Note that this check works even when _items.Length overflowed thanks to the (uint) cast
    if ((uint)newcapacity > Array.MaxLength) newcapacity = Array.MaxLength;

    // If the computed capacity is still less than specified, set to the original argument.
    // Capacities exceeding Array.MaxLength will be surfaced as OutOfMemoryException by Array.Resize.
    if (newcapacity < capacity) newcapacity = capacity;

    Capacity = newcapacity;
}

// Gets and sets the capacity of this list.  The capacity is the size of
// the internal array used to hold items.  When set, the internal
// array of the list is reallocated to the given capacity.
public int Capacity
{
    get => _items.Length;
    set
    {
        if (value < _size)
        {
            ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
        }

        if (value != _items.Length)
        {
            if (value > 0)
            {
                T[] newItems = new T[value];
                if (_size > 0)
                {
                    Array.Copy(_items, newItems, _size);
                }
                _items = newItems;
            }
            else
            {
                _items = s_emptyArray;
            }
        }
    }
}

List<T>源码open in new window

Contributors: FHL