Which algorithm is used in List to dynamically

问题:

Now I have an algorithm for dynamically allocating memory on an array:

• If array is full I create a new array of twice the size, and copy items.
• If array is one-quarter full I create a new array of half the size, and copy items.

This is fairly fast algorithm for dynamic memory allocation despite the extra over-head of copying the elements to the newly allocated array.

1. What is the faster, List<T> or such an algorithm based on an array? What would you recommend to use?

2. does List<T> use simple array as internal data structure?

回答1:

TO answer your question:

It is true, C#'s List<T> implementation uses an internal array that is

1. Serializable
2. Thread-safe
3. Implements IEnumerable<T> (which means it can be LINQ Queried, foreached etc)
4. Binary Searched

and so on

Hence, I would ask you to use List<T> instead of your own List.

Oh and btw, if you want the source code of List<T> from Microsoft, then here it is

List.cs

EDIT

The source code of EnsureCapacity in List<T> is:

    // Ensures that the capacity of this list is at least the given minimum
    // value. If the currect 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;
            if (newCapacity < min) newCapacity = min;
            Capacity = newCapacity;
        }
    }

回答2:

Unless you have a specific reason to believe otherwise, it's almost universally a good idea to use the provided libraries that come with C#. Those implementations are well-implemented, well-debugged, and well-tested.

The data structure you're describing is a standard implementation of a dynamic array data structure, and most languages use this as their default list implementation. Looking over the documentation for List<T>, it seems like List<T> uses this implementation, since its documentation has references to an internal capacity and guarantees O(1) append as long as the size is less than the capacity.

In short, avoid reinventing the wheel unless you have to.

Hope this helps!

回答3:

List<T> uses an array internally, and it uses a similar strategy as you - it doubles the size of the array if the length would go over the length of the array. However, it doesn't make it smaller should the size be way smaller.

The relevant method in mscorlib:

private void EnsureCapacity(int min)
{
    if (this._items.Length < min)
    {
        int num = (this._items.Length == 0) ? 4 : (this._items.Length * 2);
        if (num < min)
        {
            num = min;
        }
        this.Capacity = num;
    }
}

The resizing of the array actually happens in the setter of List<T>.Capacity.

回答4:

Yes, List<T> uses a T[] internally to hold your objects.

As far as I remember from the .NET 4.0 source code, before adding new objects, it ensures that the array has enough capacity to hold the new number of objects. If the existing array cannot hold the new number of objects, it is replaced by a new array of double the size and all the objects and all the existing references are copied to the new array.

回答5:

No need to reinvent the wheel.

From MSDN:

Capacity is the number of elements that the List<(Of <(T>)>) can store before resizing is required, while Count is the number of elements that are actually in the List<(Of <(T>)>).

Capacity is always greater than or equal to Count. If Count exceeds Capacity while adding elements, the capacity is increased by automatically reallocating the internal array before copying the old elements and adding the new elements.

The capacity can be decreased by calling the TrimExcess method or by setting the Capacity property explicitly. When the value of Capacity is set explicitly, the internal array is also reallocated to accommodate the specified capacity, and all the elements are copied.

Retrieving the value of this property is an O(1) operation; setting the property is an O(n) operation, where n is the new capacity.

回答6:

That's basically what List<T> (and many other languages' dynamic arrays, for that matter) does as well. The resizing factors may be different, and I think it doesn't shrink the backing array on its own when removing elements - but there's TrimToSize and you can set Capacity yourself, which probably allows more efficient strategies if client code uses this feature well. But basically, it's asymptotically equivalent.

As for which one to use: Unless you have cold, hard data that List<T> is suboptimal for your use case and that the difference matters (you obviously don't have this knowledge yet), you should use it. Your own implementation will be buggy, less feature-rich (cf. IEnumerable<T>, IList<T>, numerous methods), less optimized, less widely recognizable, not accepted by other libraries (so you may have to create expensive copies, or at least do more work than with List<T> to interact), etc. and there is most likely absolutely nothing to be gained.