4. vector 만들기 [디딤돌 자료구조와 알고리즘 with C++]

4. vector 만들기

이번에는 STL의 vector를 모델 삼아 vector를 만들어 보기로 해요.

 

3장에서는 vector를 사용했습니다. 그 프로젝트에서 헤더파일 포함문과 using 문만 변경하세요.

//#include <vector>

//#include <algorithm>

//using std::vector;

//using std::find;

//using std::find_if;

#include "vector.h"

#include "algorithm.h"

using ehlib::vector;

typedef vector<Genre *> Genres;

typedef Genres::iterator GIter;

typedef Genres::const_iterator GCIter;

 

물론 vector.h 파일와 algorithm.h 파일을 프로젝트에 추가하세요.

 

현재 구현한 것이 없기 때문에 프로젝트를 다시 빌드하면 컴파일 오류가 날 거예요. 오류가 나는 것을 하나 하나 수정하여 컴파일 오류만 나지 않게 하세요. 물론 코드 내부는 비어있는 상태입니다.

 

3장에서 만든 세 개의 프로젝트에 적용하면 다음과 같은 형태로 작성하면 컴파일 오류가 발생하지 않아요. 이게 이번 장에서 작성할 vector와 알고리즘입니다.

 

#pragma once

namespace ehlib

{

    template<typename Data>

    class vector

    {       

    public:

        class iterator

        {    

        public:

            iterator(Data *pos=0)

            {        

            }

            Data operator *()const

            {

                 return 0;

            }

            int operator-(const iterator &iter)const

            {

                return 0;

            }

            iterator &operator++()

            {

                return (*this);

            }

            const iterator operator++(int)

            {

                iterator re(*this);

                return re;

            }

            bool operator !=(const iterator &iter)const

            {

                return false;

            }

            bool operator ==(const iterator &iter)const

            {

                return false;

            }

        };

        typedef iterator const_iterator;

 

 

 

        vector()

        {

        }

        ~vector()

        {        

        }

        void resize(size_t nsize,Data data=0)

        {

        }

        void push_back(Data data)

        {        

        }

        void insert(iterator at, Data data)

        {

        }

        void erase(iterator at)

        {

        }

        Data &operator[] (size_t index)

        {

            throw "잘못된 인덱스를 사용하였습니다.";

        }

        Data &operator[] (size_t index)const

        {

            throw "잘못된 인덱스를 사용하였습니다.";

        }

        iterator begin()

        {

            iterator iter;

            return iter;

        }

        iterator end()

        {           

            iterator iter;

            return iter;

        }

        const_iterator begin()const

        {

            iterator iter;

            return iter;

        }

 

 

        const_iterator end()const

        {           

            iterator iter;

            return iter;

        }

        size_t size()

        {

            return 0;

        }

        size_t capacity()

        {

            return 0;

        }

    };

}

 

//algorithm.h

#pragma once

namespace ehlib

{

    template <typename Iter,typename Fun>

    Iter find_if(Iter beg,Iter end,Fun fun)

    {

        return beg;

    }

}

 

4.1 vector 구현

이제 STL의 vector를 모델로 정의한 vector를 구현합시다.

#pragma once

namespace ehlib

{

    template<typename Data>

    class vector

    {

vector에는 자료를 보관하는 저장소를 동적으로 생성하여 자료를 관리합니다. 자료를 보관할 저장소의 위치 정보를 기억할 멤버 필드를 추가하세요.

        Data *base;

저장소의 크기를 기억할 멤버를 추가하세요.

        size_t bcapacity;

보관한 자료 개수를 기억할 멤버를 추가하세요.

        size_t bsize;

    public:

배열에 보관한 자료를 순차적으로 탐색할 수 있는 반복자를 구현합시다.

        class iterator

        {

현재 탐색할 위치를 기억할 멤버 필드를 추가하세요.

            Data *pos;

        public:

            iterator(Data *pos=0)

            {

입력 인자로 전달받은 위치를 멤버 필드에 설정하세요.

                this->pos = pos;

            }

            Data operator *()const

            {

반복자는 간접 연산을 통해 보관한 개체를 접근할 수 있습니다.

                 return *pos;

            }

            int operator-(const iterator &iter)const

