Is there a built-in method to compare collections?

Question

I would like to compare the contents of a couple of collections in my Equals method. I have a Dictionary and an IList. Is there a built-in method to do this?

Edited: I want to compare two Dictionaries and two ILists, so I think what equality means is clear - if the two dictionaries contain the same keys mapped to the same values, then they're equal.

Softball

Enumerable.SequenceEqual and ISet.SetEquals provide versions of this functionality. If you want to be order-agnostic and work with collections that have duplicates, you'll need to roll your own. Check out the implementation suggested in this post – Narco

As mentioned in a comment below, for 99% of cases you can rely on NUnit/MSTest method CollectionAssert.AreEquivalent. – Misery

@alexlomba87 That function is worth mentioning but is there something a bit off about relying on a testing assembly for production code? – Pasto

Answer 1

Enumerable.SequenceEqual

Determines whether two sequences are equal by comparing their elements by using a specified IEqualityComparer(T).

You can't directly compare the list & the dictionary, but you could compare the list of values from the Dictionary with the list

Dye

The problem is that SequenceEqual expects the elements to be in the same order. The Dictionary class does not guarantee the order of keys or values when enumerating, so if you're going to use SequenceEqual, you have to sort the .Keys and .Values first! – Littles

@Orion: ... unless you want to detect ordering differences, of course:-) – Pin

@schoetbi: Why would you want to detect ordering differences in a container that doesn't guarantee order? – Gains

@Matti: So whats ElementAt for? msdn.microsoft.com/en-us/library/bb299233.aspx – Pin

@schoetbi: It's for taking a certain element out of an IEnumerable. However, a dictionary does not guarantee order, so .Keys and .Values may return the keys and values in any order they feel like, and that order is likely to change as the dictionary is modified as well. I suggest you read up on what a Dictionary is and what it isn't. – Gains

MS' TestTools and NUnit provide CollectionAssert.AreEquivalent – Woodshed

See this example where I think the OP would want the dictionaries to be equal and SequenceEqual method returns false. – Maidservant

@OrionEdwards it's not a problem, it's a feature :). Say in Natural Language Date Time class I want to compare in exactly the same order, if order is different it's not the same sentence :). – Newcomb

THIS is a proper answer, not the CollectionAssert that people keep suggesting, that doesn't return anything and is likely unsuitable for OP. Plus, that's a testing tool, hence why it's in test packages like NUnit and MSTest... – Unshackle

Answer 2

As others have suggested and have noted, SequenceEqual is order-sensitive. To solve that, you can sort the dictionary by key (which is unique, and thus the sort is always stable) and then use SequenceEqual. The following expression checks if two dictionaries are equal regardless of their internal order:

dictionary1.OrderBy(kvp => kvp.Key).SequenceEqual(dictionary2.OrderBy(kvp => kvp.Key))

---

EDIT: As pointed out by Jeppe Stig Nielsen, some object have an IComparer<T> that is incompatible with their IEqualityComparer<T>, yielding incorrect results. When using keys with such an object, you must specify a correct IComparer<T> for those keys. For example, with string keys (which exhibit this issue), you must do the following in order to get correct results:

dictionary1.OrderBy(kvp => kvp.Key, StringComparer.Ordinal).SequenceEqual(dictionary2.OrderBy(kvp => kvp.Key, StringComparer.Ordinal))

Rani

What if the key type will not CompareTo? Your solution will explode then. An what if the key type has a default comparer which is incompatible with its default equality comparer? This is the case for string, you know. As an example these dictionaries (with implicit default equality comparers) will fail your test (under all culture infos I am aware of): var dictionary1 = new Dictionary<string, int> { { "Strasse", 10 }, { "Straße", 20 }, }; var dictionary2 = new Dictionary<string, int> { { "Straße", 20 }, { "Strasse", 10 }, }; – Tess

@JeppeStigNielsen: As for the incompatibility between IComparer and IEqualityComparer - I wasn't aware of this issue, very interesting! I updated the answer with a possible solution. About the lack of CompareTo, I think the developer should make sure the delegate provided to the OrderBy() method returns something comparable. I think this is true for any use or OrderBy(), even outside of dictionary comparisons. – Rani

Answer 3

