9-3. STL - Vector 구현하기 (실습)

1. vector 구현하기

vector를 클래스로 구현하는 연습을 한다.

 

(1) Vector 클래스 구성하기

#include <iostream>
#include <vector>
using namespace std;

template<typename T>
class Vector
{
public:
    Vector() : _data(nullptr), _size(0), _capacity(0)
    {

    }

    ~Vector()
    {
        if (_data) // 데이터가 있으면 true 반환
            delete[] _data; // 객체 삭제, 배열의 형태이므로 delete[]
    }

    int size() {return _size;} // size 값을 반환하는 명령어
    int capacity() {return _capacity;} // capacity 값을 반환하는 명령어

private:
    T* _data;	// 포인터
    int _size;
    int _capacity;
};

기본 생성자에서 멤버 변수를 초기화해준다.

소멸 생성자에서 데이터 영역을 지워주도록 한다. 이 때 배열이므로 문법에 주의하여야 한다.

 

(2) push_back 구현

동적 배열의 끝에 값을 추가하는 push_back 함수를 구현한다.

    void push_back(cosnt T& val)
    {
        if (_size == _capacity) // 메모리 증설 조건
        {
            int newCapacity = static_cast<int>(_capacity * 1.5); // 정수에 실수를 곱하면 짤림
            if (newCapacity == _capacity)
                newCapacity++;  // 1에 1.5를 곱해도 1이므로, 같으면 1을 늘리게 설정
        
            reserve(newCapacity) // 캐퍼시티 증설 완료
        }
    }

위 코드는 사이즈(정수)와 커패시티(정수)를 비교하여 같으면 새로운 커패시티를 이전 커패시티의 1.5배로 증설하게 만든다. 이 때 정수 1에 1.5를 곱해도 1이 되므로 2가 되게 하기위하여 새로운 커패시티에 1을 더해주도록 작성한다.

 

다음으로 배열의 끝에 원소를 추가하도록 코드를 작성한다.

    void push_back(const T& val)
    {
        if (_size == _capacity) // 메모리 증설
        {
            int newCapacity = static_cast<int>(_capacity * 1.5); // 정수에 실수를 곱하면 짤림
            if (newCapacity == _capacity)
                newCapacity++;  // 1에 1.5를 곱해도 1이므로, 같으면 1을 늘리게 설정
        
            reserve(newCapacity); // 캐퍼시티 증설 완료
        }
        _data[_size] = val; // 사이즈 만큼의 원소로 이동 후에 값을 집어넣음
        _size++; // 사이즈를 증가시킴(값이 추가되었기 때문에)
    }

사이즈 만큼 접근해서 끝에 값을 집어넣는다.

 

(3) reserve 구현

동적 배열의 capacity를 늘리는 reserve 함수를 구현한다.

    void reserve(int capacity)
    {
        _capacity = capacity;

        // 동적 할당으로 새로운 메모리 공간 할당받음
        T* newData = new T[_capacity];

        // 기존 데이터 복사
        for (int i = 0; i < _size; i++)
            newData[i] = _data[i];

        // 이전 데이터 초기화
        if (_data)
            delete[] _data;

        // 새로운 공간에 데이터를 넣음
        _data = newData;

    }

기존의 capacity의 작동 방법 처럼 구현한다.

(사이즈가 커패시티만큼 커지면 1.5배 확장하여 메모리를 증설하고, 증설한 메모리로 모든 값을 복사/이동 시킴)

 

(4) 배열 임의 접근을 위한 배열 인덱스 연산자 오버로딩

V.[1] = 1 같은 코드를 작동할 수 있도록 배열 인덱스 연산자인 '[ ]'를 오버로딩하도록 한다.

   T& operator [] (const int pos) { return _data[pos]; } // 실제 값을 변경하기 때문에 참조타입을 사용

 

2. 반복자(Iterator) 구현

반복자를 증감해야 함.

역 참조를 통해 데이터에 접근할 수 있게 해야함.

template<typename T>
class Iterator
{
public:
    Iterator() : _ptr(nullptr)
    {

    }

    Iterator(T* ptr) : _ptr(ptr)
    {

    }

	~Iterator() {};

public:
    T* _ptr; // 데이터의 포인터를 가리킴.
    // Myproxy 구현은 생략함.
};

 

(1) 증감 연산자 오버로딩

    // it++, ++it, 각종 증감 연산자 오버로딩
    Iterator& operator++() // 전위형 -> 참조 형태로 만듬, ++(++it)가 가능하도록
    {
        _ptr++;
        return *this; // 자기 자신의 주소를 리턴
    }

    Iterator operator++(int) // 후위형
    {
        Iterator temp == *this;
        _ptr++;
        return temp;
    }

    Iterator& operator--() // 전위형 -> 참조 형태로 만듬, ++(++it)가 가능하도록
    {
        _ptr--;
        return *this; // 자기 자신의 주소를 리턴
    }

    Iterator operator--(int) // 후위형
    {
        Iterator temp == *this;
        _ptr--;
        return temp;
    }

 

(2) 비교 연산자 오버로딩

    // 비교 연산자 오버로딩
    bool operator==(const Iterator& right)
    {
        return _ptr == right._ptr; // 기존의 _ptr이 우변의 _ptr과 같은지
    }

    bool operator!=(const Iterator& right)
    {
        return _ptr != right._ptr; // 기존의 _ptr이 우변의 _ptr과 다른지
    }

또는 != 연산자를 만들 때 지금 포인터가 우변과 같은지 판별한 후 한번 뒤집어 줄 수 있다.

return !(*this == right)

 

(3) 포인터 연산자 ' * ' 오버로딩

    T& operator*()
    {
        return *_ptr; // *를 붙이면 실제 데이터를 건내주게 함
    }

 

3. 반복자를 사용하는 vector의 문법들 구현

다시 Vector 클래스로 돌아가서 작성한다.

public:
    typedef Iterator<T> iterator;

    iterator begin() { return iterator(&_data[0]);}
    iterator end() { return begin() + _size();}

한편, 반복자에서 덧셈 연산에 대하여 오버로딩 하지 않았으므로 그 부분을 구현해준다.

 

(1) 반복자의 덧셈, 뺄셈 연산자 오버로딩

    Iterator operator+(const int count) // count 만큼 이동
    {
        Iterator temp = *this;
        temp._ptr += count;
        return temp;
    }

    Iterator operator-(const int count) // count 만큼 이동
    {
        Iterator temp = *this;
        temp._ptr -= count;
        return temp;
    }

 

(2) clear 문법 구현

    void clear() { _size = 0; }

캐퍼시터는 유지하고 사이즈만 초기화한다.