How to get the index of an element in an IEnumerable?

Question

I wrote this:

public static class EnumerableExtensions
{
    public static int IndexOf<T>(this IEnumerable<T> obj, T value)
    {
        return obj
            .Select((a, i) => (a.Equals(value)) ? i : -1)
            .Max();
    }

    public static int IndexOf<T>(this IEnumerable<T> obj, T value
           , IEqualityComparer<T> comparer)
    {
        return obj
            .Select((a, i) => (comparer.Equals(a, value)) ? i : -1)
            .Max();
    }
}

But I don't know if it already exists, does it?

Exchangeable

The problem with a Max approach is that a: it keeps looking, and b: it returns the last index when there are duplicates (people usually expect the first index) – Cassiecassil

geekswithblogs.net compares 4 solutions and their performance. The ToList()/FindIndex() trick performs best – Leopard

@Leopard That link didn't work. But ToList() doesn't sound like the most efficient solution. The one by Marc Graveli stops when it finds a match. – Bromate

@Bromate You can still have a look at it via web.archive.org – Leopard

Oh, interesting... that would change what the best answer is, if that's really the case. (hoping someone can verify) – Bromate

Maybe it depends on what the underlying object is that implements IEnumerable. – Bromate

Answer 1

The whole point of getting things out as IEnumerable is so you can lazily iterate over the contents. As such, there isn't really a concept of an index. What you are doing really doesn't make a lot of sense for an IEnumerable. If you need something that supports access by index, put it in an actual list or collection.

Carrier

Currently I came accross this thread because I'm implementing a generic IList<> wrapper for the IEnumerable<> type in order to use my IEnumerable<> objects with third party components which only support datasources of type IList. I agree that trying to get an index of an element within an IEnumerable object is probably in most cases a sign of something beign done wrong there are times when finding such index once beats reproducing a large collection in memory just for the sake of finding the index of a single element when you already have an IEnumerable. – Doublehung

-1 cause: There are legitimate reasons why you want to get an index out of a IEnumerable<>. I don't buy the whole "you shoul'd be doing this" dogma. – Cassock

Agree with @ja72; if you shouldn't be dealing with indexes with IEnumerable then Enumerable.ElementAt would not exist. IndexOf is simply the inverse -- any argument against it must apply equally to ElementAt. – Lozada

Cleary, C# misses the concept of IIndexableEnumerable. that would just be the equivalent of an "random accessible" concept, in C++ STL terminology. – Whopping

Suppose you wanted to find the index of a member of SortedSet<T>, which enforces the uniqueness of each of its members? – Concourse

extensions with overloads like Select((x, i) => ...) seem to imply that these indexes should exist – Manda

List<XXX> myList = new List<XXX>(myIEnumerable); – Pfosi

The whole point of IEnumerable<T> is to not force consumers of objects into a specific camp (List, ObservableCollection, Collection, etc) Allowing them to define method parameters and return types how they see fit, as long as it implements IEnumerable<T> – Pfosi