In addition to the mentioned SequenceEqual, which

is true if two lists are of equal length and their corresponding elements compare equal according to a comparer

(which may be the default comparer, i.e. an overriden Equals())

it is worth mentioning that in .Net4 there is SetEquals on ISet objects, which

ignores the order of elements and any duplicate elements.

So if you want to have a list of objects, but they don't need to be in a specific order, consider that an ISet (like a HashSet) may be the right choice.

Beaton

Be warry that you can use SetEquals to compare content of two enumerables only if you can guarantee that their content values are distinct. Otherwise performing SetEquals on [1, 2, 2, 3] and [1, 2, 3, 3, 3] will return true when you probably don't want it to. – Fachanan

Answer 4

Take a look at the Enumerable.SequenceEqual method

var dictionary = new Dictionary<int, string>() {{1, "a"}, {2, "b"}};
var intList = new List<int> {1, 2};
var stringList = new List<string> {"a", "b"};
var test1 = dictionary.Keys.SequenceEqual(intList);
var test2 = dictionary.Values.SequenceEqual(stringList);

Im

This is not reliable because SequenceEqual expects the values to come out of the dictionary in a reliable order - The dictionary makes no such guarantees about order, and dictionary.Keys could well come out as [2, 1] instead of [1, 2] and your test would fail – Littles

Answer 5

This is not directly answering your questions, but both the MS' TestTools and NUnit provide

 CollectionAssert.AreEquivalent

which does pretty much what you want.

Woodshed

This doesn't return anything though, like bool. It will only throw an exception if the collections aren't equal. – Unshackle

Answer 6

I didn't know about Enumerable.SequenceEqual method (you learn something every day....), but I was going to suggest using an extension method; something like this:

    public static bool IsEqual(this List<int> InternalList, List<int> ExternalList)
    {
        if (InternalList.Count != ExternalList.Count)
        {
            return false;
        }
        else
        {
            for (int i = 0; i < InternalList.Count; i++)
            {
                if (InternalList[i] != ExternalList[i])
                    return false;
            }
        }

        return true;

    }

Interestingly enough, after taking 2 seconds to read about SequenceEqual, it looks like Microsoft has built the function I described for you.

Isogloss

Answer 7

.NET Lacks any powerful tools for comparing collections. I've developed a simple solution you can find at the link below:

http://robertbouillon.com/2010/04/29/comparing-collections-in-net/

This will perform an equality comparison regardless of order:

var list1 = new[] { "Bill", "Bob", "Sally" };
var list2 = new[] { "Bob", "Bill", "Sally" };
bool isequal = list1.Compare(list2).IsSame;

This will check to see if items were added / removed:

var list1 = new[] { "Billy", "Bob" };
var list2 = new[] { "Bob", "Sally" };
var diff = list1.Compare(list2);
var onlyinlist1 = diff.Removed; //Billy
var onlyinlist2 = diff.Added;   //Sally
var inbothlists = diff.Equal;   //Bob

This will see what items in the dictionary changed:

var original = new Dictionary<int, string>() { { 1, "a" }, { 2, "b" } };
var changed = new Dictionary<int, string>() { { 1, "aaa" }, { 2, "b" } };
var diff = original.Compare(changed, (x, y) => x.Value == y.Value, (x, y) => x.Value == y.Value);
foreach (var item in diff.Different)
  Console.Write("{0} changed to {1}", item.Key.Value, item.Value.Value);
//Will output: a changed to aaa

Tart

Of course .NET has powerful tools for comparing collections (they are set-based operations). .Removed is the same as list1.Except(list2), .Added is list2.Except(list1), .Equal is list1.Intersect(list2) and .Different is original.Join(changed, left => left.Key, right => right.Key, (left, right) => left.Value == right.Value). You can do almost any comparison with LINQ. – Rani

