linq way to insert element in order

i have a collection of elements sorted by the elements' Name property. i need to insert a new element into the collection while maintaining the order. i am looking for a concise LINQ way to do this. my code is below. "this.Children" is the collection, and "d" is the new element that i need to insert. it takes two passes over the collection to find the insertion point. is there a way to get the index from the First() extension method? (please do not suggest using foreach, i know that :), i am learning LINQ).

than开发者_StackOverflow社区ks! konstantin

var v = this.Children.FirstOrDefault(x => string.Compare(x.Name, d.Name) > 0);
int index = this.Children.IndexOf(v);

if (index < 0)
{
    this.children.Add(d);
}
else
{
    this.Children.Insert(index, d);
}

---

Yes, using the overload of Select which includes the index as well as the value:

var pair = this.Children
               .Select((value, index) => new { value, index })
               .FirstOrDefault(x => string.Compare(x.value.Name, d.Name) > 0);

if (pair == null)
{
    Children.Add(d);
}
else
{
    Children.Insert(pair.index, d);
}

Note that this is still inefficient though - if you already know the values are sorted, you can use a binary chop to find out the insertion index. It's hard to give sample code for that without knowing the type of Children though... there's already List<T>.BinarySearch and Array.BinarySearch.

Learning LINQ is admirable - but it's also important to learn when using LINQ isn't the best way to go :)

---

Assuming that this.Children is a List<T>, you can use List<T>.BinarySearch with a custom comparer to efficiently find the position to insert the new element at:

IComparer<Foo> comparer = AnonymousComparer.Create<Foo>(
    (x, y) => string.Compare(x.Name, y.Name));

int index = this.Children.BinarySearch(d, comparer);
if (index < 0) index = ~index;
this.Children.Insert(index, d);

with

static class AnonymousComparer
{
    public static IComparer<T> Create<T>(Func<T, T, int> comparer)
    {
        if (comparer == null) { throw new ArgumentNullException("comparer"); }
        return new TheComparer<T>(comparer);
    }
    private class TheComparer<T> : IComparer<T>
    {
        private readonly Func<T, T, int> c;
        public TheComparer(Func<T, T, int> c) { this.c = c; }
        int IComparer<T>.Compare(T x, T y) { return this.c(x, y); }
    }
}

---

I created my own Extension method for adding a new item in the correct order:

public static class ListExtension
{
    public static void InsertOrderedBy<TSource, TKey>(this IList<TSource> source, TSource item, Func<TSource, TKey> keySelector) where TKey : IComparable<TKey>
    {
        var i = source.Select((Value, Index) => new { Value, Index }).FirstOrDefault(x => keySelector(x.Value).CompareTo(keySelector(item)) > 0);

        if (i == null)
        {
            source.Add(item);
        }
        else
        {
            source.Insert(i.Index, item);
        }
    }
}

I use it like this:

List<Item> ItemList = new List<Item>();
ItemList.InsertOrderedBy(item, x => x.Duration);

It's almost the same like the answer from Jon Skeet, but I can pass the sort argument as second parameter, e.g. a Duration (type TimeSpan).

---

Well, you could always just use OrderBy after adding the new element...

var v = this.Children.Union(new List<TypeOfChildren>() { d }).OrderBy<TypeOfChildren, string>(x => x.Name).ToList<TypeOfChildren>();