[Design Pattern] Container

Linked List와 같은 Container를 만들때 사용하는 전통적인 기법과 이에 대한 장점을 활용하고, 단점을 극복하는 방법에 대해 알아보자.

Single Linked List의 예

#include <iostream>
using namespace std;

struct Node
{
    int data;
    Node* next;
    Node(int d, Node* n) : data(d), next(n) {}
};

class slist
{
    Node* head = 0;
public:
    void push_front(int n) { head = new Node(n, head); }
    int front() { return head->data; }
};

int main()
{
    slist s;
    s.push_front(10);
    s.push_front(20);
    s.push_front(30);
    s.push_front(40);
}

생성자를 잘 활용하면 위와 같이 아주 간단하게도 Single linked list를 구현할 수 있다. 이 예제의 자료 형태를 도식화 해보면 아래와 같다. 

Node 객체의 형태

main 함수 실행시의 메모리 형태

이 예제에서는 int 데이터 하나 밖에 저장 할 수 없다. 다양한 형태의 자료를 저장하려면 어떻게 해야할까? 

 

1. 기반 클래스의 포인터를 저장하는 컨테이너 (전통적인 방법)

#include <iostream>
using namespace std;

struct object
{
    virtual ~object() {}
};
// 모든 클래스는 object로부터 파생되어야 한다. 규칙!

class Dialog : public object {};
class Point : public object {};
class Rect : public object {};

// Primitive type을 사용할 수 없어 별도로 다시 만들어줘야한다.
class integer : public object
{
    int value;
public:
    integer(int n) : value(n) {}
};

struct Node
{
    // object 적용
    object data;
    Node* next;
    Node(int d, Node* n) : data(d), next(n) {}
};

class slist
{
    Node* head = 0;
public:
    void push_front(object* n) { head = new Node(n, head); }
    object* front() { return head->data; }
};

int main()
{
    slist s;
    /*s.push_front(10);
    s.push_front(20);
    s.push_front(30);
    s.push_front(40);*/

    s.push_front(new Point);
    s.push_front(new Point);

    slist s2;
    s2.push_front(new Dialog);

 	// * 문제점1 * 
    // Point를 넣는 컨테이너에 Dialog를 넣어도 에러가 발생하지 않는다.
    s.push_front(new Dialog);

	// * 문제점2 * 
    // 반드시 캐스팅이 필요하다.
    //Point* p = s.front(); // Error! casting이 필요하다.
    Point* p = static_cast<Point*>(s.front());
    
    // * 문제점3 * 
    // 프리미티브 타입을 사용할 수 없다. 프리미티브 타입은 object의 파생클래스가 아니므로 사용할 수 없다.
    // -> 프리미티브 타입 저장을 위한 별도의 타입을 사용할 수 있다. -> integer
    // s.push_front(10); // Error!
    s.push_front(new integer(10));  // ok.
}

이 방식의 특징은 자료형의 기반 클래스(object)를 만들고 모든 자료형들이(Dialog, Point, Rect, integer) 이 기반 클래스를 상속 받아 사용하는 것을 강제하는 것에 있다. 이 방식의 장, 단점은 다음과 같다.

장점

코드 메모리가 증가하지 않는다. (Tamplate가 아니므로)

단점

[문제점1] 타입 안정성이 떨어진다. 
[문제점2] 컨테이너에서 요소를 꺼낼 때, 반드시 캐스팅 해야한다.
[문제점3] int, double과 같은 Primitive type은 저장할 수 없다. 별도의(integer) object 파생 클래스가 필요하다.
Point를 저장하는 목적의 Container에 Dialog를 넣는 실수가 발생해도 에러가 발생하지 않는다.

2. Template 기반의 Container 방식

#include <iostream>
using namespace std;

//struct Node
template<typename T> struct Node
{
    T data;
    Node* next;
    Node(const T& d, Node* n) : data(d), next(n) {}
};

template<typename T> class slist
{
    Node<T>* head = 0;
public:
    void push_front(const T& n) { head = new Node<T>(n, head); }
    T front() { return head->data; }
};

int main()
{
    //slist s;
    slist<int> s
    s.push_front(10);
    s.push_front(20);
    s.push_front(30);
    s.push_front(40);

    // 타입을 달리하여 변수를 생성할때마다 다른 클래스가 생성되는 것.
    // 즉 코드 메모리가 증가한다.
    slist<Point> s2;
    
    //s.push_front(new Dialog); // Error!
}

Template이 사용되어 이제 slist에서 어떤 타입이든지 사용할 수 있다. 이 방식도 장점, 단점을 정리해보면 아래와 같다.

장점

타입 안정성이 뛰어나다.
Container에서 요소를 꺼낼 때, Casting이 필요없다. 
int, double 등의 Primitive type을 저장할 수 있다.

단점

Template이 사용되어 타입을 달리하여 slist 인스턴스를 생성할 때마다 다른 클래스 코드가 생성되어 코드 메모리가 증가한다.

그렇다면 [기반 클래스의 포인터를 저장하는 컨테이너], [Template 기반의 Container 방식] 의 장점을 조합하고 단점을 극복하는 방법은 없을까?

3. void pointer의 사용한 방식

#include <iostream>
using namespace std;

struct Node
{
    void* data;	// 저장할 데이터에 void pointer가 사용되었다.
    Node* next;
    Node( void* d, Node* n) : data(d), next(n) {}
};

class slistImp
{
    Node* head = 0;
public:
    void push_front(void* n) { head = new Node(n, head);}
    void* front()           { return head->data;}
};

template<typename T> class slist : public slistImp
{
public:
    inline void push_front(T n) { slistImp::push_front( (void*)n);}
    inline T front()           { return (T)(slistImp::front());}
};


int main()
{
    slist<int> s;

    //s.push_front((void*)10);    // 입력 이후 단계에서 캐스팅이 되므로 캐스팅이 필요없다.
    s.push_front(10);
    s.push_front(20);
    s.push_front(30);
    s.push_front(40);
    s.push_front(50);

    int n = s.front();
}

입출력 단계에서 void pointer를 한번 더 거치게 되는것에 대한 성능 우려를 inline의 사용으로 극복한다. 이로인해 코드가 기계어 코드로 치환되어 버리니 성능저하가 발생하지 않는다.

사용자 입장에서는 템플릿 같지만, 링크드리스트 내부에서는 void*를 사용했기 때문에 결국 내부 구조 상에는 템플릿이 없고 인라인을 사용했기 때문에 코드들이 치환되어 지워진다. 

-> void*를 사용하는 컨테이너와 완벅기 똑같은 메모리 구조.
-> 사용자 입장에서는 템플릿 버전처럼 보인다. 
-> 사용하기 편리하면서도 메모리 사용량을 줄일 수 있다.
-> Thin template라고 한다. 

Thin template 기반 컨테이너

- 템플릿에 의한 코드 중복을 줄이기 위한 기술
- void* 등으로 내부 자료구조를 구성하고, 캐스팅을 위한 템플릿을 제공한다.
- Symbian OS, Android등 모바일 용 라이브러리에서 많이 사용하는 기술

C++ IDioms

 - C++에서 널리 사용되는 기법에 이름을 붙인것