Filtering collections in C#

I am looking for a very fast way to filter down a collection in C#. I am currently using generic List<object> collections, but am open to using other structures if they perform better.

Currently, I am just creating a new List<object> and looping thru the original list. If the filtering criteria matches, I put a copy into the new list.

Is there a better way to do this? Is there a way to filter in place so there is no temporary list required?

If you're using C# 3.0 you can use linq, which is way better and way more elegant:

List<int> myList = GetListOfIntsFromSomewhere();

// This will filter ints that are not > 7 out of the list; Where returns an
// IEnumerable<T>, so call ToList to convert back to a List<T>.
List<int> filteredList = myList.Where(x => x > 7).ToList();

If you can't find the .Where, that means you need to import using System.Linq; at the top of your file.

Here is a code block / example of some list filtering using three different methods that I put together to show Lambdas and LINQ based list filtering.

#region List Filtering

static void Main(string[] args)
{
    ListFiltering();
    Console.ReadLine();
}

private static void ListFiltering()
{
    var PersonList = new List<Person>();

    PersonList.Add(new Person() { Age = 23, Name = "Jon", Gender = "M" }); //Non-Constructor Object Property Initialization
    PersonList.Add(new Person() { Age = 24, Name = "Jack", Gender = "M" });
    PersonList.Add(new Person() { Age = 29, Name = "Billy", Gender = "M" });

    PersonList.Add(new Person() { Age = 33, Name = "Bob", Gender = "M" });
    PersonList.Add(new Person() { Age = 45, Name = "Frank", Gender = "M" });

    PersonList.Add(new Person() { Age = 24, Name = "Anna", Gender = "F" });
    PersonList.Add(new Person() { Age = 29, Name = "Sue", Gender = "F" });
    PersonList.Add(new Person() { Age = 35, Name = "Sally", Gender = "F" });
    PersonList.Add(new Person() { Age = 36, Name = "Jane", Gender = "F" });
    PersonList.Add(new Person() { Age = 42, Name = "Jill", Gender = "F" });

    //Logic: Show me all males that are less than 30 years old.

    Console.WriteLine("");
    //Iterative Method
    Console.WriteLine("List Filter Normal Way:");
    foreach (var p in PersonList)
        if (p.Gender == "M" && p.Age < 30)
            Console.WriteLine(p.Name + " is " + p.Age);

    Console.WriteLine("");
    //Lambda Filter Method
    Console.WriteLine("List Filter Lambda Way");
    foreach (var p in PersonList.Where(p => (p.Gender == "M" && p.Age < 30))) //.Where is an extension method
        Console.WriteLine(p.Name + " is " + p.Age);

    Console.WriteLine("");
    //LINQ Query Method
    Console.WriteLine("List Filter LINQ Way:");
    foreach (var v in from p in PersonList
                      where p.Gender == "M" && p.Age < 30
                      select new { p.Name, p.Age })
        Console.WriteLine(v.Name + " is " + v.Age);
}

private class Person
{
    public Person() { }
    public int Age { get; set; }
    public string Name { get; set; }
    public string Gender { get; set; }
}

#endregion

List<T> has a FindAll method that will do the filtering for you and return a subset of the list.

MSDN has a great code example here: <http://msdn.microsoft.com/en-us/library/aa701359(VS.80).aspx>

EDIT: I wrote this before I had a good understanding of LINQ and the Where() method. If I were to write this today i would probably use the method Jorge mentions above. The FindAll method still works if you're stuck in a .NET 2.0 environment though.

You can use IEnumerable to eliminate the need of a temp list.

public IEnumerable<T> GetFilteredItems(IEnumerable<T> collection)
{
    foreach (T item in collection)
    if (Matches<T>(item))
    {
        yield return item;
    }
}

where Matches is the name of your filter method. And you can use this like:

IEnumerable<MyType> filteredItems = GetFilteredItems(myList);
foreach (MyType item in filteredItems)
{
    // do sth with your filtered items
}

This will call GetFilteredItems function when needed and in some cases that you do not use all items in the filtered collection, it may provide some good performance gain.

To do it in place, you can use the RemoveAll method of the "List<>" class along with a custom "Predicate" class...but all that does is clean up the code... under the hood it's doing the same thing you are...but yes, it does it in place, so you do same the temp list.

You can use the FindAll method of the List, providing a delegate to filter on. Though, I agree with @IainMH that it's not worth worrying yourself too much unless it's a huge list.

>> If you're using C# 3.0 you can use linq

Or, if you prefer, use the special query syntax provided by the C# 3 compiler:

var filteredList = from x in myList
                   where x > 7
                   select x;

Using LINQ is relatively much slower than using a predicate supplied to the Lists FindAll method. Also be careful with LINQ as the enumeration of the list is not actually executed until you access the result. This can mean that, when you think you have created a filtered list, the content may differ to what you expected when you actually read it.

If your list is very big and you are filtering repeatedly - you can sort the original list on the filter attribute, binary search to find the start and end points.

Initial time O(n*log(n)) then O(log(n)).

Standard filtering will take O(n) each time.