            {

보관하거나 삭제할 때 상대적 거리로 저장소에 접근할 필요가 있어요. 이를 위해 -연산을 제공하세요.

                return pos - iter.pos;               

            }

            iterator &operator++()

            {

전위 증가 연산은 자신을 증가한 뒤에 자신을 반환하세요.

                pos++;

                return (*this);

            }

            const iterator operator++(int)

            {

후위 증가 연산은 자신을 복제한 후에 자신의 위치를 증가한 후에 복제한 값을 반환하세요.

                iterator re(*this);               

                pos++;

                return re;

            }

비교 연산은 가리키는 위치가 같은지 여부로 판변합니다.

            bool operator !=(const iterator &iter)const

            {

                return pos != iter.pos;

            }

            bool operator ==(const iterator &iter)const

            {

                return pos == iter.pos;

            }

        };

        typedef iterator const_iterator;

 

        vector()

        {

생성자에서는 저장소가 없는 상태이며 저장소의 크기와 보관 개수가 0인 상태로 설정하세요. 실제 vector는 여기서 구현하는 것보다 훨씬 복잡합니다.

            base = 0;

            bcapacity = bsize = 0;

        }

        ~vector()

        {

소멸자에서는 저장소가 유효하면 소멸하세요.

            if(base)

            {

                delete[] base;

            }

        }

        void resize(size_t nsize,Data data=0)

        {

resize 메서드는 첫 번째 인자 개수만큼 vector에 자료를 보관한 상태로 변경하는 메서드입니다. 이미 보관 중인 자료를 제외한 나머지는 두 번째 인자로 전달받은 값으로 설정합니다.

            if(nsize>bcapacity)

            {

먼저 nsize가 저장소의 크기보다 크면 저장소를 확장하세요. 이 부분은 별도의 메서드로 정의합시다.

                reserve(nsize);

            }

보관 개수가 nsize가 될 때까지 data를 순차보관하세요.

            while(bsize<nsize)

            {

                push_back(data);

            }

        }

        void reserve(size_t ncapacity)

        {

먼저 입력 인자로 전달받은 크기의 저장소를 생성하고 저장소의 크기를 변경하세요.

 

 

 

 

            Data *temp = new Data[ncapacity]; //새로운 저장소를 할당

            bcapacity = ncapacity; //새로운 저장소 용량 대입

            if(bsize) //보관한 자료가 있다면

            {

보관한 자료가 있으면 보관한 개수만큼 새로 생성한 버퍼에 복사하고 기존 저장소를 소멸하세요.

 

                for(size_t n=0; n<bsize; n++)

                {

                    temp[n] = base[n]; //기존 저장소에 보관한 자료를 새로운 저장소로 복사

                }

                delete[] base; //기존 저장소를 소멸

            }

base에 새로운 저장소를 대입하세요.

            base=temp; //base에 새로운 저장소를 대입

        }

 

        void push_back(Data data)

        {

순차 보관은 맨 뒤에 보관하는 것입니다. vector에서는 탐색하기 위해 시작 반복자와 끝 반복자를 구하는 메서드를 제공합니다. 여기서 시작 반복자는 저장소의 시작 위치이며 끝 반복자는 마지막 자료를 보관한 다음 위치입니다.

 

시작 반복자 위치부터 끝 반복자 위치가 나올 때까지 반복하여 탐색하게 작성하였으며 끝 반복자는 탈출 조건을 위해 만든 것입니다. 따라서 끝 반복자는 실제 마지막 자료를 보관한 위치가 아니라 그 다음 위치입니다.

 

맨 뒤에 보관하는 것은 end() 앞에 data를 보관하면 되겠죠.

            insert(end(),data);

        }

        void insert(iterator at, Data data)

        {

꽉 차면 저장소의 크기를 늘려야 합니다. 반복자는 이전 저장소에 자료를 저장한 위치여서 저장소를 확장하면 기존에 위치 정보는 아무런 가치가 없습니다. 따라서 입력 인자로 전달받은 반복자의 위치가 저장소와의 상대적 거리를 계산하세요.

            size_t index = at-base;

            if(bsize == bcapacity)

            {

꽉 차면 저장소의 크기를 늘립니다. 여기에서는 확장할 때 10개의 공간씩 늘리는 것으로 할게요.

                reserve(bcapacity+10);

            }

보관할 위치 뒤에 것을 한 칸씩 뒤로 이동해야 합니다. 뒤쪽부터 이동해야 값의 손실을 막을 수 있어요.

            for(size_t pos=bsize; pos>index; pos--)

            {

                base[pos] = base[pos-1];

            }

저장소의 index 위치에 자료를 보관하고 보관 개수를 1 증가합니다.

            base[index] = data;

            bsize++;

        }

