티스토리 뷰
[C#/Collection] Dictionary<TKey, TValue>, SortedDictionary<TKey, TValue> 분석
KIBBOMI 2021. 8. 12. 22:53C# Collection에 속한 Dictionary<TKey, TValue> 클래스에 대해서 살펴보겠습니다.
https://docs.microsoft.com/ko-kr/dotnet/api/system.collections.generic.dictionary-2?view=net-5.0
Dictionary<tkey,tvalue> 클래스 (System.Collections.Generic)</tkey,tvalue>
키와 값의 컬렉션을 나타냅니다.Represents a collection of keys and values.
docs.microsoft.com
SortedDictionary<tkey,tvalue> 클래스 (System.Collections.Generic)</tkey,tvalue>
키에 따라 정렬된 키/값 쌍의 컬렉션을 나타냅니다.Represents a collection of key/value pairs that are sorted on the key.
docs.microsoft.com
정확한 자료는 위 링크의 MSDN에 있고 이 중에서 PS에 도움되는 부분만 추출해서 설명하도록 하겠습니다.
주로 알고리즘 문제풀이에서 Dictionary(map)은 삽입, 삭제, 존재 유무 정도만 사용합니다. 생성도 대부분 텅 빈 map을 선언하고..
문제풀이에서 사용하는 부분과 조금 C#적인 부분도 함께 살펴보고 글을 마무리 하겠습니다.
1. Dictionary<TKey, TValue>의 특성
C++의 map과 같은 부류입니다. 차이점은 TKey를 정렬하지 않는다는 점입니다. C++에서는 Key기준으로 정렬을 해주기 때문에 기본 자료형이 아닌 따로 선언한 구조체, 클래스라면 bool operator<(const class &other)를 구현해주어야 했습니다. 이것처럼 Dictionary도 TKey가 동일한지 비교하는 인터페이스를 구현해야만 합니다. (IEqualityComparer)
삽입과 삭제는 O(1)로 동작합니다.
2. Dictionary<TKey, TValue> 매서드
2.1. 생성자
문제풀이에서 사용하는 주요 생성자는 대부분 빈 dictionary 입니다.
물론 복사 생성자도 존재합니다. 또, IEuqalityComparer를 매개변수로 받는 생성자도 있습니다.
특수한 상황에서 쓰기 때문에 다음에 알아보도록 하겠습니다.
빈 생성자는 다음과 같이 선언합니다.
//key : int, value : int
Dictionary<int, int> map = new Dictionary<int, int>();
//Key : string, value : int
Dictionary<string, int> map = new Dictionary<string, int>();
2.2. 삽입
삽입은 .Add(TKey, TValue)을 사용합니다.
이름대로 TKey는 Key를, TValue는 Value를 지정합니다. 중요한 부분은 중복되는 Key가 있을 때 Argument Exception을 던집니다.
다음 코드는 간단히 10개의 값을 삽입하는 코드입니다.
using System;
using System.Collections.Generic;
namespace PS
{
class Solution
{
static void Main(string[] args)
{
Dictionary<int, int> map = new Dictionary<int, int>();
Random r = new Random();
for(int i=0; i<10; ++i)
{
try
{
map.Add(r.Next() % 10, r.Next() % 100);
}
catch(ArgumentException e)
{
Console.WriteLine(e.Message);
}
}
Console.WriteLine("Adding is finished");
foreach(var item in map)
{
Console.WriteLine($"({item.Key}, {item.Value})");
}
}
}
}
Try-catch문에서 예외를 받아 잘 처리하는 것을 볼 수 있습니다. Try-catch문을 사용해주지 않으면 예외를 발생시키고 프로그램이 종료됩니다.
특별한 점은 C++처럼 Key순서대로 정렬되어 있지 않다는 점 입니다.
2.3. 삭제
삭제는 .Remove(Key)를 사용합니다.
using System;
using System.Collections.Generic;
namespace PS
{
class Solution
{
static void Main(string[] args)
{
Dictionary<int, int> map = new Dictionary<int, int>();
map.Add(1, 10);
map.Add(2, 20);
map.Add(4, 40);
map.Add(6, 60);
map.Add(8, 80);
foreach(var item in map)
Console.WriteLine($"({item.Key}, {item.Value})");
Console.WriteLine();
map.Remove(1);
map.Remove(5);
Console.WriteLine("---after removing---");
foreach (var item in map)
Console.WriteLine($"({item.Key}, {item.Value})");
}
}
}
위 코드의 결과대로, key 1를 가지는 원소가 삭제되었고, Key 5는 찾을 수 없어서 아무런 동작도 하지 않았습니다.
지우고자 하는 Key가 존재한다면 삭제, 그렇지 않으면 아무런 일도 일어나지 않습니다.
.Remove(Key)뿐만 아니라 오버로딩된 함수 중에 .Remove(Key, out Value)도 있습니다. 이 매서드는 key가 Dictionary에 존재하는 경우 삭제하고, 그 값을 Value에 저장합니다.
3. 비교자
다른 collection에도 있었던 것 처럼 비교자가 필요합니다.
<Key, Value> 쌍을 삽입하려고할 때 Dictionary는 Key가 이미 존재하는지, 아닌지 판단합니다.
이때, 기본 자료형 같은 경우는 이미 구현이 되어있기 때문에 괜찮은데 사용자가 직접 정의한 Class나 구조체에 대해서는 이를 정의해줄 필요가 있습니다.
C++에서는 bool operator==(const Class &other)const{}가 되겠습니다.
C#에서는 IEqualityComparer<T> 인터페이스를 구현하면 됩니다. (friend를 사용해서 구현한 operator==와 비슷한 역할)
그래서 IEqualityComparer를 구현하지 않고 Dictionary에 삽입하면 다음과 같은 결과가 나옵니다.
using System;
using System.Collections.Generic;
namespace PScs
{
class Point
{
public Point() { }
public Point(int x_, int y_) { x = x_; y = y_; }
public int x { get; set; }
public int y { get; set; }
}
class Solution
{
static void Main(string[] args)
{
Dictionary<Point, int> circle = new Dictionary<Point, int>();
circle.Add(new Point(1, 2), 3);
circle.Add(new Point(1, 2), 5);
foreach (var item in circle)
Console.WriteLine($"Key : ({item.Key.x}, {item.Key.y}) Value: {item.Value}");
}
}
}
이처럼 Key가 동일함에도 불구하고 제가 정의한 Point class에 '두개의 값이 동일한지' 알아낼 방법(기준)이 없어서 두개의 동일한 키가 Dictionary에 삽입되어 있습니다.
이를 해결하기 위해서 IEqualityComparer<T>를 구현해줍시다.
SortedSet<T>에서 정렬순서를 변경해줄 때, IComparer를 구현해줬던 것 처럼 해줍시다.
(별도의 비교자 클래스를 만들어야 함.)
using System;
using System.Collections.Generic;
namespace PScs
{
class Point
{
public Point() { }
public Point(int x_, int y_) { x = x_; y = y_; }
public int x { get; set; }
public int y { get; set; }
}
class PointEqualityComparer : IEqualityComparer<Point>
{
public bool Equals(Point lhs, Point rhs)
{
if (lhs == null && rhs == null)
return true;
else if (lhs == null || rhs == null)
return false;
else if (lhs.x == rhs.x && lhs.y == rhs.y)
return true;
else
return false;
}
public int GetHashCode(Point obj)
{
int hCode = obj.x ^ obj.y;
return hCode.GetHashCode();
}
}
class Solution
{
static void Main(string[] args)
{
Dictionary<Point, int> circle = new Dictionary<Point, int>(new PointEqualityComparer());
circle.Add(new Point(1, 2), 3);
Console.WriteLine("new Point(1, 2), 3 is added!");
circle.Add(new Point(1, 2), 5);
Console.WriteLine("new Point(1, 2), 5 is added!");
foreach (var item in circle)
Console.WriteLine($"Key : ({item.Key.x}, {item.Key.y}) Value: {item.Value}");
}
}
}C++에서 두개의 class를 어떨때 같다고 할 수 있는지, 구분하기 위해 operator==를 정의해주는 것과 같습니다.
위의 class에서는 x, y가 같다면 동일하다고 정의했습니다.
이 처럼 첫번째 key는 삽입되었지만, 두번째 동일한 key가 삽입되면 예외를 던지는 것을 볼 수 있습니다.
삽입하는 Class에 IEquatable<T>를 구현해서 Equals(Class other)로 비교할 수 있지 않을까 생각되지만 IEuqalityComparer<T>로 비교해야 dictionary가 제대로 동작합니다.
삽입과 삭제의 시간복잡도는 모두 O(1)로 동작합니다.
4. SortedDictionary<TKey, TValue>
마지막으로 SortedDictionary를 보겠습니다. 위의 dictionary(map)은 Key를 정렬하고 있지는 않습니다.
SortedSet과 마찬가지로, SortedDictionary<TKey, TValue>는 IComparer<TKey>를 구현하여 인자로 넘겨주어야 합니다.
그 외, 사용점은 Dictionary와 동일합니다.
정렬방법도 SortedSet과 동일하게 IComparer를 구현해주면 됩니다.
using System;
using System.Collections.Generic;
namespace PScs
{
class Point
{
public Point() { }
public Point(int x_, int y_) { x = x_; y = y_; }
public int x { get; set; }
public int y { get; set; }
}
class Comparer : IComparer<Point>
{
public int Compare(Point lhs, Point rhs)
{
//ascending
if (lhs.x < rhs.x)
return -1;
else if (lhs.x == rhs.x)
{
if (lhs.y < rhs.y)
return -1;
else if (lhs.y == rhs.y)
return 0; //Equal
else
return 1;
}
else
return 1;
}
}
class Solution
{
static void Main(string[] args)
{
SortedDictionary<Point, int> circle = new SortedDictionary<Point, int>(new Comparer());
var rd = new Random();
for(int i=0; i<20; ++i){
try
{
circle.Add(new Point(rd.Next() % 10, rd.Next() % 10), rd.Next() % 50);
}
catch(ArgumentException e)
{
Console.WriteLine(e.Message);
}
}
Console.WriteLine("---finished---");
foreach (var item in circle)
Console.WriteLine($"Key : ({item.Key.x}, {item.Key.y}) Value: {item.Value}");
}
}
}
위처럼 동일한 키는 IComparer에 의해서 구분되고 try-catch문에서 예외를 잘 처리해주고 있습니다.
문제풀이에서 사용하는 dictionary(map)은 딱 이정도인 것 같습니다. 또 필요한 부분이 있으면 추가하도록 하겠습니다.
'개발 > C#' 카테고리의 다른 글
| [C#/API] API 호출하기 (Json) (0) | 2021.09.02 |
|---|---|
| [C# / Collection] SortedSet<T>, HashSet<T>분석 (0) | 2021.08.09 |
| [C# / Collection] LinkedList<T> 분석 (0) | 2021.01.03 |
| [C#/JSON] JSON parser 구현 (0) | 2021.01.02 |
| [C#/ XML] XML parser 구현 (0) | 2021.01.01 |