std::vector, Iterator 직접 구현하며 이해하기

들어가며

 C++ 표준 라이브러리 (STL) std::vector는 순차적인 자료(배열)를 저장하는 템플릿 클래스입니다. 

처음 프로그래밍을 배우던 시절 수년간 동적 메모리 할당(Dynamic Allocation) 을 오직 new, delete 구문에만 의존해 왔습니다. (STL이 뭔지 몰랐습니다.)

그러던 어느날 std::vector를 처음 사용해 본 후 그 편리함과 왜 이런 존재를 나는 몰랐지라는 허무함이 공존했던 기억이 납니다.

하지만 new, delete를 다년간 사용하며 배웠던 포인터, 메모리에 대한 깊은 이해는 현재까지도 프로그래밍 지식의 좋은 밑바탕이 되었음을 스스로 느낍니다.

편리함의 이면

std::vector를 접한 후 대부분의 동적 배열, 동적메모리 할당은 제 코드에서 사라지게 되었고, 남이 만든 클래스(물론 표준이지만)의 사용법을 배우는 것에만 집착하게 됩니다.

"이게 어떻게 만들어져 있지" 보다 "어떻게 이것을 사용하지" 라는 생각만 남아 깊은 공부에 별 도움이 되지 않는 도구의 사용법에만 관심이 있었습니다. 

대학시절의 자신에게 돌아간다면, 그건 (사용법은) 별로 중요하지 않다고 말해주고 싶군요.

오히려 "비슷하게 직접 한번 만들어 보는 것은 어때" 라고 권해주고 싶습니다.

또한, STL은 C++의 강력한 표준 라이브러리이지만 언제나 사용가능한 것은 아닙니다.

(아두이노 IDE는 C++언어를 지원하지만 STL은 사용이 불가, 작은 메모리환경)

 

std::vector

그럼 직접 나만의 벡터를 만들어 보겠습니다.

앞으로 소개할 예제는 vector Class, Nested Class로 iterator Class 구현까지 포함한 내용입니다.

물론 표준 라이브러리만큼 훌륭하진 않지만 좋은 공부가 될 것입니다.

왜냐하면 벡터 클래스를 직접 만드는 과정에서 C++의 템플릿, 포인터, 중첩클래스, 연산자 오버로딩, 게다가 Modern C++ (C++11, 14, 17) 에 새롭게 정립된 LValue, RValue 개념 등을 모두 공부할 수 있는 기회이기 때문입니다.

그전에 std::vector가 동작하는 방식을 한번 살펴보겠습니다.

표준 라이브러리 std::vector는 아래와 같이 사용합니다.

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v;
    v.push_back(0);
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);    

    std::vector<int>::iterator itr;

    for (itr=v.begin();itr!=v.end();++itr)
        std::cout << *itr << '\n';
    
    std::cout << "size: " << v.size() << '\n';
    std::cout << "capa: " << v.capacity() << '\n';    
}

정수형 타입을 담는 벡터 템플릿 클래스를 선언하고, push_back() 메서드를 통해 값을 배열에 집어 넣습니다.

이어서 벡터 컨테이너의 요소를 순회, 접근 가능한 반복자 (Iterator)를 선언한 후 역참조(*) 연산자를 통해 벡터 컨테이너 요소들을 순차적으로 출력하는 모습입니다.

또한 size() 함수와 capacity()함수를 따로 가진다는 것은 벡터클래스가 저장된 요소의 갯수만큼만 배열을 할당하는 것이 아니라는 사실도 추측해 볼 수 있습니다.

[std::vector의 기본 구조]

코드의 수행 결과 입니다.

똑똑하게도 필요한 만큼만 메모리를 할당한 모습입니다.

벡터의 용량 (capacity)은 늘 크기 (size) 보다 크거나 같아야 합니다.

[코드 실행 결과]

 

Custom vector 만들기

나만의 커스텀 벡터 클래스를 만들기 위해 템플릿 클래스를 만들고, 반복자 클래스를 중첩 (Nested) 클래스로 선언합니다.

대략 아래와 같은 모습입니다.

기초 구현

namespace ocs
{
    template<typename T>
    class vector
    {
    public:
        // nested class
        class iterator
        {        
        };        
    };
} // end of namesapce

• 클래스 이름 충돌을 피하기 위해 ocs 네임스페이스 생성
  

• ocs::vector 클래스 선언
  

• ocs::vector<T>::iterator 중첩 (nested) 클래스 선언