For IndexOf to be meaningful, the IEnumerable must be ordered (don't confuse with sorted), and must be able to be enumerated more than once. I suspect this method isn't part of LINQ because not all IEnumerables meet those criteria. But, in nearly all cases where you want to use this you know that the the underlying collection DOES meet those criteria, so I wish it were included. – Crimpy

Stumbled upon this while working with OpenXML.. you can only refer to the styles by their Indices and you can only access them via enumerators... Now you would think a good idea would be to be able to stop enumeration if the desired style was found, rather than eagerly build long lists prior to traversal. I am fairly new to this, maybe there is an elegant way to achieve this... – Whimsy

@ja72 What do you make of the comments above stating "For IndexOf to be meaningful, the IEnumerable must be ordered (don't confuse with sorted), and must be able to be enumerated more than once." Don't you think it is a valid argument against getting the index of IEnumerable? – Tote

@Crimpy Excellent argument. However, someone pointed out the fact that Enumerable implements ElementAt which assumes some ordering, although Enumerable being a class may specifically have an ordering. What do you think? – Tote

This is hardly an answer... And what should be done if we don't control the IEnumerable class? For example, I need to grab an Excel spreadsheet's named ranges by index. Check out Microsoft.Office.Interop.Excel Names. How can I get the nth named range? – Requital

I can agree that using indicies over IEnumerable would be conceptually incorrect, However I feel that this response completely fails to understand that problems has context. I don't think the ElementAt method is an excuse for a IndexOf method. What really makes sense here is that we wish the get the first item after a certain number of items. (It's not an ElementAt an Index, it's a first element after a count) - Likewise - I think it is perfectly reasonable to have a method that phrases "How many items did I get before I got a match" - The name IndexOf is simply from familiarity. – Bend

" If you need something that supports access by index, put it in an actual list or collection", Why would you assume that the item is ours to implement or re-implement? Some people use software and API's they're not allowed to change. Why would anyone pretend this is not well understood. – Hughey

Answer 2

I'd question the wisdom, but perhaps:

source.TakeWhile(x => x != value).Count();

(using EqualityComparer<T>.Default to emulate != if needed) - but you need to watch to return -1 if not found... so perhaps just do it the long way

public static int IndexOf<T>(this IEnumerable<T> source, T value)
{
    int index = 0;
    var comparer = EqualityComparer<T>.Default; // or pass in as a parameter
    foreach (T item in source)
    {
        if (comparer.Equals(item, value)) return index;
        index++;
    }
    return -1;
}

Cassiecassil

+1 for "questioning the wisdom". 9 times out of 10 it's probably a bad idea in the first place. – Mohock

The explicit loop solution also runs 2x faster (in the worst case) than the Select().Max() solution too. – Clench

You can just Count elements by lambda without TakeWhile - it saves one loop: source.Count(x => x != value); – Purpure

@Purpure - no, that does something different. TakeWhile stops when it gets a failure; Count(predicate) returns the ones that match. i.e. if the first was a miss and everything else was true, TakeWhile(pred).Count() will report 0; Count(pred) will report n-1. – Cassiecassil

TakeWhile is clever! Bear in mind though this returns Count if element doesn't exist which is a deviation from standard behaviour. – Popularly

The "long way" solution could probably be improved regarding performance with fast paths for sources that can be casted to IList<T> or IReadOnlyList<T>. – Sharpen

Answer 3

I would implement it like this:

public static class EnumerableExtensions
{
    public static int IndexOf<T>(this IEnumerable<T> obj, T value)
    {
        return obj.IndexOf(value, null);
    }

    public static int IndexOf<T>(this IEnumerable<T> obj, T value, IEqualityComparer<T> comparer)
    {
        comparer = comparer ?? EqualityComparer<T>.Default;
        var found = obj
            .Select((a, i) => new { a, i })
            .FirstOrDefault(x => comparer.Equals(x.a, value));
        return found == null ? -1 : found.i;
    }
}

Dutyfree

That's actually very cute, +1! It involves extra objects, but they should be relatively cheap (GEN0), so not a huge problem. The == might need work? – Cassiecassil

Added IEqualityComparer overload, in true LINQ style. ;) – Dutyfree

I think you mean to say ... comparer.Equals(x.a, value) =) – Pacien

Since the Select expression is returning the combined result, which is then processed, I'd imagine explicitly using the KeyValuePair value type would allow you to avoid any sort of heap allocations, so long as the .NET impl allocates value types on the stack and any state machine which LINQ may generate uses a field for the Select'd result which isn't declared as a bare Object (thus causing the KVP result to get boxed). Of course, you'd have to rework the found==null condition (since found would now be a KVP value). Maybe using DefaultIfEmpty() or KVP<T, int?> (nullable index) – Flaxseed

