C#: List.Add() 实际上是如何在内部向数组添加新项的?

huangapple go评论63阅读模式
英文:

c#: How does List.Add() actually adds new item to array internally?

问题

I am curious to know how List.Add actually works? Internally, it stores items in an array, but an array can't be resized once created. So far, I can only imagine one way to do this: creating a new array, copying all the values from the old array, and resizing it. But how does this work? I am trying to recreate List.Add, but I don't know how to make it work like the real one.

英文:

I am courious to know how List.Add actually works ? internally it stores items in array. but array can't be resized once created. So far I can imagine only way could be creating a new aray and copy all the values of old array and resizing it. ut how does this work ? I am tryig to recreate List.Add but I don't know how to make it work like real one.

答案1

得分: 1

来自 源代码

// 将给定对象添加到此列表的末尾。列表的大小增加了一个。如果需要,列表的容量会加倍,然后再添加新元素。
//
public void Add(T item) {
    if (_size == _items.Length) EnsureCapacity(_size + 1);
    _items[_size++] = item;
    _version++;
}

private void EnsureCapacity(int min) {
    if (_items.Length < min) {
        int newCapacity = _items.Length == 0? _defaultCapacity : _items.Length * 2;
    // 允许列表在遇到溢出之前增长到最大可能容量(约 2G 个元素)。
    // 请注意,即使 _items.Length 溢出,此检查也能正常工作,这要归功于 (uint) 转换
    if ((uint)newCapacity > Array.MaxArrayLength) 
        newCapacity = Array.MaxArrayLength;
    if (newCapacity < min) newCapacity = min;
        Capacity = newCapacity;
}

你可以看到它只是将项目添加到内部数组,直到其大小达到。因此,并非每个项目都需要调整大小。当达到最大大小时,将以加倍的大小重新创建数组,这样你就可以在每次调整大小时添加多个项目。

英文:

From the source-code:

// 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 void Add(T item) {
    if (_size == _items.Length) EnsureCapacity(_size + 1);
    _items[_size++] = item;
    _version++;
}

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.MaxArrayLength) 
        newCapacity = Array.MaxArrayLength;
    if (newCapacity < min) newCapacity = min;
        Capacity = newCapacity;
}

You see it just adds items to the internal array until its size is reached. So not every item needs a resize. When the max size is reached, the array will be recreated with a doubled size, so you can add more than only a single item per resize.

huangapple
  • 本文由 发表于 2023年5月22日 14:45:31
  • 转载请务必保留本文链接:https://go.coder-hub.com/76303599.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定