[C++] 73. 최종 실습 – 확장 가능한 순차 배열

 

[C++] 최종 실습 – 확장 가능한 순차 배열

EhNara 프로그램에서는 EhNara 클래스, 학생 공장에서 학생 개체를 보관합니다. 그리고 장소에서는 사람 개체를 보관합니다. 여기에서는 순차적으로 보관할 수 있는 확장 가능한 배열을 템플릿으로 정의합시다.

확장 가능한 배열은 저장소가 꽉 차면 내부에서 저장소의 크기를 늘려 주어 사용하는 개발자가 저장소의 크기에 신경을 쓰지 않고 사용할 수 있는 동적 배열입니다.

여기에서는 순차 보관하는 기능과, 특정 인덱스의 요소를 제거, 특정 알고리즘이 참인 인덱스를 구하는 등의 기능을 제공하는 확장 가능한 배열을 만듭시다.

template <typename data>
class SeqArray
{
먼저 저장소와 저장소의 크기, 보관 개수를 기억하고 있어야 합니다.
    data *base; //저장소
    size_t capacity; //저장소 크기
    size_t size; //보관 개수
public:

생성자에서는 멤버 필드의 값을 0으로 초기화합시다.
    SeqArray()
    {
        base = 0;
        capacity = 0;
        size = 0;
    }

소멸자에서는 저장소를 할당하였을 때 저장소를 해제하는 구문이 필요하겠죠.
    ~SeqArray(void)
    {
        if(base)//저장소가 있을 때
        {
            delete[] base;//저장소 해제
        }
    }
순차 보관하는 메서드를 구현합시다.
    void PushBack(data value)//순차 보관
    {
꽉 차면 저장소를 늘려주어야 합니다.
        if(IsFull())//꽉차면
        {
현재 저장소의 크기가 0이 아니면 두 배로 늘리고 0이면 1로 늘리기로 합시다.
            if(capacity)//저장소의 개수가 참일 때
            {
                Reserve(capacity *2);//두 배로 확장
            }
            else//아닐 때(0일 때)
            {
                Reserve(1);//1로 확장
            }
        }
입력 인자로 받은 값을 순차 보관하고 보관 개수를 1 증가하세요.
        base[size] = value;//보관
        size++;//보관 개수 1 증가
    }

특정 인덱스 요소를 삭제하는 메서드를 구현합시다.
    void RemoveAt(size_t index)//특정 인덱스 요소 삭제
    {
인덱스가 유효하지 않으면 메서드를 종료합니다.
        if(IsAvailIndex(index)==false)//인덱스가 유효하지 않을 때
        {
            return;
        }
인덱스가 유효하면 보관 개수를 1 감소합니다. 그리고 인덱스 뒤의 값들을 한 칸씩 앞으로 이동합니다.
        size--;//보관 개수 1 감소
        for(   ;index<size;index++)
        {
            base[index] = base[index+1];//한 칸씩 앞으로 이동
        }
    }
특정 알고리즘이 처음으로 참인 위치를 찾는 메서드를 제공합시다. 특정 알고리즘은 find_if로 가정합시다.
    template <typename find_if>
    int FindIf(find_if fun)//특정 알고리즘이 처음으로 참인 위치 찾기
    {
순차적으로 입력 알고리즘에 보관한 값을 적용합니다.
        for(size_t i = 0; i<size; ++i)
        {
            if(fun(base[i]))//알고리즘에 적용하였을 때 참이면
            {
만약 참인 부분을 만나며 인덱스를 반환합니다.
                return i; //인덱스 반환
            }
        }
끝까지 반복해도 참인 부분을 만나지 못하면 -1을 반환합시다.
        return -1;//-1 반환
    }

인덱스 연산자를 중복 정의합시다.
    data &operator[](size_t index)//인덱서
    {
인덱스가 유효하지 않으면 예외를 던져줍니다.
        if(IsAvailIndex(index)==false)//유효하지 않은 인덱스일 때
        {
            throw "유효하지 않은 인덱스를 사용하였습니다.";//예외 던짐
        }
인덱스가 유효하면 해당 인덱스의 원소를 반환합니다.
        return base[index];//인덱스의 원소 반환
    }
유효한 인덱스인지 판별하는 메서드와 보관한 원소 개수를 반환하는 메서드를 제공합시다.
    bool IsAvailIndex(size_t index)const//유효한 인덱스인지 판별
    {
        return (index>=0)&&(index<size);
    }
    size_t GetSize()const
    {
        return size;
    }
private:
꽉 찼는지 판별하는 메서드도 구현하세요.
    bool IsFull()const//꽉 찼는지 판별
    {
        return size == capacity;
    }
저장소를 확장하는 메서드를 구현합시다.
    void Reserve(int ncapacity)//저장소 확장
    {
저장소의 위치를 임시 변수에 설정합니다.
        data *tbuf = base;//저장소 위치를 tbuf로 설정
새로운 저장소를 동적 할당합니다.
        base = new data[ncapacity];//저장소 동적 할당
저장소의 크기를 설정합니다.
        capacity = ncapacity;//저장소 크기 설정
        if(tbuf)//이전 저장소가 참이면
        {
이전 저장소가 있었다면 원래 보관한 값을 새로운 저장소에 보관합니다.
            for(size_t i=0; i<size;++i)
            {
                base[i] = tbuf[i];//이전 저장소에 보관한 값을 새로운 저장소로 이동
            }
이전 저장소의 메모리는 해제합니다.
            delete[] tbuf;//이전 저장소 메모리 해제
        }
    }
};