Correction: .Different is original.Join(changed, left => left.Key, right => right.Key, (left, right) => new { Key = left.Key, NewValue = right.Value, Different = left.Value == right.Value).Where(d => d.Different). And you can even add OldValue = left.Value if you need the old value too. – Rani

@AllonGuralnek your suggestions are good, but they don't handle the case where the List is not a true set - where the list contains the same object multiple times. Comparing { 1, 2 } and { 1, 2, 2 } would return nothing added/removed. – Hasin

@CrispinH Archive.org is Robert Bouillon's (and your) friend. ;^) – Hills

Answer 8

To compare collections you can also use LINQ. Enumerable.Intersect returns all pairs that are equal. You can comparse two dictionaries like this:

(dict1.Count == dict2.Count) && dict1.Intersect(dict2).Count() == dict1.Count

The first comparison is needed because dict2 can contain all the keys from dict1 and more.

You can also use think of variations using Enumerable.Except and Enumerable.Union that lead to similar results. But can be used to determine the exact differences between sets.

Enoch

Answer 9

For ordered collections (List, Array) use SequenceEqual

for HashSet use SetEquals

for Dictionary you can do:

namespace System.Collections.Generic {
  public static class ExtensionMethods {
    public static bool DictionaryEquals<TKey, TValue>(this IReadOnlyDictionary<TKey, TValue> d1, IReadOnlyDictionary<TKey, TValue> d2) {
      if (object.ReferenceEquals(d1, d2)) return true; 
      if (d2 is null || d1.Count != d2.Count) return false;
      foreach (var (d1key, d1value) in d1) {
        if (!d2.TryGetValue(d1key, out TValue d2value)) return false;
        if (!d1value.Equals(d2value)) return false;
      }
      return true;
    }
  }
}

(A more optimized solution will use sorting but that will require IComparable<TValue>)

Glioma

Answer 10

How about this example:

 static void Main()
{
    // Create a dictionary and add several elements to it.
    var dict = new Dictionary<string, int>();
    dict.Add("cat", 2);
    dict.Add("dog", 3);
    dict.Add("x", 4);

    // Create another dictionary.
    var dict2 = new Dictionary<string, int>();
    dict2.Add("cat", 2);
    dict2.Add("dog", 3);
    dict2.Add("x", 4);

    // Test for equality.
    bool equal = false;
    if (dict.Count == dict2.Count) // Require equal count.
    {
        equal = true;
        foreach (var pair in dict)
        {
            int value;
            if (dict2.TryGetValue(pair.Key, out value))
            {
                // Require value be equal.
                if (value != pair.Value)
                {
                    equal = false;
                    break;
                }
            }
            else
            {
                // Require key be present.
                equal = false;
                break;
            }
        }
    }
    Console.WriteLine(equal);
}

Courtesy : https://www.dotnetperls.com/dictionary-equals

Faceless

value != pair.Value is doing reference comparison, use Equals instead – Glioma

Answer 11

No, because the framework doesn't know how to compare the contents of your lists.

Have a look at this:

http://blogs.msdn.com/abhinaba/archive/2005/10/11/479537.aspx

Superstructure

Isn't there already several options to tell the framework how to compare the elements? IComparer<T>, overriding object.Equals, IEquatable<T>, IComparable<T> ... – Huneycutt

Answer 12

public bool CompareStringLists(List<string> list1, List<string> list2)
{
    if (list1.Count != list2.Count) return false;

    foreach(string item in list1)
    {
        if (!list2.Contains(item)) return false;
    }

    return true;
}

Panslavism

Answer 13

There wasn't, isn't and might not be, at least I would believe so. The reason behind is collection equality is probably an user defined behavior.

Elements in collections are not supposed to be in a particular order though they do have an ordering naturally, it's not what the comparing algorithms should rely on. Say you have two collections of:

{1, 2, 3, 4}
{4, 3, 2, 1}

Are they equal or not? You must know but I don't know what's your point of view.

Collections are conceptually unordered by default, until the algorithms provide the sorting rules. The same thing SQL server will bring to your attention is when you trying to do pagination, it requires you to provide sorting rules:

https://learn.microsoft.com/en-US/sql/t-sql/queries/select-order-by-clause-transact-sql?view=sql-server-2017

Yet another two collections:

{1, 2, 3, 4}
{1, 1, 1, 2, 2, 3, 4}

Again, are they equal or not? You tell me ..

Element repeatability of a collection plays its role in different scenarios and some collections like Dictionary<TKey, TValue> don't even allow repeated elements.

I believe these kinds of equality are application defined and the framework therefore did not provide all of the possible implementations.

Well, in general cases Enumerable.SequenceEqual is good enough but it returns false in the following case:

var a = new Dictionary<String, int> { { "2", 2 }, { "1", 1 }, };
var b = new Dictionary<String, int> { { "1", 1 }, { "2", 2 }, };
Debug.Print("{0}", a.SequenceEqual(b)); // false

I read some answers to questions like this(you may google for them) and what I would use, in general:

public static class CollectionExtensions {
    public static bool Represents<T>(this IEnumerable<T> first, IEnumerable<T> second) {
        if(object.ReferenceEquals(first, second)) {
            return true;
        }

        if(first is IOrderedEnumerable<T> && second is IOrderedEnumerable<T>) {
            return Enumerable.SequenceEqual(first, second);
        }

        if(first is ICollection<T> && second is ICollection<T>) {
            if(first.Count()!=second.Count()) {
                return false;
            }
        }

        first=first.OrderBy(x => x.GetHashCode());
        second=second.OrderBy(x => x.GetHashCode());
        return CollectionExtensions.Represents(first, second);
    }
}

That means one collection represents the other in their elements including repeated times without taking the original ordering into account. Some notes of the implementation:

• GetHashCode() is just for the ordering not for equality; I think it's enough in this case

• Count() will not really enumerates the collection and directly fall into the property implementation of ICollection<T>.Count

• If the references are equal, it's just Boris

Inhibit

Answer 14

I've made my own compare method. It returns common, missing, and extra values.

private static void Compare<T>(IEnumerable<T> actual, IEnumerable<T> expected, out IList<T> common, out IList<T> missing, out IList<T> extra) {
    common = new List<T>();
    missing = new List<T>();
    extra = new List<T>();

    var expected_ = new LinkedList<T>( expected );
    foreach (var item in actual) {
        if (expected_.Remove( item )) {
            common.Add( item );
        } else {
            extra.Add( item );
        }
    }
    foreach (var item in expected_) {
        missing.Add( item );
    }
}

Lavadalavage

Answer 15

Comparing dictionaries' contents:

To compare two Dictionary<K, V> objects, we can assume that the keys are unique for every value, thus if two sets of keys are equal, then the two dictionaries' contents are equal.

Dictionary<K, V> dictionaryA, dictionaryB;
bool areDictionaryContentsEqual = new HashSet<K>(dictionaryA.Keys).SetEquals(dictionaryB.Keys);

---

Comparing collections' contents:

To compare two ICollection<T> objects, we need to check:

1. If they are of the same length.
2. If every T value that appears in the first collection appears an equal number of times in the second.

public static bool AreCollectionContentsEqual<T>(ICollection<T> collectionA, ICollection<T> collectionB)
    where T : notnull
{
    if (collectionA.Count != collectionB.Count)
    {
        return false;
    }
    Dictionary<T, int> countByValueDictionary = new(collectionA.Count);
    foreach(T item in collectionA)
    {
        countByValueDictionary[item] = countByValueDictionary.TryGetValue(item, out int count) 
            ? count + 1 
            : 1;
    }
    foreach (T item in collectionB)
    {
        if (!countByValueDictionary.TryGetValue(item, out int count) || count < 1)
        {
            return false;
        }
        countByValueDictionary[item] = count - 1;
    }
    return true;
}

---

These solutions should be optimal since their time and memory complexities are O(n), while the solutions that use ordering/sorting have time and memory complexities greater than O(n).

Fachanan

Your dictionary comparison does not check that the values are equal, merely that they have the same keys. This is obviously insufficient to check that "the contents are equal". – Phyllida

@AlastairMaw The whole idea behing the concept of a dictionary and a key is that a key must uniquely represent the content. In case the reader's codebase does not follow that rule, I gave the collection comparison code. – Fachanan

A Dictionary in .NET maps keys to values. But there is no reason two different dictionaries cannot do this differently for an identical set of keys, so I'm not sure what you were/are trying to get at here. There is no such "rule" across the two dictionaries that the OP was asking about. In addition, the original (pre-edit) question that you responded to asked about comparing a Dictionary and a List, which your original answer comparing two Dictionaries did not help with at all. Your updated answer throws exceptions on null inputs, and misbehaves with duplicates ([1] should not equal [1, 1]). – Phyllida