ExtensionMethod.NET Home of 880 C#, Visual Basic, F# and Javascript extension methods

RemoveAtFast

Fast version of the RemoveAt function. Overwrites the element at the specified index with the last element in the list, then removes the last element, thus lowering the inherent O(n) cost to O(1). IMPORTANT: Intended to be used on *unordered* lists only.

Source

public static class ListExtender
{
    /// <summary>
    /// Fast version of the RemoveAt function. Overwrites the element at the specified index
    /// with the last element in the list, then removes the last element, thus lowering the 
    /// inherent O(n) cost to O(1). Intended to be used on *unordered* lists only.
    /// </summary>
    /// <param name="_list">List.</param>
    /// <param name="_index">Index of the element to be removed.</param>
    public static void RemoveAtFast<T>( this IList<T> _list, int _index )
    {
        _list[ _index ] = _list[ _list.Count - 1 ];
        _list.RemoveAt( _list.Count - 1 );
    }
}

Example

using ListExtender;

void Test()
{
    List<int> intList = new List<int>( 10000 );

    // Populate list
    for( int n = 0; n < 10000; ++n )
    {
        intList.Add( n );
    }

    // Remove all elements. Note that not a single memory 
    // xfer will be performed since internally we're 
    // always removing the last element regardless the 
    // index we passed in.
    for( int n = 0; n < 10000; ++n )
    {
        intList.RemoveAtFast( 0 );
    }
}

Author: José María Calvo Iglesias

Submitted on: 5 jun. 2009

Language: C#

Type: System.Collections.Generic.IList<T>

Views: 5407