This topic started from question on StackOverflow: different collections (Array and List) have different implementation of IList.IndexOf method.
Example
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 impelments 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 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 impelments 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 is not calls to generic implementation, it operates with 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. 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 has different behavior, when we search index of item. It 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 result is the same! We can find item in list, but not in array.
List uses generic method that we saw before:
public int IndexOf(T item)
{
return Array.IndexOf<T>(this._items, item, 0, this._size);
}
But 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 look 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:
Despite the fact that 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, don’t forget 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);
}