다음은 이를 테스트 하기 위한 코드를 포함한 전체 코드입니다.

//SeqArray.h
#pragma once
template <typename data>
class SeqArray
{
    data *base; //저장소
    size_t capacity; //저장소 크기
    size_t size; //보관 개수
public:
    SeqArray()
    {
        base = 0;
        capacity = 0;
        size = 0;
    }

    ~SeqArray(void)
    {
        if(base)//저장소가 있을 때
        {
            delete[] base;//저장소 해제
        }
    }

    void PushBack(data value)//순차 보관
    {
        if(IsFull())//꽉차면
        {
            if(capacity)//저장소의 개수가 참일 때
            {
                Reserve(capacity *2);//두 배로 확장
            }
            else//아닐 때(0일 때)
            {
                Reserve(1);//1로 확장
            }
        }
        base[size] = value;//보관
        size++;//보관 개수 1 증가
    }


    void RemoveAt(size_t index)//특정 인덱스 요소 삭제
    {
        if(IsAvailIndex(index)==false)//인덱스가 유효하지 않을 때
        {
            return;
        }
        size--;//보관 개수 1 감소
        for(   ;index<size;index++)
        {
            base[index] = base[index+1];//한 칸씩 앞으로 이동
        }
    }
    template <typename find_if>
    int FindIf(find_if fun)//특정 알고리즘이 처음으로 참인 위치 찾기
    {
        for(size_t i = 0; i<size; ++i)
        {
            if(fun(base[i]))//알고리즘에 적용하였을 때 참이면
            {
                return i; //인덱스 반환
            }
        }
        return -1;//-1 반환
    }
    data &operator[](size_t index)//인덱서
    {
        if(IsAvailIndex(index)==false)//유효하지 않은 인덱스일 때
        {
            throw "유효하지 않은 인덱스를 사용하였습니다.";//예외 던짐
        }
        return base[index];//인덱스의 원소 반환
    }
    bool IsAvailIndex(size_t index)const//유효한 인덱스인지 판별
    {
        return (index>=0)&&(index<size);
    }
    size_t GetSize()const
    {
        return size;
    }

private:
    bool IsFull()const//꽉 찼는지 판별
    {
        return size == capacity;
    }

    void Reserve(int ncapacity)//저장소 확장
    {
        data *tbuf = base;//저장소 위치를 tbuf로 설정
        base = new data[ncapacity];//저장소 동적 할당
        capacity = ncapacity;//저장소 크기 설정

        if(tbuf)//이전 저장소가 참이면
        {
            for(size_t i=0; i<size;++i)
            {
                base[i] = tbuf[i];//이전 저장소에 보관한 값을 새로운 저장소로 이동
            }
            delete[] tbuf;//이전 저장소 메모리 해제
        }
    }
};

//Program.cpp
#include <iostream>
using namespace std;
#include "SeqArray.h"

class FindFun
{
    int value;
public:
    FindFun(int value)
    {
        this->value = value;
    }
    bool operator()(int data)
    {
        return value == data;
    }
};


int main()
{
    SeqArray<int> sa;

    sa.PushBack(3);
    sa.PushBack(9);
    sa.PushBack(2);
    sa.PushBack(4);

    size_t size = sa.GetSize();
    for(size_t i = 0; i<size; i++)
    {
        cout<<sa[i]<<" ";//3 9 2 4
    }
    cout<<endl;

    sa.RemoveAt(2);
    size = sa.GetSize();
    for(size_t i = 0; i<size; i++)
    {
        cout<<sa[i]<<" ";//3 9 4
    }
    cout<<endl;

    FindFun ff(3);
    size_t index = sa.FindIf(ff);
    if(index!=-1)
    {
        cout<<3<<" is located at index "<<index<<endl;
        cout<<"sa["<<index<<"]:"<<sa[index]<<endl;
    }
    return 0;
}

▷ 실행 결과

3 9 2 4
3 9 4
3 is located at index 0
sa[0]:3