[ 개발 잡소리 ] 제네릭과 템플릿

이게 뭐지?

제네릭은 C#에 존재하는

namespace인데 이는 여러 유용한 자료구조 클래스들을 지원해 주고

이런 것들에는 List, Queue, Stack, Dictionary가 있다.

 

이런 자료형에 대한 부분 중에 Stack과 Queue는 다른 글에서 앞서 설명한 적이 있으니 생략하고

List와 Dictionary에 대한 설명을 하겠다.

 

---

List

List는 길이에 제약을 받지 않는 가변길이 배열이다.

C++로 치면 vector에 해당하는 개념인 것이다.

사용 예제는 이러하다. 

List<int> numberList = new List<int>();

일반적인 정적 배열과는 달리 가변길이 배열이기 때문에

Add나 Remove와 같은 메서드를 통해 리스트의 요소들을 쉽게 관리할 수 있다.

 

하지만 이 List가 편하고 좋다고 완전히 배열을 대체해서 쓴다는 생각은 하면 안 된다

배열이 정적배열인 이유는 크기가 한번 할당되면 확장할 수 없기 때문인데

List는 새로운 값이 추가되면 다른 메모리공간에 새로 할당하는 오버헤드가 조금씩 발생하게 된다.

따라서 List의 잦은 크기 변경을 자제 해야한다.

되도록 배열을 사용할 수 있다면 배열을 지향해 보도록 하자.

 

값이 변경되는 경우는 3가지 정도가 있는데

Add, Remove와 Insert 메서드를 활용하는 경우가 있다.

 

Add()의 경우.

만약 배열의 사이즈와 요소의 개수와 같으면. (값을 여기서 더 추가했을때 넘칠 것같으면.)

public void Add(T item)
{
    if (_size == _items.Length)
        EnsureCapacity(_size + 1);

    _items[_size++] = item;
    _version++;
}

배열 크기를 두배로 늘린다.

그리고 새로운 요소를 끄트머리 인덱스에 추가한다.

 

Insert()의 경우 좀더 번거로운 작업이 필요하다.

앞의 작업에 더불어, 마지막 요소에 추가하는 것이 아닌, 중간에 집어 넣는 것 이기 때문에.

그 인덱스 기준으로 뒤의 모든 요소를 뒤로 한칸씩 시프트하고. 그 인덱스에 새로운 값을 삽입한다.

따라서 시간 복잡도는 O(n)이다.

 

Remove()의 경우. 들어온 매개변수의 아이템의 인덱스를 먼저 찾아야하기 때문에 벌써 O(n)이 발생한다.

그리고 그 인덱스의 값을 지운 후 뒤의 요소들을 모두 앞으로 당겨야하는 작업을 거친다.

따라서 총 시간복잡도는 O(n)이다.

 

---

 

Dictionary

Dictionary는 key, value가 1대 1로 할당된 C++로 치면 map과 같은 개념의 자료구조이다.

값 탐색 방식은 Map은 트리형식이고 Dictionary는 배열과 매핑된 해시테이블로 탐색하는

형식으로 조금 다르긴 한데. 사용하는 형태는 유사하기에 설명해보겠다.

이런 식으로 Key와 Value가 한쌍으로 할당되는 구조이며 Key값은 중복될 수 없다는 규칙을 가지고 있다.

Add나 Remove로 내부 값들을 추가하고 삭제. 배열에서 쓰는 것과 같이

private Dictionary<int, string> _dictionary;

_dictionary[2] => Value반환

이런 식으로 대괄호 안에 Key값을 넣어 Value값을 찾아올 수 있다.

 

어 그럼 없는 키를 넣어서 Value를 찾아오려 하면 코드도 박살 나고 인생도 끝나는 게 아닌가?

걱정하지 마시라. TryGetValue()라는 함수가 있다. 키를 넣고 out으로 Value를 받을 수 있는데

기본적으로 bool 값을 반환하여 if문을 통해 한 번 걸러주기 위함이다. 

private Dictionary<int, string> _dictionary;

if (_dictionary.TryGetValue(1, out string ming))
{
    // 키 값이 있을때,  out으로 받은 ming으로 뭔가 해주면 됨
}
else
{
    // 예외 처리가능
}

 

 

하지만 Dictionary 또한 List와 같이 기본적으로 차지하는 메모리 용량이 있는데

72 Byte나 잡아먹는다. List보다 더더욱 자주 쓰는게 안좋을 수 있다.

 

중간에 자주 쓰면 안 된다, 뭐 이런 식으로 부정적으로 얘기해서 그렇지

여기서 자주 쓰지 말라는 것은

Memory usage of Dictionaries in C#

stackoverflow 글

이런 짓을 하지 말라는 뜻이지 아예 쓰면 안 된다거나 한다는 건 아니다.

탐색도 빠르고 좋은 자료구조인데 쓸데는 써야 함.

---

 

물론 그만큼 리사이징에 드는 비용또한 리스트와 비슷하게 값 배열을 동적으로 옮겨서 쓰기 때문에 비슷하게 든다.