        void erase(iterator at)

        {

특정 위치에 자료를 지우는 기능입니다. 여기에서 할 일은 보관한 자료의 개수를 1 줄이는 것 뿐만 아니라 지울 위치 뒤에 있는 자료들을 한 칸씩 앞으로 당기는 작업을 수행합니다.

 

먼저 보관한 자료를 줄이세요. 그리고 입력 인자로 전달받은 반복자의 상대적 위치를 구하세요. 그리고 인덱스가 보관한 자료 개수보다 작으면 인덱스 뒤에 자료를 인덱스 위치에 복사하는 것을 반복하세요.

 

보관한 자료 개수를 1 감소시키세요.

            bsize--;

반복자의 위치가 저장소에서 상대적 거리가 얼마인지 계산한 후에 뒤쪽 자료를 한 칸씩 앞으로 당기세요.

            for(size_t index = at-base; index<bsize; index++)

            {

                base[index] =base[index+1];

            }

        }

인덱스 연산을 구현합시다. 인덱스 연산은 대입 연산자 왼쪽에 올 수 있어야 하기 때문에 값을 반환하지 않고 보관한 자료 자체를 반환하기 위해 참조 형식으로 반환하게 정의하였습니다.

        Data &operator[] (size_t index)

        {

인덱스가 유효하면 인덱스 위치에 보관한 자료를 반환하세요.

            if((index>=0)&&(index<bsize))

            {

                return base[index];

            }

인덱스가 유효하지 않으면 예외를 던지세요. 여기에서 0을 반환하는 것은 컴파일 오류입니다. 반환 형식이 참조 형식임을 주의하세요.

            throw "잘못된 인덱스를 사용하였습니다.";

        }

상수화 메서드에서 접근할 수 있는 인덱스 연산자도 같은 원리로 구현하세요.

        Data &operator[] (size_t index)const

        {

            if((index>=0)&&(index<bsize))

            {

                return base[index];

            }

            throw "잘못된 인덱스를 사용하였습니다.";

        }

 

탐색에 사용할 시작 반복자를 구하는 begin에서는 저장소의 위치를 갖는 반복자를 반환합니다.

        iterator begin()

        {

            iterator iter(base);

            return iter;

        }

 

탐색에 사용할 끝 반복자를 구하는 end는 base+bsize를 갖는 반복자를 반환합니다. 끝 반복자는 탐색 반복문에서 탈출 조건으로 사용할 것이므로 맨 뒤에 보관한 다음 위치를 반환하는 것입니다.

        iterator end()

        {           

            iterator iter(base+bsize);

            return iter;

        }

상수화 메서드에서 사용하기 위한 메서드도 구현은 같습니다.

        const_iterator begin()const

        {

            iterator iter(base);

            return iter;

        }

        const_iterator end()const

        {           

            iterator iter(base+bsize);

            return iter;

        }

보관한 원소 개수를 구하는 기능을 구현하세요.

        size_t size()

        {

            return bsize;

        }

저장소의 크기를 구하는 기능을 구현하세요.

        size_t capacity()

        {

            return bcapacity;

        }

    };

}

 

이번에는 find_if 알고리즘을 구현합시다.

namespace ehlib

{

    template <typename Iter,typename Fun>

    Iter find_if(Iter beg,Iter end,Fun fun)

    {

find_if는 탐색 구간을 순차적으로 이동하면서 원하는 조건을 만족하는 위치를 찾는 알고리즘입니다.

        for(  ;beg != end ; ++beg)

        {

세 번째 전달할 함수(혹은 함수 개체)에 탐색 구간에 있는 자료를 적용했을 때 참인지 판별합니다. 반복자는 간접 연산으로 보관한 자료를 구할 수 있으니 다음처럼 표현할 수 있어요.

            if(fun(*beg))

            {

                break;

            }

        }

        return beg;

    } 

}

