BCL Refresher: List Predicates [Inbar Gazit]
This time I’m going to focus on one class in this blog post. System.Collections.Generic.List<T> contains some special methods that exist on this type. Those methods take a System.Predicate which is essentially a delegate that allows us to filter based on a certain criteria. This means we can selectively carry out operations only on those member that meet the criteria we choose. Let’s see an example so that we can better understand this. Say we have a List<String> names; object representing a bunch of names. If we want to remove from the list all the names that begin with “a” we may have to write something like this:
for (int i = names.Count - 1; i >= 0; i--) {
if (names[i].StartsWith("a", StringComparison.OrdinalIgnoreCase)) {
names.RemoveAt(i);
}
}
This works well but we can do a little better using predicates. First, we have to define the static method to be the predicate to validate that a name starts with an “a”. This would be:
static bool StartsWithA(string name) {
return name.StartsWith("a", StringComparison.OrdinalIgnoreCase);
}
Which is essentially the same as the statement we had above. Separating it into a static method has a few advantages, practically the ability to reuse the same predicate in various places and being able to separate the logic for other uses. Now once we have this predicate removing all names that start with an “a” is as simple as calling names.RemoveAll(StartsWithA);
You can still write the whole thing in one line if you so choose by using an anonymous delegate this way:
names.RemoveAll(delegate(string name) {
return (name.StartsWith("a", StringComparison.OrdinalIgnoreCase));
});
Now, let’s take a different example and explore a different method. Say we have a list of integers and we want to find all the primes in the list. Given that we have List<Int32> numbers; we can use the numbers.FindAll(IsPrime); to get back the filtered list of primes. This assumes we have a predicate in this form:
static bool IsPrime(Int32 number) {
// TODO: Implement this predicate...
}
Some other useful predicates include:
Finding elements
Find — is used to find the first element that fulfils the condition. If none are found it returns the default value for the given type T (the value you get by calling the default constructor).
FindIndex — returns the first index of an item matching the condition. There are also two additional overloads that are used to start from a certain index or count multiple occurrences.
FindLast — returns the last element in the list matching the condition. Again returning the default value for T if none were found.
FindLastIndex — returns the last index of an item matching the condition. Again, it has 3 overloads.
Evaluating conditions
TrueForAll — returns true if the predicate is met for all elements in the list. You could easily use many of the other methods discussed above to obtain this information but this is a little more elegant.
Exists — this could have been called TrueForAtLeastOne as it basically determines if there exists an element in the list that meets the condition determined by the predicate.
Now, let’s take a look at how to combine our knowledge of predicates with a new C# language feature of 3.5 called extension methods. We could extend IList<T> to have a couple of new methods that take delegates. The first one we called ReplaceIf() which will replace every element that meets the predicate condition with a certain element. This is how it looks like:
public static void ReplaceIf<T>(this IList<T> list, Predicate<T> predicate, T replacement) {
for (int i = 0; i < list.Count; i++) {
if (predicate(list[i])) {
list[i] = replacement;
}
}
}
Since this is an extension method, the first argument has the “this” keyword following by the type we want to extend. The second argument is the predicate that we’ll test and third is the replacement element we’ll use to replace all items in the list. Note that this is a generic method since we’re extending IList<T> for every possible type T so we need to have T available as a generic type in the method body. Now with the new LINQ types we don’t really need to use Predicate anymore. We have uber-generic functions and method delegates called Func and Action that we can use for any purpose. I would recommend using them. So now it would then look like this:
public static void ReplaceIf<T>(this IList<T> list, Func<T, bool> predicate, T replacement) {
for (int i = 0; i < list.Count; i++) {
if (predicate(list[i])) {
list[i] = replacement;
}
}
}
In the second example we’ll use a converter to convert the element that meet the predicate condition instead of simply replacing them with a constant.
public static void ConvertIf<T>(this IList<T> list, Predicate<T> predicate, Converter<T, T> convert) {
for (int i = 0; i < list.Count; i++) {
T item = list[i];
if (predicate(item)) {
list[i] = convert(item);
}
}
}
This is very similar to the previous example only instead of using the fixed value t we’re suing a Converter to convert the value to something else.
Again, with LINQ we would use Func instead of Converter and Predicate, and this would be instead:
public static void ConvertIf<T>(this IList<T> list, Func<T, bool> predicate, Func<T, T> convert) {
for (int i = 0; i < list.Count; i++) {
T item = list[i];
if (predicate(item)) {
list[i] = convert(item);
}
}
}
Now, if we have a List<Double> ld and we want to invert all the numbers in the list we can write it this way:
ld.ConvertIf(delegate(double d) { return (d != 0); }, delegate(double d) { return 1 / d; });
The code can be expressed even more succinctly using lambda expressions, another new C# 3.0 language feature included as part of .NET 3.5:
ld.ConvertIf(d => d != 0, d => 1 / d);
For more information about Collections please read the recent MSDN article I wrote about Collections Best Practices.