ocs는 학원명 약자(Ocean Coding School)입니다. ^^

 

이제 벡터 및 반복자 객체는 다음과 같이 선언하고 사용합니다.

반복자의 경우, 범위 지정 연산자(::)를 통해 접근 가능합니다.

ocs::vector<int> v;

ocs::vector<int>::iterator itr; 

간략화를 위해 const_iterator는 구현하지 않았습니다.

기본 구현

그럼 std::vector와 유사하게 멤버 변수와 함수까지 확장해 보겠습니다. 

#pragma once
#include <memory>
#include <utility>

namespace ocs
{
    template<typename T>
    class vector
    {
    public:
        // nested class
        class iterator
        {
        public:
            iterator(T* p = nullptr, size_t idx=0);
            ~iterator();
            iterator& operator++();            
            iterator operator++(int);
            iterator& operator--();
            iterator operator--(int);
            iterator operator+(size_t n);            
            iterator operator-(size_t n);            
            bool operator==(const iterator& it);
            bool operator!=(const iterator& it);
            T& operator*();
            const T* operator->();
        private:        
            friend class vector;
            T* pv;
            size_t pos;
        };
        
        // constructors
        explicit vector(size_t c = 1);
        vector(const vector<T>& rhs);
        vector(vector<T>&& rhs);
        vector(const std::initializer_list<T>& lst);
        ~vector();        

        // operator
        vector<T>& operator=(const vector& rhs);        
        vector<T>& operator=(vector&& rhs);
        T& operator[](size_t pos);        

    private:
        T* p;
        size_t _size, _capacity;

    public:
        inline T& front();
        inline const T& front();
        inline T& back();
        inline const T& back();

        inline iterator begin();
        inline iterator end();
        inline iterator erase(const iterator& it);
        inline iterator erase(const iterator& sit, const iterator& eit);

        inline void push_back(const T& val);
        inline void push_back(const T&& val);
        inline void pop_back();

        inline iterator insert(const iterator& it, const T& val);                
        inline void resize(size_t n, const T& val=T());        
        inline void reserve(size_t n);
        
        inline void swap(vector<T>& rhs);        

        inline bool empty();
        inline void clear();
        inline size_t size();
        inline size_t capacity();
    };
} // end of namesapce

ocs::vector<T>::Iterator Class의 메서드(함수) 및 필드(변수)는 아래와 같습니다.

• 생성자, 소멸자

• 증감 연산자 (prefix, postfix)

• 더하기, 빼기 연산자 (+, -)

• 비교 연산자 (==, !=)

• 포인터 연산자 (*, ->)

• 멤버 변수 (T* pv, size_t pos)

 

다음은 ocs::vector<T> Class의 메서드, 필드 입니다.

• 생성자, 소멸자 (Copy, Move, Uniform Initialization)
  

• 대입 연산자 (Copy, Move Assignment)
  

• 첨자 연산자 (Subscript [] )
  

• 추가, 삽입, 삭제 등 함수 (push_back, insert, erase...)

• 멤버 변수 (T* p, size_t size, capacity)
  

 

VS의 클래스 다이어그램을 이용해 UML로 시각화한 모습입니다.

[ocs::vector 클래스 다이어그램]

이제 어느정도 형태가 갖춰진 모습입니다.

세부적인 동작은 이어지는 상세구현에서 설명하겠습니다.

 

상세구현

빈 vector.h 파일을 프로젝트에 추가하고 아래와 같이 코드를 추가합니다.

템플릿 클래스이므로 구현(Implementation)도 *.h에 같이 작성하는게 편리하겠죠.

#pragma once
#include <memory>
#include <utility>

namespace ocs
{
    template<typename T>
    class vector
    {
    public:
        // nested class
        class iterator
        {
        public:
            iterator(T* p = nullptr, size_t idx=0) : pv(p), pos(idx) {}
            ~iterator() {}
            iterator& operator++()
            {                
                ++pos;                
                return *this;
            }
            iterator operator++(int)
            {
                auto temp = *this;
                this->operator++();
                return temp;
            }
            iterator& operator--()
            {                
                --pos;            
                return *this;
            }
            iterator operator--(int)
            {
                auto temp = *this;
                this->operator--();
                return temp;
            }
            iterator operator+(size_t n)
            {
                return iterator(&pv[pos], pos+n);
            }
            iterator operator-(size_t n)
            {
                return iterator(&pv[pos], pos - n);
            }
            bool operator==(const iterator& it) const noexcept
            {
                return &pv[pos] == &it.pv[pos];
            }
            bool operator!=(const iterator& it) const noexcept
            {
                return &pv[pos] != &it.pv[it.pos];
            }
            T& operator*() const
            {
                return pv[pos];
            }
            const T* operator->() const
            {
                return &pv[pos];
            }