You're correct that there are extra allocations for the intermediate result. Though if you're that constrained for performance you'll probably avoid using LINQ altogether. :) – Dutyfree

Nice implementation, though one thing I'd suggest adding is a check to see if obj implements IList<T> and if so, defer to its IndexOf method just in case it has a type-specific optimization. – Mandalay

Answer 4

The way I'm currently doing this is a bit shorter than those already suggested and as far as I can tell gives the desired result:

 var index = haystack.ToList().IndexOf(needle);

It's a bit clunky, but it does the job and is fairly concise.

Toggle

Though this would work for small collections, suppose you have a million items in the "haystack". Doing a ToList() on that will iterate through all one-million elements and add them to a list. Then it will search through the list to find the matching element's index. This would be extremely inefficient as well as the possibility of throwing an exception if the list gets too big. – Sforza

@Sforza Definitely - you need to choose an approach which suits your use case. I doubt there's a one size fits all solution, which is possibly why there isn't an implementation in the core libraries. – Toggle

@Sforza Hmm... See the link by nixda in the comments under the main questions. My thinking was similar to yours but the analysis shows that ToList() / FindIndex() is more efficient. – Bromate

@Bromate That is an interesting article, though it may not show the whole picture. The ToList() method has two branches: One, when the underlying object implements ICollection<T> the other when it doesn't. It seems that the algorithm used by the author uses a List for the backing instance. Because List<T> implements ICollection<T>, it takes the first branch which does a memory copy of the underlying array. This is extremely fast and would account for the results. I'm interested to see a comparison using an IEnumerable<T> instance that does not implement ICollection. – Sforza

@Bromate There is also still the concern of an OutOfMemoryException if the source is sufficiently large. – Sforza

@Sforza Interesting. My first thought is: what if the underlying object is a List. Wouldn't it be most efficient to first check for that and if so, just do a simple IndexOf; otherwise, first do a ToList. (Similarly if the underlying object is an array.) – Bromate

@Bromate That is a really good point. Maybe the best solution would be to check if the enumerable is a List<T> and if so do IndexOf() (like you said). If not, check if it implements ICollection<T> (which arrays do). If it does, do ToList().IndexOf() and if not use an iterative approach to find the index. – Sforza

Answer 5

I think the best option is to implement like this:

public static int IndexOf<T>(this IEnumerable<T> enumerable, T element, IEqualityComparer<T> comparer = null)
{
    int i = 0;
    comparer = comparer ?? EqualityComparer<T>.Default;
    foreach (var currentElement in enumerable)
    {
        if (comparer.Equals(currentElement, element))
        {
            return i;
        }

        i++;
    }

    return -1;
}

It will also not create the anonymous object

Farro

Answer 6

The best way to catch the position is by FindIndex This function is available only for List<>

Example

int id = listMyObject.FindIndex(x => x.Id == 15); 

If you have enumerator or array use this way

int id = myEnumerator.ToList().FindIndex(x => x.Id == 15); 

or

 int id = myArray.ToList().FindIndex(x => x.Id == 15); 

Anfractuous

Answer 7

A bit late in the game, i know... but this is what i recently did. It is slightly different than yours, but allows the programmer to dictate what the equality operation needs to be (predicate). Which i find very useful when dealing with different types, since i then have a generic way of doing it regardless of object type and <T> built in equality operator.

It also has a very very small memory footprint, and is very, very fast/efficient... if you care about that.

At worse, you'll just add this to your list of extensions.

Anyway... here it is.

 public static int IndexOf<T>(this IEnumerable<T> source, Func<T, bool> predicate)
 {
     int retval = -1;
     var enumerator = source.GetEnumerator();

     while (enumerator.MoveNext())
     {
         retval += 1;
         if (predicate(enumerator.Current))
         {
             IDisposable disposable = enumerator as System.IDisposable;
             if (disposable != null) disposable.Dispose();
             return retval;
         }
     }
     IDisposable disposable = enumerator as System.IDisposable;
     if (disposable != null) disposable.Dispose();
     return -1;
 }

