자체 구현 컨테이너 클래스 만들기

STL의 장점

 * STL은 풍부한 기능들을 지원한다.

 * 다양한 플랫폼에서 쓸 수 있는 대체적으로 안정적인 구현들이 존재한다.

 * 거의 모든 C++ 컴파일러는 STL을 표준으로서 지원한다.

STL의 단점

 * STL은 처음에 배우기기 힘들다.

 * 구체적인 목적을 위한 자료구조에 비해 성능이 떨어진다.

 * 대부분의 경우 자체 제작한 자료 구조보다 메모리를 더 많이 먹는다.

 * 동적 메모리 할당을 많이 사용하다.

 * 여러 플랫폼을 지원하는 엔진에서 사용하기 힘들다.

1. 동적 배열과 메모리 할당

  동적 할당은 느리기 때문에 동적 배열은 개발기간에 사용하고 버퍼의 크기를 알게 되면 고정크기 배열로 바꾸어 사용하는 것도 좋다.

2. 연결 리스트

  ⓐ 고려사항

    - 빈 리스트에 첫 요소를 추가하는 경우

    - 현재의 머로 요소 앞에 새 요소를 추가하는 경우

    - 현재의 꼬리 요소 뒤에 새 요소를 추가하는 경우

    - 중간에 요소를 추가하는 경우

  ⓑ 링크 자료구조

template< typename ELEMENT >

struct Link

{

Link<ELEMENT>* m_pPrev;

Link<ELEMENT>* m_pNext;

Link<ELEMENT>* m_pElem;

};

  ⓒ 돌출 리스트 (extrusive list)

    - Link 자료구조와 요소 자료 구조가 완전 별개인 연결리스트 이다.

    - 연결리스트에 요소가 추가될 때면 링크를 하나 새로 할당하고 요소에 대한 포인터 및 다음과 이전 링크에 대한 포인터를 맞게 설정한다.

    - 장점은 한 요소가 동시에 여러 연결리스트에서 포함할 수 있다는 것이다.

    - 단점은 링크 객체를 동적할당 해야한다는 것이다. 링크는 언제나 크기가 같기 때문에 풀할당자를 사용하는 경우가 많다.

  ⓓ 함몰 리스트 (Instrusive list)

    - Link 자료구조가 요소의 자료구조 안에 포함되는 연결 리스트다.

    - 링크 객체를 동적 할당하지 않아도 되는 이점이 있다.

    - Link 안에는 요소를 가리키는 포인터가 있어야 하지만, 상속을 사용하면 없어도 된다.

  ⓓ 머리와 꼬리 포인터 : 순환리스트

    - Head 포인터와 tail 포인터를 가지고 있으면 삭제나 추가 시 복잡해진다.

    - 그러므로 이 두개의 포인터를 m_root포인터로 합치면 순환하는 리스트가 된다.

  ⓔ 단순 연결 리스트

    - 이전을 가리키는 포인터가 없기 때문에 제거 동작은 O(n)이고 이중연결리스트에선 O(1)이다.

    - 리스트의 Head나 Tail에서 제거 동작이 발생하는 경우에는 단순 연결로 메모리를 절약할 수 있다.

3. 사전과 해시 테이블

사전은 키-값 쌍의 테이블이다. 

사전은 대부분 이진트리나 해시테이블을 사용하는다.

이진트리의 검색 연산은 O(logn)이다.

해시 테이블은 키를 정수형태로 변환하고 모듈로(modulo) 연산으로 검색하기 때문에 O(1)이다.

  ⓐ 충돌 : 개방형 해시 테이블과 폐쇄형 해시 테이블

    - 개방형 해시 테이블은 충돌을 해결하기 위해 단순하게 인덱스 하나에 여러개의 키-값 쌍을 저장하는 방식을 쓴다.

    - 구현하기 쉽고 저장할 수 있는 키-값 쌍의 수에도 제약이 없지만 새로운 키-값 쌍을 추가할 때 동적 메모리 할당이 발생한다.

  

    - 폐쇄형 해시 테이블은 충돌이 발생하면 빈 슬롯을 찾을 때 까지 탐지하는 과정을 반복한다.

    - 구현이 까다롭고 키-값 쌍의 수에 제한이 있다. 하지만 정해진 양만큼의 메모리를 사용하고 동적 메모리 할당이 필요 없다.

  ⓑ 해시 값 계산

    - 해시 값 계산(Hashing)은 임의의 데이터 타입인 키 값을 정수로 부꾼 후 이 정수와 테이블 크기를 모듈로 연산해 테이블에 대한 인덱스를 얻는 과정이다.

    h = H(k)    i = h mod N

    - 해시 테이블의효율성은 해시 함수 품질에 달려 있다. 좋은 해시 함수란 모든 키값을 테이블 전체에 고르게 배분하는 함수이고, 충돌을 최소화 한다.

    - 결정적이어야 한다. 입력이 같으면 그 출력도 같아야 한다.

  ⓒ 폐쇄형 해시 테이블 구현

    - 폐쇄형 해시 테이블 상식에서는 키-값 쌍을 각 테이블 항목마다 하나씩 연결 리스트에 저장하는것이 아니라 테이블 안에 직접 저장한다.

    - 이렇게 되면 해시 테이블을 사용할 메모리 양을 미리 정확히 알 수 있다.

    - 충돌이 일어나서 탐자 과정을 할때 가장 간단한 방식은 선형 탐지다. 충돌이 일어난 곳 부터 하나씩 탐지하는 것이다.

    ( 요소들이 뭉치게 된다.)

    - 그래서 이차 탐지 알고리즘을 쓰는데 하나씩이 아니라 i의 제곱씩 늘려가며 탐색한다.

    - 폐쇄형 해시는 크기를 소수로 하는 것이 좋다. 이차 탐색을 했을 때 고르게 배치 할 수 있다.