        private:        
            friend class vector;
            T* pv;
            size_t pos;
        };
        
        // constructors
        explicit vector(size_t c = 1) : p(new T[c]{}), _size(0), _capacity(c) {}
        vector(const vector<T>& rhs) : p(new T[rhs._size]), _size(rhs._size), _capacity(rhs._capacity)
        {
            for (size_t i = 0; i < _size; ++i)
                p[i] = rhs.p[i];
        }
        vector(vector<T>&& rhs) : p(std::move(rhs.p)), _size(std::move(rhs._size)), _capacity(std::move(rhs._capacity))
        {
            rhs.p = nullptr;
            rhs._size = 0;
            rhs._capacity = 0;
        }
        vector(const std::initializer_list<T>& lst) : p(new T[lst.size()]{}), _size(lst.size()), _capacity(lst.size())
        {
            memcpy(p, lst.begin(), sizeof(T)*lst.size());
        }
        ~vector()
        {
            if (p)
            {
                delete[] p;
                p = nullptr;
            }
        }

        // operator
        vector<T>& operator=(const vector& rhs)
        {
            if (this != &rhs)
            {
                vector temp(rhs);
                temp.swap(*this);

                /*if (_capacity != rhs._capacity)
                {
                    delete[] p;                    
                    _capacity = rhs._capacity;
                    p = new T[_capacity];
                }                
                _size = rhs._size;
                for (size_t i = 0; i < _size; ++i)
                    p[i] = rhs.p[i];*/
            }
            return *this;
        }
        vector<T>& operator=(vector&& rhs)
        {
            rhs.swap(*this);
            /*std::swap(p, rhs.p);
            std::swap(_size, rhs._size);
            std::swap(_capacity, rhs._capacity);*/
            return *this;
        }
        
        T& operator[](size_t pos)
        {
            return p[pos];
        }
        

    private:
        T* p;
        size_t _size, _capacity;

    public:
        inline T& front() { return p[0]; }
        inline const T& front() const { return p[0]; }
        inline T& back() { return p[_size-1]; }
        inline const T& back() const { return p[_size-1]; }

        inline iterator begin() { return iterator(p); }
        inline iterator end() { return iterator(p, _size); }
        inline iterator erase(const iterator& it)
        {
            --_size;
            memcpy(&p[it.pos], &p[it.pos+1], sizeof(T)*(_size - it.pos));
            return iterator(p);
        }
        inline iterator erase(const iterator& sit, const iterator& eit)
        {
            size_t sz = eit.pos - sit.pos;
            memcpy(&p[sit.pos], &p[eit.pos], sizeof(T)*(_size - eit.pos));
            _size -= sz;
            return iterator(p);
        }

        inline void push_back(const T& val)
        {
            if (_size >= _capacity)
            {
                _capacity *= 2;
                T* temp = new T[_capacity];
                memcpy(temp, p, sizeof(T)*_size);
                delete[] p;
                p = temp;
            }
            p[_size++] = val;
        }
        inline void push_back(const T&& val)
        {
            if (_size >= _capacity)
            {
                _capacity *= 2;
                T* temp = new T[_capacity];
                memcpy(temp, p, sizeof(T)*_size);
                delete[] p;
                p = temp;
            }
            p[_size++] = std::move(val);
        }
        inline void pop_back() { _size = size > 0 ? -1 : 0; }

        inline iterator insert(const iterator& it, const T& val)
        {            
            if (_capacity > _size)
            {
                memcpy(&p[it.pos + 1], &p[it.pos], sizeof(T)*(_size - it.pos));
                p[it.pos] = val;
                ++_size;
            }
            else
            {
                T* temp = new T[_size + 1];
                memcpy(temp, p, sizeof(T)*(_size));
                memcpy(&temp[it.pos + 1], &p[it.pos], sizeof(T)*(_size - it.pos));
                temp[it.pos] = val;

                delete[] p;
                p = temp;
                ++_size;
                _capacity = _size;
            }
            return iterator(p, it.pos);
        }
                
