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: 5398