What is the most elegant way to get a set of items by index from a collection?

Question

Given

IList<int> indexes;
ICollection<T> collection;

What is the most elegant way to extract all T in collection based on the the indexes provided in indexes?

For example, if collection contained

"Brian", "Cleveland", "Joe", "Glenn", "Mort"

And indexes contained

1, 3

The return would be

"Cleveland," "Glenn"

Edit: Assume that indexes is always sorted ascending.

Answer 1

This assumes that the index sequence is a monotone ascending sequence of non-negative indices. The strategy is straightforward: for each index, bump up an enumerator on the collection to that point and yield the element.

public static IEnumerable<T> GetIndexedItems<T>(this IEnumerable<T> collection, IEnumerable<int> indices)
{
    int currentIndex = -1;
    using (var collectionEnum = collection.GetEnumerator())
    {
        foreach(int index in indices)
        {
            while (collectionEnum.MoveNext()) 
            {
                currentIndex += 1;
                if (currentIndex == index)
                {
                    yield return collectionEnum.Current;
                    break;
                }
            }
        }    
    }
}

Advantages of this solution over other solutions posted:

• O(1) in extra storage -- some of these solutions are O(n) in space
• O(n) in time -- some of these solutions are quadradic in time
• works on any two sequences; does not require ICollection or IList.
• only iterates the collection once; some solutions iterate the collection multiple times (to build a list out of it, for instance.)

Disadvantages:

• harder to read

Answer 2

Here's a faster version:

IEnumerable<T> ByIndices<T>(ICollection<T> data, IList<int> indices)
{
    int current = 0;
    foreach(var datum in data.Select((x, i) => new { Value = x, Index = i }))
    {
        if(datum.Index == indices[current])
        {
            yield return datum.Value;
            if(++current == indices.Count)
                yield break;
        }
    }
}