英文:
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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论