With a Comparer to comparer keys by their values from a dictionary, SortedDictionary always throw exception

Question

I want to achieve a heap with SortedDictionary which compares values instead of keys. My elements are in the dictionary and I added them one by one to the SortedDictionary. It always thow exception at the 2nd time from the "Add" method in the loop. "An entry with the same key already exists". Since I got elements from a dictionary, I know that keys cannot be same. What should I do to make such a SortedDictionary work? Thanks a lot!

dic = new Dictionary<int, int>();
var sort = new SortedDictionary<int, int>(Comparer<int>.Create((x, y) => dic[x].CompareTo(dic[y])));
foreach (var pair in dic)
{
    sort.Add(pair.Key, pair.Value);
}

Answer 1

You can try the next approach:

var sort = new SortedDictionary<int, int>(
    Comparer<int>.Create(
        (x, y) => 
        {
            int vx = dic[x];
            int vy = dic[y];

            // If values are the same then compare keys.
            if (vx == vy)
                return x.CompareTo(y);

            // Otherwise - compare values.
            return vx.CompareTo(vy);
        }));

If you declare sort using this approach then Keys in the sort will be ordered by Values. Here is complete sample that shows how this approach works.

---

@SylvainLIU asked:

What confuse me is, in my original post, by using dic[x].CompareTo(dic[y]) I meant to get the return value of the Compare() method, but not to take dic[x] or dic[y] as Key of the SortedDictionary. Why they're asked to be unique?

You were right and your sample worked as you assumed. So why did it throw an exception?

SortedDictionary must contain unique keys. By specifying Comparer for SortedDictionary we specify how to order keys and how to define if a new key is unique. If Comparer returns 0 for a new key then this key is not unique and an exception An entry with the same key already exists will be thrown.

If we use comparer dic[x].CompareTo(dic[y]) then to compare keys x and y we use their values dic[x] and dic[y]. For example, lets we have two pairs (Key=1, Value=3) and (Key=2, Value=3). If we use comparer dic[x].CompareTo(dic[y]) to compare them, then keys of this pairs are not unique, because they are compared by their values: 3.CompareTo(3) = 0. Of course, values 1 and 2 are different numbers, but from the point of view of comparer dic[x].CompareTo(dic[y]) they are the same. Therefore if we use this comparer we must ensure that values of the pairs must be unique to prevent duplicate errors.

If we use next comparer

int vx = dic[x];
int vy = dic[y];

// If values are the same then compare keys.
if (vx == vy)
    return x.CompareTo(y);

// Otherwise - compare values.
return vx.CompareTo(vy);

then values of the dic must not be unique, because this comparer takes into account that values in dic can be the same and for this case it uses another strategy to ordering and checking for uniqueness.