[API Proposal]: Add `OrderedSet<T>`

Start with the API Proposal and API Usage sections, then compare the proposed OrderedSet surface with existing collection APIs in the runtime. No files or tests are named in the issue. Done means the API design, ordering semantics, and implementation scope are agreed and validated.

Background and motivation

Bringing this issue back since it was closed without being resolved. (https://github.com/dotnet/runtime/issues/24828 and https://github.com/dotnet/corefxlab/issues/2457):

"Sometimes I've come across places when needing a HashSet where the insertion order of the elements is important to me. Unfortunately, .NET does not have an OrderedSet class even though it has a SortedSet which to me has less value but perhaps not to others. This has led to users rolling their own solution, typically by using a combination of a LinkedList and Dictionary field resulting in the worst of both worlds in terms of performance and resulting in larger memory usage, and even worse sometimes users instead rely on implementation details of HashSet for ordering which is quite dangerous."

API Proposal

namespace System.Collections.Generic;

public class OrderedSet<T> : ISet<T>, IReadOnlySet<T>, IList<T>, IReadOnlyList<T>
{
    public struct Enumerator : IDisposable, IEnumerator, IEnumerator<T> {
        public T Current { get; }
        public void Dispose();
        public bool MoveNext();
    }
    public OrderedSet();
    public OrderedSet(int capacity);
    public OrderedSet(IEqualityComparer<T> comparer);
    public OrderedSet(int capacity, IEqualityComparer<T> comparer);
    public OrderedSet(IEnumerable<T> collection);
    public OrderedSet(IEnumerable<T> collection, IEqualityComparer<T> comparer);
    public IEqualityComparer<T> Comparer { get; }
    public int Count { get; }
    public T this[int index] { get; set; }
    public bool Add(T item);
    public void Clear();
    public bool Contains(T item);
    public void CopyTo(T[] array);
    public void CopyTo(T[] array, int arrayIndex);
    public void CopyTo(T[] array, int arrayIndex, int count);
    public void ExceptWith(IEnumerable<T> other);
    public OrderedSet<T>.Enumerator GetEnumerator();
    public int IndexOf(T item);
    public bool Insert(int index, T item);
    public void IntersectWith(IEnumerable<T> other);
    public bool IsProperSubsetOf(IEnumerable<T> other);
    public bool IsProperSupersetOf(IEnumerable<T> other);
    public bool IsSubsetOf(IEnumerable<T> other);
    public bool IsSupersetOf(IEnumerable<T> other);
    public bool Overlaps(IEnumerable<T> other);
    public bool Remove(T item);
    public void RemoveAt(int index);
    public bool SetEquals(IEnumerable<T> other);
    public void SymmetricExceptWith(IEnumerable<T> other);
    public int TrimExcess();
    public bool TryGetValue(T equalValue, out T actualValue);
    public void UnionWith(IEnumerable<T> other);
}

API Usage

var triangles = new List<(int A, int B, int C)>();
var vertices = new OrderedSet<Vector3>();

var vert0 = new Vector3(1f);
var vert1 = new Vector3(2f);
var vert2 = new Vector3(3f);

var a = vertices.IndexOf(vert0);
if (a == -1)
{
    a = vertices.Count;
    vertices.Add(vert0);
}

var b = vertices.IndexOf(vert1);
if (b == -1)
{
    b = vertices.Count;
    vertices.Add(vert1);
}

var c = vertices.IndexOf(vert2);
if (c == -1)
{
    c = vertices.Count;
    vertices.Add(vert2);
}

// Add triangle to list now that we have unique vertex indices
triangles.Add((a, b, c));

Alternative Designs

No response

Risks

No response