Is there a SortedSet-like container that groups non-comparable objects?

Question

I have some objects that I'd like to put into an associative container that groups them by a non-comparable field value. So if I had the following:

using System.Collections.Generic;
using Pair = System.Tuple<Penguin, int>;

class Penguin {}

class Whatever {

    public static void Main(string[] args) {
        Penguin emperor = new Penguin(),
                adelie = new Penguin(),
                batmanVillain = new Penguin();

        var okay = new HypotheticalCollection<Pair>(5);

        okay.Add(new Pair(emperor, 1) );
        okay.Add(new Pair(adelie, 2) );
        okay.Add(new Pair(batmanVillain, 3) );
        okay.Add(new Pair(emperor, -500) );
        okay.Add(new Pair(batmanVillain, 5) );

    }
}

and I iterated over the HypotheticalCollection, I would want to see the two emperor entries together and the two batmanVillain entries together, but I don't care which one's first. However, I would like to be able to look up an entry in logarithmic time.

If I were using C++, I would just sort the Penguins by their address, but I don't have that luxury in C#. Right now I'm handling it by assigning a serial number to each of the objects, but that feels kind of hacky, and I'd prefer not to have the extra space overhead. Is there a better way, maybe a ReferenceLessThan function or something?

Answer 1

Option 1: (suggestion)

public static class Whatever
{
    class Penguin
    {
        private Guid id = Guid.NewGuid();       
        public Guid GetId() { return id; }
    }

    public static void Main(string[] args)
    {
        Penguin emperor = new Penguin(),
            adelie = new Penguin(),
            batmanVillain = new Penguin();

        var okay = new List<KeyValuePair<Penguin, int>>();
        okay.Add(new KeyValuePair<Penguin, int>(emperor, 1));
        okay.Add(new KeyValuePair<Penguin, int>(adelie, 2));
        okay.Add(new KeyValuePair<Penguin, int>(batmanVillain, 3));
        okay.Add(new KeyValuePair<Penguin, int>(emperor, -500));
        okay.Add(new KeyValuePair<Penguin, int>(batmanVillain, 5));

        okay.Sort((a, b) => a.Key.GetId().CompareTo(b.Key.GetId()));

        // Iterate 'okay'
    }
}

Option 2 is to use the object address in the sort compare function, which according to this is not a fix address and can be changed by the CLR. In addition, getting the address requires to build your app with unsafe flag. If you claim that option 1 feels "hacky", so csharaply option 2 is super "hacky". And a GUID is a 128-bit integer (16 bytes).