LINQ To Objects GroupBy method

How does LINQ To Objects GroupBy method work? Does it look throught the whole collection for each key? Is there any way to say to GroupBy开发者_如何学Go method that collection is sorted?

---

GroupBy, if done sensibly, would work in a single forwards only pass. A basic implementation (not theirs) would be something comparable to:

var data = new Dictionary<TKey, List<TValue>>(comparer);
foreach(var item in source) {
    var key = keySelector(item);
    List<TValue> list;
    if(!data.TryGetValue(key, out list))
    {
        data.Add(key, list = new List<TValue>());
    }
    list.Add(itemSelector(item));
}

That basically groups by key, creating a list for each unique key, containing the values.

You could do things like compare to the last-seen key (to help with sorted data), but... you'd need to profile to know if it is worthwhile.

---

Let's just look at the overload

IEnumerable<IGrouping<TKey, TSource>> Enumerable.GroupBy<TSource, TKey>(
    this IEnumerable<TSource> source,
    Func<TSource, TKey> keySelector
);

as its the simplest to understand. Effectively the code will do something like this:

Enumerate through source

For each element in source, map element to key = keySelector(element)

See if key is in a dictionary keyed by TKey if it is not, add the key with the value a List<TSource> and first item element else, get the List<TSource> associated to key and add element to the list

Now you have a dictionary mapping TKey -> TSource and can easily produce a sequence of IGrouping<TKey, TElement>.

So something like

var dictionary = new Dictionary<TKey, List<TSource>> dictionary;
foreach(var element in source) {
    key = keySelector(element);
    List<TSource> list;
    if(!dictionary.TryGetValue(key, out list)) {
        list = new List<TSource>();
        dictionary.Add(key, list);
    }
    list.Add(element);
}

From here you can easily yield a sequence of IGrouping<TKey, TSource>.

I don't see why you think the list being sorted matters.

---

Does it look throught the whole collection for each key?

No. The implementation of GroupBy is O(n), not O(n^2)