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?

Solution 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.

Solution 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;
}

Solution 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;
    }
}

Solution 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.

Solution 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

View more solutions

Comments

[Marc Gravell]

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)

[nixda]

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

[KevinVictor]

@nixda 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.

[nixda]

@KevinVictor You can still have a look at it via web.archive.org

[KevinVictor]

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

[KevinVictor]

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

[Joel Coehoorn]

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

[Steve Guidi]

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

[Marc Gravell]

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?

[dahlbyk]

Added IEqualityComparer overload, in true LINQ style. ;)

[Marc]

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

[jpierson]

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.

[Kamarey]

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

[Marc Gravell]

@Kamarey - 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.

[John Alexiou]

-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.

[Kirk Woll]

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.

[v.oddou]

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

[DavidRR]

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

[Michael]

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

[kornman00]

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)

[dahlbyk]

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. :)

[Josh Gallagher]

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

[MaxOvrdrv]

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

[Josh Gallagher]

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 stackoverflow.com/questions/4982396/…) 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!

[MaxOvrdrv]

@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...

[Josh Gallagher]

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?

[esteuart]

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.

[Mark Watts]

@esteuart 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.

[Josh]

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.

[JJS]

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

[Rick the Scapegoat]

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

[Rick the Scapegoat]

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>

[Darryl]

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.

[nawfal]

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

[Palcente]

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...

[Anu Thomas Chandy]

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); }

[Tarik]

@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?

[Tarik]

@Darryl 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?

[Martin Odhelius]

"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.

[Theodor Zoulias]

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>.

[ctwheels]

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?

[KevinVictor]

@esteuart 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.

[esteuart]

@KevinVictor 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.

[esteuart]

@KevinVictor There is also still the concern of an OutOfMemoryException if the source is sufficiently large.

[KevinVictor]

@esteuart 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.)

[esteuart]

@KevinVictor 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.