[API Proposal]: Add IList<T> extension methods providing in-place update operations

[eiriktsarpalis]

Background and motivation

The List<T> type provides a number of methods providing bulk in-place updates, such as RemoveAll, RemoveRange, Reverse and Sort. The same cannot be said about IList<T> where common in-place operations are cumbersome to achieve. Consider for instance the following System.Text.Json example used in our own docs repo:

https://github.com/dotnet/docs/blob/6c6942bcb4594dc063db293e5fff33c6bea0b331/docs/standard/serialization/system-text-json/snippets/custom-contracts/IgnoreType.cs#L26-L38

A possible alternative to the above would be to roll your own extension method, but it would be even better if we shipped extension methods like that out of the box.

API Proposal

namespace System.Collections.Generic;

public partial static class CollectionExtensions
{
    public static void AddRange<T>(this IList<T> list, IEnumerable<T> collection);
    public static void InsertRange<T>(this IList<T> list, int index, IEnumerable<T> collection);
    public static void RemoveAll<T>(this IList<T> list, Predicate<T> predicate);
    public static void RemoveRange<T>(this IList<T> list, int index, int count);
    public static void Reverse<T>(this IList<T> list);

    public static void Sort<T>(this IList<T> list);
    public static void Sort<T>(this IList<T> list, Comparison<T> comparison);
    public static void Sort<T>(this IList<T> list, IComparer<T> comparer);
    public static void Sort<T>(this IList<T> list, int index, int count, IComparer<T> comparer);
}

API Usage

Removing properties of a given type in System.Text.Json can now be expressed as follows:

    public void ModifyTypeInfo(JsonTypeInfo ti)
    {
        if (ti.Kind != JsonTypeInfoKind.Object)
            return;

        ti.Properties.RemoveAll(prop => _ignoredTypes.Contains(prop.PropertyType));
    }
}

Alternative Designs

• Should we consider exposing as DIMs?
• Should the Sort implementation be stable? Or match List/Array.Sort semantics?
• Should we include BinarySearch extension methods?

Risks

No response

Related to dotnet/core#2199

Tagging subscribers to this area: @dotnet/area-system-collections
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Background and motivation

The List<T> type provides a number of methods providing bulk in-place updates, such as RemoveAll, RemoveRange, Reverse and Sort. The same cannot be said about IList<T> where common in-place operations are cumbersome to achieve. Consider for instance the following System.Text.Json example used in our own docs repo:

https://github.com/dotnet/docs/blob/6c6942bcb4594dc063db293e5fff33c6bea0b331/docs/standard/serialization/system-text-json/snippets/custom-contracts/IgnoreType.cs#L26-L38

A possible alternative to the above would be to roll your own extension method, but it would be even better if we shipped extension methods like that out of the box.

API Proposal

namespace System.Collections.Generic;

public partial static class CollectionExtensions
{
    public static void RemoveAll<T>(this IList<T> list, Predicate<T> predicate);
    public static void RemoveRange<T>(this IList<T> list, int index, int count);
    public static void Reverse<T>(this IList<T> list);

    // List.Sort is not stable -- should this extension be stable?
    public static void Sort<T>(this IList<T> list);
    public static void Sort<T>(this IList<T> list, Comparison<T> comparison);
    public static void Sort<T>(this IList<T> list, IComparer<T> comparer);
    public stsatic void Sort<T>(this IList<T> list, int index, int count, IComparer<T> comparer);

    // TOCONSIDER BinarySearch extension methods?
}

API Usage

Removing properties of a given type in System.Text.Json can now be expressed as follows:

    public void ModifyTypeInfo(JsonTypeInfo ti)
    {
        if (ti.Kind != JsonTypeInfoKind.Object)
            return;

        ti.Properties.RemoveAll(prop => _ignoredTypes.Contains(prop.PropertyType));
    }
}

Alternative Designs

• Should we consider exposing as DIMs?
• Should the Sort implementation be stable? Or match List/Array.Sort semantics?
• Should we include BinarySearch extension methods?

Risks

No response

Author:	eiriktsarpalis
Assignees:	-
Labels:	api-suggestion, area-System.Collections
Milestone:	-

[stephentoub]

Should the Sort implementation be stable? Or match List/Array.Sort semantics?

If we add such extension methods, they should have the same semantics as List<T>. Otherwise, changing code from:

IList<T> list = new List<T>() { ... };
list.Sort(...);

to:

List<T> list = new List<T>() { ... };
list.Sort(...);

is a very subtle and unexpected source of bugs.

If we update List<T>/Array.Sort to be stable, then such extensions should follow suit as well.

[eiriktsarpalis]

If we update List/Array.Sort to be stable

Assuming it doesn't regress perf we could do that, to my knowledge there is no stable in-place sorting implementation available.

[eiriktsarpalis]

And if not, we might consider using a different name, e.g. StableSort.

[stephentoub]

Assuming it doesn't regress perf we could do that, to my knowledge there is no stable in-place sorting implementation available.

There's been a long discussion of this in #68436.

[jkotas]

How are the Sort methods expected to be implemented? How efficient is the implementation going to be and is it going to require yet another copy of the whole Sort algorithm?

In-place sorting of IList will require a virtual method call for each element get and set. It expect that it is often going to be faster to convert the IList to array first and then sort the array.