[자료구조] 템플릿 함수, 컨테이너 클래스(Bag), C++의 서브타입과 상속

템플리 함수

- 클래스와 함수의 재사용에 기여

- 소프트웨어 개발 시간과 저장 공간을 절약

 

예시

template <class T>
void SelectionSort(T *a, const int n)
{ // a[0]부터 a[n-1]까지 정렬
    for (int i = 0; i < n; i++)
    {
        int j = i;
        // a[i]에서 a[n-1]까지 중 가장 작은 수 찾기
        for (int k = i + 1; k < n; k++)
            if (a[k] < a[j])
                j = k;
        swap(a[i], a[j]);
        //swap 함수 또한 템플릿화 시켜줘야 전체 함수가 올바르게 작동
    }
}

함수를 템플릿화 하면 기존 정수 대상으로만 작동했던 함수가 실수 대상으로도 작동

 

컨테이너 클래스

- 다수의 데이터 객체들을 수용 또는 저장하는 자료구조를 표현하는 클래스

- 객체들의 삽입, 삭제 가능

Bag(백)

• 동일한 원소가 여러번 나타남
• 원소 위치, 삭제 연산 시 무작위 원소가 제거
• 삽입 - 배열의 첫 번째 가용 위치에 저장, 배열이 가득 찼을 경우 크기를 2배 확장
• 삭제 - 배열 랜덤 위치에서 원소 삭제, 그 오른쪽 모든 원소는 한 자리씩 왼쪽으로 이동

 

구현

template <class T>
class Bag
{
public:
    Bag(int bagCapacity = 10); // 생성자
    ~Bag();                    // 소멸자

    int Size() const;     // Bag의 원소 수 리턴
    bool IsEmpty() const; // Bag이 비어 있으면 true, 아니면 false
    T& Element() const;   // bag의 무작위 원소 리턴
    
    void Push(const T&); // 원소 삽입
    void Pop();           // 원소 삭제

private:
    T *array;     // 원소 배열
    int capacity; // Bag의 크기
    int top;      // top의 위치
};

 

함수 구현

template <class T>
Bag<T>::Bag(int bagCapacity) : capacity(bagCapacity)
{
    if (capacity < 1)
        throw "Capacity must be > 0";
    array = new T[capacity];
    top = -1;
}

template <class T>
Bag<T>::~Bag() { delete[] array; }

template <class T>
void Bag<T>::Push(const T &x)
{
    if (capacity == top + 1)
    {
        ChangeSize1D(array, capacity, 2 * capacity);
        // 배열의 크기 2배 확장
        capacity *= 2;
    }
    array[++top] = x;
}

template <class T>
void Bag<T>::Pop()
{
    if (IsEmpty())
        throw "Bag is empty, cannot delete";
    int deletePos = rand() % (top + 1);
    copy(array + deletePos + 1, array + top + 1, array + deletePos);
    // 원소 삭제
    array[top--].~T(); // T의 소멸자
}

template <typename T>
void ChangeSize1D(T *&a, int size)
{
    T *newArray = new T[size];
    int copySize = min(size, capacity);
    for (int i = 0; i < copySize; i++)
    {
        newArray[i] = a[i];
    }
    delete[] a;
    a = newArray;
}

 

C++의 서브 타입과 상속

상속 - 추상 데이터 타입간의 서브타입 관계를 표현

IS~A 관계

 

Bag과 Stack, Queue의 관계

Bag - 단순이 원소들이 삽입과 삭제가 될 수 있는 자료구조

Stack - 원소들이 후입선출 순서에 따라 삭제되는 자료구조

Queue - 선입선출 순서로 원소가 삭제되어야 하므로 Bag보다 세분화 된 자료구조

 

→ Stack, Queue는 Bag의 하나(IS-A) 즉, Stack, Queue는 Bag의 서브타입

 

Bag, Stack 구현

class Bag
{
public:
    Bag(int bagCapacity = 10);
    virtual ~Bag();

    virtual int Size() const;
    virtual bool IsEmpty() const;
    virtual int Element() const;

    virtual void Push(const int);
    virtual void Pop();

protected:
    int *array;
    int capacity;
    int top;
};

class Stack : public Bag
{
public:
    Stack(int stackCapacity = 10);
    ~Stack();
    int Top() const;
    void Pop();
};

 

Stack의 함수 구현

Stack::Stack(int stackCapacity) : Bag(stackCapacity) {}
// 스택은 백의 생성자 호출

Stack::~Stack() {}
// 스택의 소멸자가 호출되면 자연스럽게 백의 소멸자가 호출됨

int Stack::Top() const
{
    if (IsEmpty())
        throw "Stack is empty.";
    return array[top];
}

void Stack::Pop()
{
    if (IsEmpty())
        throw "Stack is empty. Cannot delete.";
    top--;
}