Given a custom generic class that stores a List how do I prevent adding an object of type T more than once to the List?

Question

So this is the code that I have tried, but it adds the same object more than once:

namespace TestComparison
{
    public interface IAddable
    {
        int RandomIntValue { get; set; } // often Times this value will repeat.
    }

    public class AdditionManager<T> where T : IAddable
    {
        private List<T> addables;

        public AdditionManager()
        {
            addables = new List<T>();
        }

        public void Add(T _addable)
        {
            if (!addables.Contains(_addable))
            {
                addables.Add(_addable);
            }
        }

    }

    public class TestAddable : IAddable
    {
        public int RandomIntValue { get; set; }
        public Data UniqueData = new Data() { UniqueId = 10023 }; // This is what really make each item unique
    }

    public class Data
    {
        public int UniqueId { get; set; }
    }
}

I've heard about the IEqualityComparer and I have implemented it in non-generic classes, but I'm not quite sure how to implement it here.

Answer 1

Your problem indeed seems to be related to a missing IEqualityComparer.

Imagine the following:

class TestClass
{
    public int x;
}

class Program
{
    static void Main(string[] args)
    {
        TestClass nine = new TestClass() { x = 9 };
        TestClass twelve = new TestClass() { x = 12 };
        TestClass anotherNine = new TestClass() { x = 9 };

        Console.WriteLine(nine == twelve);
        Console.WriteLine(nine == anotherNine);
    }
}

What will this program output? The "surprising" answer is that it outputs False two times. This is because the objects are compared to each other, not the members of the objects. To achieve an actual value comparison which will compare the objects by their content instead of their reference you need to consider quite a few things. If you want to be really complete, you need IComparable, IEquality, GetHashcode etc etc. It's very easy to make a mistake there.

But since C# 9.0 there's a new type which can be used instead of class. The type is record. This new record type has all the stuff I mentioned implemented by default. If you want to go the long route, I suggest you to look into the new record type and what it actually is.

This means all you need to do is change the type of your TestAddable and Data from class to record and you should be fine.

Answer 2

You can use dependency injection to provide you with generic implementation. Doing so you'll need to provide the custom IEqualityComparer<T> implementation that you want at the point of generic object's construction.

public class AdditionManager<T> where T : IAddable
{
    private List<T> addables;
    private IEqualityComparer<T> comparer;

    public AdditionManager()
        : this (EqualityComparer<T>.Default)
    { }

    public AdditionManager(IEqualityComparer<T> _comparer)
    {
        addables = new List<T>();
        comparer = _comparer;
    }

    public void Add(T _addable)
    {
         if (!addables.Contains(_addable, comparer))
         {
             addables.Add(_addable);
         }
    }
}

However, if you are looking for you list of addables to be unique based on some constraint, I would not use the above implementation for performance reasons. As the List<T>.Contains check will become slower as the list grows larger.

If the order of the list does not matter change your List<T> to a HashSet<T>. HashSet<T>.Contains will be just as quick as a Dictionary<TKey, TValue> lookup. But this call can be avoided altogether with HashSet<T> as the Add call will first check to see if the item is in the set before adding it, and return true or false to indicate it was added or not`

So if the order of addables is of not concern, then I would use the following implementation.

public class AdditionManager<T> where T : IAddable
{
    private HashSet<T> addables;

    public AdditionManager()
        : this(EqualityComparer<T>.Default)
    { }

    public AdditionManager(IEqualityComparer<T> _comparer)
    {
        addables = new HashSet<T>(_comparer);
    }

    public void Add(T _addable)
    {
        // will not add the item to the HashSet if it is already present
        addables.Add(_addable);
    }
}

If you need to maintain the order of addables then I suggest maintaining the list of objects in both a HashSet<T> and List<T>. This will provide you with the performance of the above implementation, but maintain the addition order on your items. In this implementation any of the operations you need to perform, do them against the List<T> and only use the HashSet<T> to make sure the item isn't already present when adding to List<T> If you are going to have some type of Remove operation, make sure to remove the item from both the HashSet<T> and List<T>

public class AdditionManager<T> where T : IAddable
{
    private HashSet<T> set;
    private List<T> list;

    public AdditionManager()
        : this(EqualityComparer<T>.Default)
    { }

    public AdditionManager(IEqualityComparer<T> _comparer)
    {
        set = new HashSet<T>(_comparer);
        list = new List<T>();
    }

    public void Add(T _addable)
    {
        if (set.Add(_addable))
            list.Add(_addable);
    }
}

To create this object using TestAddable you'll need an IEqualityComparer<TestAddable> like the following. As others have suggested, the field(s) you are doing your comparison on should be made immutable, as a mutable key is going to cause bugs.

public class TestAddableComparer : IEqualityComparer<TestAddable>
{
    public bool Equals(TestAddable x, TestAddable y)
    {
        return x.UniqueData.Equals(y.UniqueData);
    }

    public int GetHashCode(TestAddable obj)
    {
        // since you are only comparing use `UniqueData` use that here for the hash code
        return obj.UniqueData.GetHashCode();
    }
}

Then to create the manager object do:

var additionManager = new AdditionManager<TestAddable>(new TestAddableComparer());

Answer 3

You can use a dictionary instead of a list. If you need a list in other parts of your code, it is easy to add a property that exposes the Values only.

public class AdditionManager<T> where T : IAddable
{
    private Dictionary<int,T> addables;

    public AdditionManager()
    {
        addables = new Dictionary<int,T>();
    }

    public void Add(T _addable)
    {
        if (!addables.ContainsKey(_addable.Data.RandomIntValue))
        {
            addables.Add(_addable.Data.RandomIntValue, _addable);
        }
    }

    public Dictionary<int,T>.ValueCollection Values => _addables.Values;
}