This topic started from question on StackOverflow:
different collections (Array and List) have different implementation of IList.IndexOf method.
Example
using System;
using System.Collections;
using System.Collections.Generic;
namespace IndexOf
{
class Program
{
public static void Main()
{
var item = new Item { Id = 1 };
IList list = new List<Item> { item };
IList array = new[] { item };
var newItem = new Item { Id = 1 };
var lIndex = list.IndexOf(newItem);
var aIndex = array.IndexOf(newItem);
Console.WriteLine(lIndex); //0
Console.WriteLine(aIndex); //-1
}
public class Item : IEquatable<Item>
{
public int Id { get; set; }
public bool Equals(Item other) => other != null && other.Id == Id;
}
}
}
As we see Item implements generic interface IEquatable<T> with generic method Equals(T other). Both collections are declared as IList that has non-generic method IndexOf(object value). But why results are different? We can find item in the list, but not in array.
Let's look at List<T> implementation of the method:
int IList.IndexOf(object item)
{
if (List<T>.IsCompatibleObject(item))
return this.IndexOf((T) item);
return -1;
}
It calls generic implementation IndexOf(T item):
public int IndexOf(T item)
{
return Array.IndexOf<T>(this._items, item, 0, this._size);
}
And static generic method IndexOf of Array class:
public static int IndexOf<T>(T[] array, T value, int startIndex, int count)
{
if (array == null)
throw new ArgumentNullException("array");
if (startIndex < 0 || startIndex > array.Length)
throw new ArgumentOutOfRangeException("startIndex", Environment.GetResourceString("ArgumentOutOfRange_Index"));
if (count < 0 || count > array.Length - startIndex)
throw new ArgumentOutOfRangeException("count", Environment.GetResourceString("ArgumentOutOfRange_Count"));
return EqualityComparer<T>.Default.IndexOf(array, value, startIndex, count);
}
The main part is EqualityComparer<T>.Default. Here .net creates comparer for out class Item. As our class implements IEquatable<> interface, GenericEqualityComparer will be created. Check with:
Console.WriteLine(EqualityComparer<Item>.Default.GetType());
GenericEqualityComparer uses IEquatable<T>.Equals(T other) method to compare objects:
internal class GenericEqualityComparer<T> : EqualityComparer<T> where T : IEquatable<T>
{
public override bool Equals(T x, T y)
{
if ((object) x != null)
{
if ((object) y != null)
return x.Equals(y);
return false;
}
return (object) y == null;
}
//...
}
So, method IndexOf implemented in List always uses IEquatable<T>.Equals(T other). What about arrays?
Array implementation:
int IList.IndexOf(object value)
{
return Array.IndexOf(this, value);
}
There are no calls to generic implementation, it operates with an object:
public static int IndexOf(Array array, object value)
{
if (array == null)
throw new ArgumentNullException("array");
int lowerBound = array.GetLowerBound(0);
return Array.IndexOf(array, value, lowerBound, array.Length);
}
And again calls non-generic methods. The final method has this code:
for (int index = startIndex; index < num; ++index)
{
object obj = objArray[index];
if (obj != null && obj.Equals(value))
return index;
}
Where obj.Equals(value) is Equals(object obj) method of Object class.
So, Array and List have different behavior when we search the index of an item. It is also the same for Contains method:
Console.WriteLine(list.Contains(newItem)); //true
Console.WriteLine(array.Contains(newItem)); //false
Ok, but we worked with non-generic interface IList and it looks not so strange. Let's change example to use generic IList<T>:
using System;
using System.Collections;
using System.Collections.Generic;
namespace IndexOf
{
class Program
{
public static void Main()
{
var item = new Item { Id = 1 };
IList<Item> list = new List<Item> { item };
IList<Item> array = new[] { item };
var newItem = new Item { Id = 1 };
var lIndex = list.IndexOf(newItem);
var aIndex = array.IndexOf(newItem);
Console.WriteLine(lIndex); //0
Console.WriteLine(aIndex); //-1
Console.WriteLine(list.Contains(newItem)); //true
Console.WriteLine(array.Contains(newItem)); //false
}
public class Item : IEquatable<Item>
{
public int Id { get; set; }
public bool Equals(Item other) => other != null && other.Id == Id;
}
}
}
But the result is the same! We can find item in the list, but not in array.
List uses a generic method that we saw before:
public int IndexOf(T item)
{
return Array.IndexOf<T>(this._items, item, 0, this._size);
}
But an array... has no generic implementation of IndexOf<T> method! Here magic begins. CLR uses special wrapper for array - SZArrayHelper and it's method IndexOf<T>:
int IndexOf<T>(T value) {
//! Warning: "this" is an array, not an SZArrayHelper. See comments above
//! or you may introduce a security hole!
T[] _this = JitHelpers.UnsafeCast<T[]>(this);
return Array.IndexOf(_this, value);
}
It looks like we work with generic method and objects and should lead to GenericEqualityComparer<T>:
public static int IndexOf<T>(T[] array, T value) {
if (array==null) {
throw new ArgumentNullException("array");
}
Contract.Ensures((Contract.Result<int>() < 0) ||
(Contract.Result<int>() >= 0 && Contract.Result<int>() < array.Length && EqualityComparer<T>.Default.Equals(value, array[Contract.Result<int>()])));
Contract.EndContractBlock();
return IndexOf(array, value, 0, array.Length);
}
But the problem is how CLR calls this method:
Although we use generic IList<Item> and pass Item, CLR cast it to object type and use ObjectEqualityComparer<T> instead of GenericEqualityComparer<T>. Funny, that ObjectEqualityComparer<T> is generic too but compares values as objects:
internal class ObjectEqualityComparer<T> : EqualityComparer<T>
{
public override bool Equals(T x, T y)
{
if ((object) x != null)
{
if ((object) y != null)
return x.Equals((object) y);
return false;
}
return (object) y == null;
}
//...
}
And we returned to Item that has only generic Equals, not base one.
So, remember to override Equals(object obj):
public class Item : IEquatable<Item>
{
public int Id { get; set; }
public bool Equals(Item other) => other != null && other.Id == Id;
public override bool Equals(object obj) => Equals(obj as Item);
}