[자료구조와 STL] 10. vector 만들기

2. 4 vector 만들기

 

 먼저, 앞에서 만든 프로젝트에 EHVector.h를 추가하여 STL에서 제공되는 vector와 비슷하게 직접 만들어 보기로 합시다. 이를 만드는 목적은 vector 내부를 좀 더 명확하게 이해하기 위해서입니다. EHVecotr.h에는 템플릿 클래스인 vector를 정의할 것입니다. 여기서는 EHLIB 이름 공간 내에 정의할게요.

 

#pragma once

namespace EHLIB

{

    template<typename T>

    class vector{    };

};

 

 이제 StuManager.h에 vector 대신 "EHVector.h"를 포함하는 구문으로 변경하고 std 이름 공간에 있는 vector 대신 EHLIB 이름 공간에 있는 vector를 사용하도록 바꾸세요.

 

#include "EHVector.h"

using EHLIB::vector;

typedef vector<Stu *> StuCollection;

 

 참고로 앞으로 코드를 수정 후에는 빌드 메뉴에서 정리를 선택한 후에 빌드하세요.

 

 vector에는 템플릿 인자 형식 요소들을 보관하는 저장소가 있어야 할 것입니다. 그리고 이것 외에 저장소의 크기(보관할 수 있는 요소의 개수)를 보관하는 멤버와 보관된 요소 개수를 저장하는 멤버가 있습니다. 저장소를 base라 하고 보관된 요소 개수를 bsize, 저장소의 크기를 bcapacity라 할게요.

 

template<typename T>

class vector

{

    T *base; //요소들을 보관할 저장소의 시작 위치

    size_t bsize; //보관된 요소 개수

    size_t bcapacity; //저장소의 크기

};

 

 vector를 생성할 때에는 vector<int> vi(10);나 vector<int> vi;와 같이 초기 요소 개수를 입력 인자로 전달하거나 전달하지 않을 수 있을 것입니다. 여기에서는 디폴트 매개 변수를 이용하도록 할게요. 참고로, 요소 개수 외에도 초기에 보관할 요소 값도 입력 인자로 전달할 수 있는데 이것 또한 디폴트 매개 변수를 이용할게요.

 

vector(size_t init_cnt=0,T t=0);

 

 생성자 메서드에서는 초기에 base나 bsize, bacapactiy를 0으로 설정을 하겠죠. 첫 번째 입력 인자로 전달 인자로 저장소 크기를 지정(reserve)하고 두 번째 입력 인자로 각 요소의 값을 보관(push_backs)해야 할 것입니다.

 

base = 0;

bsize = 0;

bcapacity = 0;

reserve(init_cnt); //저장소의 용량을 init_cnt로 변경,

pushbacks(init_cnt,t); //init_cnt 개수만큼 t를 차례대로 보관

 

 reserve 메서드에서는 동적으로 저장소를 할당하는 작업을 수행하면 될 것입니다. 만약, 기존에 저장소가 존재한다면 기존에 보관되었던 것을 새로 할당한 저장소에 복사하는 작업과 기존에 할당된 저장소를 해제하는 구문이 필요하겠죠.

 

void reserve(size_t ncapacity)

{

    T *temp = new T[ncapacity]; //새로운 크기의 저장소를 생성하여 temp에 대입

    if(bsize) //보관된 것이 있다면

    {

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

        {

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

        }

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

    }

    base=temp; //새로운 저장소의 위치를 base에 대임

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

}

 

 resize 메서드는 입력 인자로 전달된 개수만큼을 보관하는 것으로 갱신하는 작업을 수행합니다. 만약, 현재 5개가 보관된 상태에서 nsize가 7, t가 0일 때 0으로 2개를 추가 보관하는 것입니다. 그리고 현재 1,2,3,4,5 의 값으로 5개가 보관되어 있을 때 nsize가 3이 오면 앞에 보관된 1,2,3 만 보관한 것으로 남겨두게 합니다.

 

 이에 resize 메서드에서는 입력 인자로 전달된 nsize와 현재 보관된 요소 개수인 bsize를 비교를 하여 nsize가 bsize보다 크다면 뒤에 추가로 보관합니다. 만약, bsize가 nsize보다 크다면 nsize가 bsize와 같을 때까지 뒤에 있는 것들을 제거하면 되겠죠.

 

void resize(size_t nsize,T t=0)

{

    if( nsize > bsize) //새로운 요소 개수가 보관된 요소 개수보다 크다면

    {

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

        {

            push_back(t); //t를 뒤에 보관

        }

    }

    else//새로운 요소 개수가 보관된 요소 개수보다 크지 않다면

    {

        for(size_t n=nsize; n<bsize ; )

        {

            erase(base+n); //줄여야 할 뒤의 요소들을 삭제

        }

    }

}

 

 push_back 메서드에서는 보관된 맨 마지막 요소의 다음 위치에 입력 인자로 전달된 요소를 보관면 될 것입니다. 특정 위치에 원하는 요소를 보관하는 메서드도 필요할 수 있으니 insert 메서드를 정의하도록 할게요.

 

void push_back(T t)