        inline void resize(size_t n, const T& val=T())
        {
            if (n != _size)
            {
                T* temp = new T[n];
                if (n > _size)
                {
                    memcpy(temp, p, sizeof(T)*_size);                    
                    T* extra = new T[n - _size]{};
                    memcpy(temp + _size, extra, sizeof(T)*(n - _size));
                    delete[] extra;                    
                    _size = _capacity = n;
                }
                else
                {
                    memcpy(temp, p, sizeof(T)*n);
                    _size = n;
                }
                delete[] p;
                p = temp;
            }
        }
        inline void reserve(size_t n)
        {
            if (n <= _capacity)
                return;

            _capacity = n;
            T* temp = new T[_capacity];
            memcpy(temp, p, sizeof(T)*_size);
            delete[] p;
            p = temp;
        }
        inline void swap(vector<T>& rhs) noexcept
        {
            std::swap(p, rhs.p);
            std::swap(_size, rhs._size);
            std::swap(_capacity, rhs._capacity);
        }

        inline bool empty() const noexcept { return _size == 0; }
        inline void clear()  noexcept { _size = 0; }
        inline size_t size() const noexcept { return _size; }
        inline size_t capacity() const noexcept { return _capacity; }
    };
} // end of namesapce

C++ 11 이전에는 동적할당을 진행하는 클래스 선언 시 복사생성자, 대입연산자를 정의하면 끝이었지만, Modern C++ 이후 많은 변화가 있었습니다.

불필요한 복사를 줄이는 이동 생성자 (Move Constructor), 및 이동 할당 연산자 (Move Assignment Operator)도 필수적인 요소가 되었습니다.

RValue Reference을 이용한 Move Semantics를 활용해서 말이죠.

더불어 std::initialize_list (중괄호 초기화) 를 이용, 객체를 생성하는 부분도 같이 코드에 소개해 두었습니다. 

그럼 완성된 Custom Vector Class 테스트를 위해 std::vector VS ocs::vector 를 비교 동작해 보겠습니다.

(생성, 추가, 삽입, 삭제, 반복자 등) 

std::vector 는 sv, ocs::vector 는 ov로 구분.

#include<vector>는 std::vector,

#include"vector.h"는 위에서 만든 ocs::vector 를 의미.

벡터 생성

#include <iostream>
#include <vector>
#include "vector.h"

int main()
{
    std::vector<int> sv = { 0,1,2 };
    ocs::vector<int> ov = { 0,1,2 };
    
    std::cout << "std::vector" << '\n';
    for (auto& i : sv)
        std::cout << i << '\n';
    
    std::cout << "ocs::vector" << '\n';
    for (auto& i : ov)
        std::cout << i << '\n'; 
} 

ocs::vector 템플릿 클래스의 std::initialize_list {0, 1, 2} 를 전달인자로 받는 생성자가 호출되겠죠.

이어서 초기화 리스트로 *p 변수의 공간을 동적 할당하고, memcpy로 복사해 벡터를 생성합니다.

생성 결과는 아래와 같습니다.

[벡터 생성 비교]

벡터 추가

#include <iostream>
#include <vector>
#include "vector.h"

int main()
{
    std::vector<int> sv;
    sv.push_back(0);
    sv.push_back(1);
    sv.push_back(2);
    sv.push_back(3);

    ocs::vector<int> ov;
    ov.push_back(0);
    ov.push_back(1);
    ov.push_back(2);
    ov.push_back(3);
    
    std::cout << "std::vector" << '\n';
    for (auto& i : sv)
        std::cout << i << '\n';
    

    std::cout << "ocs::vector" << '\n';
    for (auto& i : ov)
        std::cout << i << '\n';
}

이번에는 explicit vector(size_t c = 1) 생성자를 호출해 벡터 객체가 생성됩니다.

사이즈(0), 용량(1) 인 벡터를 생성하고, push_back() 함수를 통해 사이즈가 충분하지 확인하고, 부족하다면 용량을 2배로 늘인 후 데이터를 복사합니다.

추가 결과는 아래와 같습니다.

[벡터 추가 비교]

벡터 삽입

#include <iostream>
#include <vector>
#include "vector.h"

int main()
{
    std::vector<int> sv;
    sv.push_back(0);
    sv.push_back(1);
    sv.push_back(2);
    sv.push_back(3);
    sv.insert(sv.begin(), -1);    

    ocs::vector<int> ov;
    ov.push_back(0);
    ov.push_back(1);
    ov.push_back(2);
    ov.push_back(3);
    ov.insert(ov.begin(), -1);
    
    std::cout << "std::vector" << '\n';
    for (auto& i : sv)
        std::cout << i << '\n';    

    std::cout << "ocs::vector" << '\n';
    for (auto& i : ov)
        std::cout << i << '\n';
}

