Is there a reasonable scenario for a stateful IComparer<T>?

Question

I have never written a stateful IComparer<T> with a default constructor. All standard library implementations which I've checked in Reflector are stateless as well. Therefore, I'd like to assume that I can freely cache IComparer<T> like this:

PriorityQueue<TPriority, TComparer> where TComparer : IComparer<TPriority>, new()
{
    private static TComparer _comparer = new TComparer();

    public PriorityQueue() {...}
    ...
}

instead of

PriorityQueue<TPriority>
{
    private IComparer<TPriority> _comparer;

    public PriorityQueue(IComparer<TPriority> comparer) { 
        _comparer = comparer;
        ...
    }

    ...
}

So here is the question: have you ever written/seen an IComparer<T> for which this would break down? If yes, how common is it?

EDIT: The reason I really don't want the overhead of the second version in this case is that the data structure is persistent. It is implemented as a tree where nodes have no parent/root reference. So it wouldn't be one reference to comparer per queue, but one reference to comparer per node! My original design was just to use IComparable<T> and recommend writing a wrapper struct for custom comparisons.

Answer 1

Yes, I have, but I think it's fairly uncommon.

There are rare instances where you want to implement a comparison that's dependent on other data. For example, we've got some spatial routines where we feed an axis that's used for comparison as part of the IComparer.

That being said, it's pretty easy to work around this by just using a separate comparer class, and that's probably a better design in many ways. You are putting a limitation on the IComparer<T> implementation that does need to exist, though, so I would document your rationale.

My personal preference would be to make the IComparer<T> non-static, and provide two constructors - one that takes an external instance and one that creates a default comparer. You have the extra overhead of a comparer per queue, but that's pretty minimal (nearly 0 if you have no state, since it's only a single object reference to an "empty" object).

Answer 2

Well, having a static comparer means you can't have different comparisons on different queues; this can be a problem... occasionally people do need a custom comparison; for example, if they don't control the type. My default approach would be:

PriorityQueue<TPriority>
{
    private IComparer<TPriority> _comparer;

    public PriorityQueue(IComparer<TPriority> comparer) { 
        _comparer = comparer;
        ...
    }

    public PriorityQueue() : this(Comparer<T>.Default) {}
}

Re stateful comparers; yes, I've written several - particularly for writing LINQ-style projection comparers... for example, something like:

public static class ProjectionComparer<TSource>
{
    public static IComparer<TSource> CompareBy<TValue>(
        Func<TSource, TValue> selector)
    {
        return CompareBy<TValue>(selector, Comparer<TValue>.Default);
    }
    public static IComparer<TSource> CompareBy<TValue>(
        Func<TSource, TValue> selector,
        IComparer<TValue> comparer)
    {
        return new ProjectionComparerItem<TValue>(
            selector, Comparer<TValue>.Default);
    }
    class ProjectionComparerItem<TValue> : IComparer<TSource>
    {
        private readonly IComparer<TValue> comparer;
        private readonly Func<TSource, TValue> selector;
        public ProjectionComparerItem(
            Func<TSource, TValue> selector,
            IComparer<TValue> comparer)
        {
            this.selector = selector;
            this.comparer = comparer;
        }
        public int Compare(TSource x, TSource y)
        {
            // TODO: some null stuff...
            return comparer.Compare(selector(x), selector(y));
        }
    }
}

which allows:

IComparer<Customer> comparer = ProjectionComparer<Customer>
          .CompareBy(cust => cust.Name);

instance "sort by name" comparison.

Answer 3

Another possible approach:

private class PriorityQueueImpl<TPriority, TComparer> where TComparer : IComparer<TPriority> {
    // all methods accept a TComparer
    // generic in TComparer to avoid boxing for struct TComparers and permit inlining for sealed TComparers
}

public struct PriorityQueue<TPriority, TComparer> where TComparer : IComparer<TPriority> {
    private readonly PriorityQueueImpl<TPriority, TComparer> _impl;
    private readonly TComparer _comparer;

    // methods delegate to _impl
}

I may go with it at least for some cases.