Hopefully this helps someone.

Ious

Maybe I'm missing something, but why the GetEnumerator and MoveNext rather than just a foreach? – Homochromatic

Short answer? Efficiency. Long answer: msdn.microsoft.com/en-us/library/9yb8xew9.aspx – Ious

Looking at the IL it appears that the performance difference is that a foreach will call Dispose on the enumerator if it implements IDisposable. (See #4982896) As the code in this answer doesn't know if the result of calling GetEnumerator is or isn't disposable it should do the same. At that point I'm still unclear that there's a perf benefit, though there was some extra IL whose purpose didn't leap out at me! – Homochromatic

@JoshGallagher I did a bit of research a while back regarding perf benefits between foreach and for(i), and the main benefit of using for(i) was that it ByRefs the object in-place rather than re-creating it/passing it back ByVal. I would assume the same applies to MoveNext versus foreach, but i'm not sure about that one. Maybe they both use ByVal... – Ious

Reading this blog (blogs.msdn.com/b/ericlippert/archive/2010/09/30/…) it may be that the "iterator loop" to which he is referring is a foreach loop, in which case for the particular case of T being a value type it might be saving a box/unbox operation by using the while loop. However, this isn't borne out by the IL I got from a version of your answer with foreach. I do still think the conditional disposal of the iterator is important, though. Could you modify the answer to include that? – Homochromatic

Sorry - So this is a good example of dangerous premature optimizations, without enough understanding and forgetting to benchmark??? o.O... The disposing above is not implemented correctly, when done "correctly" (which is less that the above) performance is for all intends and purposes identical. (Well the foreach loop is essentially lowered to the same code so DUH!...) and they allocate exactly the same. So I would avoid this answer. – Bend

Now I would give @Ious the benefit of doubt here and say this is a 9 year old response, so there may certainly have been improvements, and my benchmarks has been on .NET 481, .NET 6 and .NET 7. – Bend

Answer 8

A few years later, but this uses Linq, returns -1 if not found, doesn't create extra objects, and should short-circuit when found [as opposed to iterating over the entire IEnumerable]:

public static int IndexOf<T>(this IEnumerable<T> list, T item)
{
    return list.Select((x, index) => EqualityComparer<T>.Default.Equals(item, x)
                                     ? index
                                     : -1)
               .FirstOr(x => x != -1, -1);
}

Where 'FirstOr' is:

public static T FirstOr<T>(this IEnumerable<T> source, T alternate)
{
    return source.DefaultIfEmpty(alternate)
                 .First();
}

public static T FirstOr<T>(this IEnumerable<T> source, Func<T, bool> predicate, T alternate)
{
    return source.Where(predicate)
                 .FirstOr(alternate);
}

Funds

Another way of doing it can be: public static int IndexOf<T>(this IEnumerable<T> list, T item) { int e = list.Select((x, index) => EqualityComparer<T>.Default.Equals(item, x) ? x + 1 : -1) .FirstOrDefault(x => x > 0); return (e == 0) ? -1 : e - 1); } – Pulliam

"doesn't create extra objects". Linq will in fact create objects in the background so this is not fully correct. Both source.Where and source.DefaultIfEmpty will for example create an IEnumerable each. – Faddish

Answer 9

Stumbled across this today in a search for answers and I thought I'd add my version to the list (No pun intended). It utlises the null conditional operator of c#6.0

IEnumerable<Item> collection = GetTheCollection();

var index = collection
.Select((item,idx) => new { Item = item, Index = idx })
//or .FirstOrDefault(_ =>  _.Item.Prop == something)
.FirstOrDefault(_ => _.Item == itemToFind)?.Index ?? -1;

I've done some 'racing of the old horses' (testing) and for large collections (~100,000), worst case scenario that item you want is at the end, this is 2x faster than doing ToList().FindIndex(). If the Item you want is in the middle its ~4x faster.

