[C#] 중복된 Key를 허용하며, Key로 정렬 된 해쉬맵(Dictionary)

C#의 자료구조 중 Key-Value 컨테이너는 Dictionary입니다. 경우에 따라 Key로 정렬된 Dictionary는 SortedDictionary 클래스로써 C#에서 기본적으로 제공하고 있습니다. 그런데, Dictionary이므로 Key가 중복될 수 없습니다. 중복된 값을 정렬해서 저장하기 위해서는 Set 자료 구조를 이용해야 합니다. 그런데, Set는 Key만을 저장할 수 있고 Value는 저장할 수 없습니다. 중복된 Key를 허용하면서, Key로 정렬된 컨테이너는 기본적으로 C#에서 제공하지 않습니다. 하지만 두개의 클래스를 조합하면 가능한데, SortedSet과 Tuple입니다. 이 두개의 클래스를 통해 중복된 Key를 허용하면서, Key로 정렬된 컨테이너에 대한 클래스는 아래와 같습니다.

public class SortedTupleBag<TKey, TValue> : SortedSet<Tuple<TKey, TValue>>
where TKey : IComparable
{
    private class TupleComparer : Comparer<Tuple<TKey, TValue>>
    {
        public override int Compare(Tuple<TKey, TValue> x, Tuple<TKey, TValue> y)
        {
            if (x == null || y == null) return 0;

            return x.Item1.Equals(y.Item1) ? 1 : Comparer<TKey>.Default.Compare(x.Item1, y.Item1);
        }
    }

    public SortedTupleBag() : base(new TupleComparer()) { }

    public void Add(TKey key, TValue value)
    {
        Add(new Tuple<TKey, TValue>(key, value));
    }
}

이 클래스의 활용 예는 아래의 코드와 같습니다.

var tuples = new SortedTupleBag<double, double>();

tuples.Add(10.0, 100.1);
tuples.Add(40.0, 100.4);
tuples.Add(10.0, 1000.1);
tuples.Add(80.0, 20.8);
tuples.Add(70.0, 2100.7);
tuples.Add(50.0, 200.5);

Add 함수의 첫번째는 Key이고 두번째는 Value입니다. Key의 순서대로 정렬되어 있는지 확인하기 위해 아래의 코드를 통해 살펴볼 수 있습니다.

Console.WriteLine("Sorted List");
foreach (var tuple in tuples)
{
    Console.WriteLine("{0} {1}", tuple.Item1, tuple.Item2);
}

Console.WriteLine("");

Console.WriteLine("Min: {0}, Max: {1}", tuples.Min, tuples.Max);

위 코드의 실행 결과는 아래와 같습니다.

Sorted List
10 100.1
10 1000.1
40 100.4
50 200.5
70 2100.7
80 20.8

Min: (10, 100.1), Max: (80, 20.8)