Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[API Proposal]: Add OrderedSet<T> #110882

Open
ptasev opened this issue Dec 21, 2024 · 1 comment
Open

[API Proposal]: Add OrderedSet<T> #110882

ptasev opened this issue Dec 21, 2024 · 1 comment
Labels
api-suggestion Early API idea and discussion, it is NOT ready for implementation area-System.Collections
Milestone

Comments

@ptasev
Copy link

ptasev commented Dec 21, 2024

Background and motivation

Bringing this issue back since it was closed without being resolved. (#24828 and dotnet/corefxlab#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

@ptasev ptasev added the api-suggestion Early API idea and discussion, it is NOT ready for implementation label Dec 21, 2024
@dotnet-policy-service dotnet-policy-service bot added the untriaged New issue has not been triaged by the area owner label Dec 21, 2024
Copy link
Contributor

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

@eiriktsarpalis eiriktsarpalis removed the untriaged New issue has not been triaged by the area owner label Dec 21, 2024
@eiriktsarpalis eiriktsarpalis added this to the Future milestone Dec 21, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
api-suggestion Early API idea and discussion, it is NOT ready for implementation area-System.Collections
Projects
None yet
Development

No branches or pull requests

2 participants