For smaller collections (~10,000) it seems to be only marginally faster

Heres how I tested it https://gist.github.com/insulind/16310945247fcf13ba186a45734f254e

Bechler

Answer 10

An alternative to finding the index after the fact is to wrap the Enumerable, somewhat similar to using the Linq GroupBy() method.

public static class IndexedEnumerable
{
    public static IndexedEnumerable<T> ToIndexed<T>(this IEnumerable<T> items)
    {
        return IndexedEnumerable<T>.Create(items);
    }
}

public class IndexedEnumerable<T> : IEnumerable<IndexedEnumerable<T>.IndexedItem>
{
    private readonly IEnumerable<IndexedItem> _items;

    public IndexedEnumerable(IEnumerable<IndexedItem> items)
    {
        _items = items;
    }

    public class IndexedItem
    {
        public IndexedItem(int index, T value)
        {
            Index = index;
            Value = value;
        }

        public T Value { get; private set; }
        public int Index { get; private set; }
    }

    public static IndexedEnumerable<T> Create(IEnumerable<T> items)
    {
        return new IndexedEnumerable<T>(items.Select((item, index) => new IndexedItem(index, item)));
    }

    public IEnumerator<IndexedItem> GetEnumerator()
    {
        return _items.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

Which gives a use case of:

var items = new[] {1, 2, 3};
var indexedItems = items.ToIndexed();
foreach (var item in indexedItems)
{
    Console.WriteLine("items[{0}] = {1}", item.Index, item.Value);
}

Needlewoman

great baseline. It is helpful to add members IsEven, IsOdd, IsFirst and IsLast as well. – Flute

Answer 11

This can get really cool with an extension (functioning as a proxy), for example:

collection.SelectWithIndex(); 
// vs. 
collection.Select((item, index) => item);

Which will automagically assign indexes to the collection accessible via this Index property.

Interface:

public interface IIndexable
{
    int Index { get; set; }
}

Custom extension (probably most useful for working with EF and DbContext):

public static class EnumerableXtensions
{
    public static IEnumerable<TModel> SelectWithIndex<TModel>(
        this IEnumerable<TModel> collection) where TModel : class, IIndexable
    {
        return collection.Select((item, index) =>
        {
            item.Index = index;
            return item;
        });
    }
}

public class SomeModelDTO : IIndexable
{
    public Guid Id { get; set; }
    public string Name { get; set; }
    public decimal Price { get; set; }

    public int Index { get; set; }
}

// In a method
var items = from a in db.SomeTable
            where a.Id == someValue
            select new SomeModelDTO
            {
                Id = a.Id,
                Name = a.Name,
                Price = a.Price
            };

return items.SelectWithIndex()
            .OrderBy(m => m.Name)
            .Skip(pageStart)
            .Take(pageSize)
            .ToList();

Tertia

Answer 12

You can add a small extension method:

public static IEnumerable<(T value, int index)> Index<T>(this IEnumerable<T> source)
    => source.Select((x, i) => (value: x, index: i));

And then you can use it like:

// get the index of a particular element
myCollection.Index().First(x => x.value == myElement).index;

// loop through elements with indices
foreach (var (element, i) in myCollection.Index()) {
    // do whatever
}

// get the original index of the 3rd item that matches some criteria
myCollection.Index().Where(/* some condition */).ElementAt(2).index

Uniat

Answer 13

Try this:

static int FindIndex<T>(this IEnumerable<T> a, Predicate<T> f) =>
    a.TakeWhile(x => !f(x)).Count();

static int IndexOf<T>(this IEnumerable<T> a, T value) =>
    a.FindIndex(x => EqualityComparer<T>.Default.Equals(x, value));

var i = new[] { 1, 2, 3 }.IndexOf(2); // 1

Helmut

That only reshuffles a part of what's said in this answer given in 2009. – Tourmaline