이제 3장에서 STL에서 제공하는 vector를 사용했던 프로그램에서 여기서 만든 vector와 find_if를 사용하게 헤더 파일 포함문과 using 문을 변경하여 테스트 해 보세요.

 

이처럼 내부를 파헤치는 작업을 internal이라 부릅니다. 보통 internal 작업은 만드는 것이 목적이 아니라 내부를 이해하기 위한 것입니다. 지금처럼 비슷하게 구현할 수도 있지 논리적으로 분석할 수도 있겠죠.

 

4.2 vector와 find_if 코드

다음은 앞에서 작성한 vector와 find_if 알고리즘을 구현한 코드입니다.

 

//vector.h

#pragma once

namespace ehlib

{

 

    template<typename Data>

    class vector

    {       

        Data *base;

        size_t bcapacity;

        size_t bsize;

 

    public:

        class iterator

        {   

            Data *pos;

 

        public:

            iterator(Data *pos=0)

            {

                this->pos = pos;

            }

 

            Data operator *()const

            {

                 return *pos;

            }

 

            int operator-(const iterator &iter)const

            {

                return pos - iter.pos;               

            }

 

            iterator &operator++()

            {                  

                pos++;

                return (*this);

            }

 

 

            const iterator operator++(int)

            {

                iterator re(*this);               

                pos++;

                return re;

            }

 

            bool operator !=(const iterator &iter)const

            {

                return pos != iter.pos;

            }

            bool operator ==(const iterator &iter)const

            {

                return pos == iter.pos;

            }

        };

        typedef iterator const_iterator;

 

        vector()

        {

            base = 0;

            bcapacity = bsize = 0;

        }

 

        ~vector()

        {

            if(base)

            {

                delete[] base;

            }

        }

 

        void resize(size_t nsize,Data data=0)

        {

            if(nsize>bcapacity)

            {

                reserve(nsize);

            }

            while(bsize<nsize)

            {

                push_back(data);

            }

        }

 

        void reserve(size_t ncapacity)

        {

            Data *temp = new Data[ncapacity]; //새로운 저장소를 할당

            bcapacity = ncapacity; //새로운 저장소 용량 대입

            if(bsize) //보관한 자료가 있다면

            {

                for(size_t n=0; n<bsize; n++)

                {

                    temp[n] = base[n]; //기존 저장소에 보관한 자료를 새로운 저장소로 복사

                }

                delete[] base; //기존 저장소를 소멸

            }

            base=temp; //base에 새로운 저장소를 대입

        }

 

        void push_back(Data data)

        {

            insert(end(),data);

        }

        void insert(iterator at, Data data)

        {

            size_t index = at-base;

            if(bsize == bcapacity)

            {

                reserve(bcapacity+10);

            }

            for(size_t pos=bsize; pos>index; pos--)

            {

                base[pos] = base[pos-1];

            }

            base[index] = data;

            bsize++;

        }       

     

        void erase(iterator at)

        {

            bsize--;

            for(size_t index = at-base; index<bsize; index++)

            {

                base[index] =base[index+1];

            }

        }

        Data &operator[] (size_t index)

        {

            if((index>=0)&&(index<bsize))

            {

                return base[index];

            }

            throw "잘못된 인덱스를 사용하였습니다.";

        }

 

        Data &operator[] (size_t index)const

        {

            if((index>=0)&&(index<bsize))

            {

                return base[index];

            }

            throw "잘못된 인덱스를 사용하였습니다.";

        }

 

        iterator begin()

        {

            iterator iter(base);

            return iter;

        }

 

        iterator end()

        {           

            iterator iter(base+bsize);

            return iter;

        }

 

        const_iterator begin()const

        {

            iterator iter(base);

            return iter;

        }

 

        const_iterator end()const

        {           

            iterator iter(base+bsize);

            return iter;

        }

 

 

        size_t size()

        {

            return bsize;

        }

 

        size_t capacity()

        {

            return bcapacity;

        }

    };

}

 

//algorithm.h

#pragma once

namespace ehlib

{

    template <typename Iter,typename Fun>

    Iter find_if(Iter beg,Iter end,Fun fun)

    {    

        for(  ;beg != end ; ++beg)

        {

            if(fun(*beg))

            {

                break;

            }

        }

        return beg;

    } 

}