ov.insert(ov.begin(), -1) 구문은 벡터의 시작위치에 -1을 삽입하라는 구문이며, insert() 함수는 2개의 전달인자를 받습니다.

반복자를 이용해 데이터를 삽입할 위치를 정하고, 이어서 삽입할 값을 넣어주면 됩니다.

만약 벡터의 n번째 위치에 삽입하고 싶다면 begin() + n 이라고 작성하고, iterator 의 operator+() 연산자가 동작해 위치를 정해주게 됩니다.

실제 std::vector의 insert() 오버로딩은 더 다양하지만 osv::vector는 2가지만 구현해봤습니다.

삽입 결과는 아래와 같습니다

[벡터 삽입 비교]

벡터 삭제

#include <iostream>
#include <vector>
#include "vector.h"

int main()
{
    std::vector<int> sv;
    sv.push_back(0);
    sv.push_back(1);
    sv.push_back(2);
    sv.push_back(3);
    sv.erase(sv.begin());    

    ocs::vector<int> ov;
    ov.push_back(0);
    ov.push_back(1);
    ov.push_back(2);
    ov.push_back(3);
    ov.erase(ov.begin());
    
    std::cout << "std::vector" << '\n';
    for (auto& i : sv)
        std::cout << i << '\n';    

    std::cout << "ocs::vector" << '\n';
    for (auto& i : ov)
        std::cout << i << '\n';
}

삭제는 insert() 와 마찬가지로 반복자를 전달인자로 받아서 처리합니다.

예제에서는 0, 1, 2, 3 을 벡터에 추가하고 첫위치인 0을 삭제합니다.

erase() 함수는 벡터 요소 하나만 삭제할 수도 있고, 삭제시작, 삭제 끝 반복자를 2개 받는 형태도 오버로딩 처리해두었습니다.

삭제 결과는 아래와 같습니다.

[벡터 삭제 비교]

 반복자 비교

#include <iostream>
#include <vector>
#include "vector.h"

int main()
{
    std::vector<int> sv;    
    for (int i = 0; i < 5; i++)
        sv.push_back(i);    

    ocs::vector<int> ov;    
    for (int i = 0; i < 5; i++)
        ov.push_back(i);
    
    std::cout << "std::vector" << '\n';    
    for (std::vector<int>::iterator itr = sv.begin(); itr!=sv.end(); ++itr)
        std::cout << *itr << '\n';    

    std::cout << "size: " << sv.size() << '\n';
    std::cout << "capa: " << sv.capacity() << '\n';

    std::cout << '\n';

    std::cout << "ocs::vector" << '\n';
    for(ocs::vector<int>::iterator itr = ov.begin(); itr!=ov.end(); ++itr)
        std::cout << *itr << '\n';        
    
    std::cout << "size: " << ov.size() << '\n';
    std::cout << "capa: " << ov.capacity() << '\n';    
}

반복자를 생성하고 역참조(*) 연산자를 이용해, 값을 출력합니다.

반복문의 종료조건인 end(), 즉 nullptr이 아니면 iterator의 operator++() 전위 증가 연산자를 호출해 다음 요소로 위치를 변경해 줍니다.

반복자 비교 결과는 아래와 같습니다.

[반복자 비교]

자세히 보면 서로 capacity가 다른데 저는 capacity가 부족하면 두배로 용량을 확보하게 해 두어서 서로 차이가 납니다.

 

마무리

대량의 데이터를 벡터에 추가하고 실행시간까지 측정해보진 않았지만, 아마도 표준 라이브러리에 비해서 느리고 최적화도 부족할 것입니다. 심지어는 버그도 있을 수 있습니다.

(컴파일 과정에서 오류가 난다면 언어 표준을 ISO C++ 14 이상 적용해보기 바랍니다.)

하지만 남이 만든 클래스(C++표준이라도)를 사용하는 것은 테크닉에 불과하고 본질을 이해하는 것이 아닙니다.

좀 서툴더라도, 버그가 있더라도, 실수하더라도, 시간이 걸리더라도 스스로 만들어 보는게 중요하다고 생각합니다.

혹시 std::list를 직접 구현해 보고 싶은 생각이 들지 않나요? 한번 도전해 보세요.

게시물 중 연결리스트 구현 예제를 참조바랍니다.

감사합니다.