{

    insert(end(),t); //마지막 보관한 요소 뒤에 보관, end()앞에 t를 보관

}

 

 insert 메서드에서는 보관할 저장소가 꽉 찼다면 저장소를 늘려주는 작업을 선행해야 할 것입니다. 여기에서는 기존 저장소의 크기에서 10개의 요소를 추가로 저장할 수 있게 갱신하겠습니다. STL에 제공되는 vector에서는 보관된 요소 개수에 따라 갱신되는 정도를 다르게 하고 있지만, 여기에서는 고려하지 않겠습니다. 그리고 insert 메서드에서는 보관할 위치 뒤에 보관된 요소들을 한 칸씩 뒤로 이동 후에 보관해야 합니다.

 

void insert(iterator at, T t)

{

    size_t index = at - base; //입력받은 위치를 저장소의 인덱스로 변환

    if(bsize == bcapacity) //꽉 찼다면

    {

        reserve(bcapacity+10); //저장소의 용량을 늘려줌

    }

   

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

    {

        base[n] = base[n-1]; //보관할 위치 뒤에 있는 요소들을 한 칸씩 뒤로 이동

    }

    base[index] = t;

    bsize++;

}

 

 erase 메서드는 특정 위치에 보관된 요소를 지우는 작업을 수행합니다. 이를 위해서 특정 위치 뒤에 있는 요소들을 하나씩 앞으로 당기는 작업이 필요하겠죠.

 

void erase(iterator at)

{

    size_t index = at - base; //입력받은 위치를 저장소의 인덱스로 변환

   

    for(size_t n = index+1; n < bsize; n++)

    {

        base[n-1] = base[n]; //삭제할 위치 뒤에 요소들을 하나씩 앞으로 이동

    }

    bsize--;

}

 

 그리고 vector에 보관된 요소와 보관소 크기를 반환하는 size 메서드와 capacity 메서드를 작성합시다.

 

size_t size()

{

    return bsize;

}

size_t capacity()

{

    return bcapacity;

}

 

 사용자가 원하는 위치에 요소를 보관하기 위해서는 저장소의 원하는 위치를 찾는 방법을 제공해 주어야 합니다. STL에서는 컨테이너 종류에 상관없이 보관된 요소들을 순회하여 원하는 작업을 수행할 수 있도록 각 컨테이너 내부에 iterator를 정의하고 있습니다. 그리고 각 컨테이너에서는 맨 앞과 맨 뒤에 해당하는 iterator를 참조할 수 있게 begin, end 메서드를 제공하고 있습니다. 참고로, end는 마지막 요소가 보관된 위치가 아니라 다음 위치이므로 차례대로 보관하면 이번에 보관할 위치에 해당합니다.

 

 vector에서의 iterator는 요소가 보관된 위치를 멤버로 알고 있어야 할 것입니다. 사용자로서는 보관된 요소를 알 필요가 있고 vector에서는 보관된 위치를 알아야 insert 메서드나 erase 메서드에서 이를 사용할 수 있을 것입니다. 관점에 따라 iterator 형식은 보관된 요소의 위치 정보로 생각할 수 있습니다.

 

class iterator

{

    T *pos; //요소가 보관된 위치

};

 

 iterator의 생성자는 보관된 요소의 위치 정보를 입력 인자로 받게 정의할게요.

 

iterator(T *pos=0)

{

    this->pos = pos;

}

 

 vector를 사용하는 개발자는 iterator 형식 변수에 간접 연산자(*)를 통해 보관한 요소를 얻어올 수 있습니다. 이를 위해 간접 연산자를 중복 정의할게요.

 

T operator *()

{

    return *pos; //보관된 요소를 반환

}

 

 그리고 vector 내부에서는 보관된 위치를 알아야 하는데 상대적인 위치를 알 수 있어야 합니다. 이를 위해 뺄셈 연산자를 중복 정의할게요. 그리고 다음 요소의 위치 정보로 변경하기 위해 ++연산자를 중복 정의하겠습니다.

 

int operator-(const iterator &iter)

{

         return pos -iter.pos;

}

 

iterator &operator++()

{

    pos++;

    return (*this);

}

 

const iterator operator++(int)

{

    iterator re(*this);

    pos++;

    return re;

}

 

 iterator 형식을 정의했으니 vector의 begin 메서드와 end 메서드를 제공합시다. begin 메서드에서는 저장소의 시작 위치 base를 반환하면 되겠죠. end에서는 base+bsize를 반환하면 마지막 보관된 요소 다음 위치를 반환할 수 있겠네요.

 

iterator begin(){    return base;    }

iterator end(){    return base+bsize;    }

 이제 [] 연산자를 중복 정의해 봅시다. [] 연산자는 참조하고자 하는 인덱스를 전달받아 해당 인덱스에 있는 요소에 대한 참조를 반환하면 됩니다. 참조를 반환하는 이유는 []연산자의 결과가 대입(=) 연산자의 좌항에 올 수도 있기 때문입니다. []연산에 입력된 인덱스가 잘못된 값을 경우에는 예외를 발생하면 되겠죠.

 

T &operator[] (size_t index)

{

    if(index<bsize) //유효한 인덱스일 때

    {

        return base[index];

    }

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

}