내부적으로 해시값을 기반으로 인덱스를 매핑하는 배열인  int[] buckets 이 존재하고. 실제 값을 담는 배열인

Entry[] entries 이 존재한다.

Entry는 Key, Value, HashCode, Next를 포함한 구조체이다.

 

 

 

• 키에 대해 해시코드를 구함 → hash = key.GetHashCode() & 0x7FFFFFFF
  (&는 음수를 막기 위한 마스킹)
• index = hash % buckets.Length → 버킷 선택
• buckets[index]를 따라가서 entries 배열의 인덱스를 가져옴
• 해당 버킷에 충돌이 없으면 새 Entry 추가
• 충돌이 있으면, entries[i].next를 따라가며 체이닝(Chaining) 방식으로 연결

 

만약 값 추가가 일어나게 될 때 :

1. 키에 대한 해시코드를 구한다.

hash = key.GetHashCode() & 0x7FFFFFFF

 

2. 버킷에서 해시에 대한 인덱스를 찾는다

index = hash % buckets.Length

 

3. 버킷 배열에서 entries배열의 인덱스를 가져온다

- 버킷 충돌이 없으면 새 Entry를 추가하고 충돌이 있으면 entries[i]의 next값을 따라가며 Linked-List 에서 사용하는 체이닝 방식으로 뒤에 연결하게 된다.

 

그럼 버킷충돌은 무엇이고 왜 일어나게 되는것일까??

 

버킷이 충돌이 나려면 분명 다른 Key값이지만 해시코드를 뽑아서 인덱싱을 하고 나면

같은 인덱스를 가리키게 되는 문제를 의미한다.

예를 들면 이러하다.

var dict = new Dictionary<string, int>();
dict["cat"] = 1;
dict["tac"] = 2;

 

* "cat".GetHashCode() → 해시값 12345 → 버킷 3번

* "tac".GetHashCode() → 해시값 67890 → 버킷 3번

 

따라서 이런 경우에는 체이닝 방식으로 next를 따라가며 최종적으로 마지막에 요소를 추가하게 된다

 

일반적인 Linked-List라면 이렇게 구현되었을 것이다.

하지만 여기서 사용하는 체이닝 기법은 일반적인 Linked-List와 같이 다음 클래스를 가리키는 포인터를

가리키는 것이 아닌 그냥 단순히 이 다음 인덱스만을 가리키게 된다. 즉 next는 그냥 int로된 index를 의미한다.

따라서 더 단순하게 그냥 배열기반의 인덱스 체인 방식을 사용한다.

그나마 빠르고 메모리 친화적으로 해결했다고 볼 수 있다.

---

 

어 그런데 자꾸 막 꺾쇠가 막 중간중간에 박히고 자료형을 넣는데 이건 왜 쓰는 거지?

 

그것은 템플릿. T 자료형이다.

템플릿은 딱히 정해진 자료형이 아닌 여러 자료형에서 같은 형식의 동작을 수행하고 싶을 때 사용한다.

템플릿은 위의 제네릭클래스들을 사용하기 위해서 꼭 필요한 개념이다.

 

간단히 두 수를 더해주는 함수를 작성한다고 쳐보자

int Add(int a, int b)
{
    return a + b;
}

 어? 근데 만약 float의 합을 계산하는 함수도 필요하다면

int Add(int a, int b)
{
    return a + b;
}
float Add(float a, float b)
{
    return a + b;
}

이렇게 함수를 오버로딩하여 작성할 순 있다.

하지만 이런 식으로 모든 자료형마다 똑같은 처리를 하는 것은 하드코딩이 될 수 있다.

 

코드에서 반복되는 부분이 보이면 줄이고 싶어 하는 개발자들의 고집으로 인해 존재하는 기능기도한데 

T Add<T> (T a, T b)
{
    return a + b;
}

이렇게 해준다면 자료형에 제약을 받지 않고 Add함수를 통해 더해진 값을 받을 수 있을 것이다.

 

일단 템플릿 T을 사용하는 것은 이런 이유로 쓰는 것인데.

하지만 저렇게 그대로 쓰게 되면 문제가 생긴다.

T에는 어떤 자료형이든 들어갈 수 있다고 했는데. 만약 + operator가 오버로딩되어있지 않는

자료형이 들어가는 경우에 문제가 생길 수 있다. 따라서 아마 이 코드를 작성하게 되면

이런 오류가 무조건 뜰 것이다.

 

public T Add<T>(T a, T b)
{
    dynamic A = a;
    dynamic B = b;
    return A + B;
}

이렇게 하는 방법이 있긴 하지만.

자료형에 대한 모호성이 발생하고 실수로 +operator 로버로딩을 하지 않은 자료형이 들어가면

발작하며 오류를 내뱉는 코드가 되기 때문에 보통 저런 단순 연산을 하는데에 T 자료형을 쓰지는 않는다.

(어디까지나 예시를 위함)