어느 게임 개발자의 기록

Set은 레드블랙트리를 활용해서 데이터가 삽입, 삭제될 때마다 자동으로 트리의 균형을 맞추며 정렬하는 자료구조이다.

레드블랙트리 알고리즘에 따른 Insert까지는 일단 구현을 해보았다.

#pragma once
#include "Node.h"

#include <queue>
#include <string>

template<typename DataType>
class Set
{
private:
    using MyNode = typename TreeNode<DataType>;

public:
    using Iterator = typename BidirectionalIterator<DataType>;

public:
    Set()
    {
        NilNode = new MyNode();
        NilNode->Color = MyNode::NodeColor::Black;

        NilNode->LeftChild = NilNode;
        NilNode->RightChild = NilNode;
    }

    void Insert(const DataType& _Data)
    {
        MyNode* NewNode = InsertNewElement(_Data);

        if (NewNode == nullptr)
        {
            return;
        }

        MySize++;

        //더블레드발생
        while(NewNode != nullptr && NewNode != RootNode && (NewNode->Color == MyNode::NodeColor::Red && NewNode->Parent->Color == MyNode::NodeColor::Red))
        {
            NewNode = Balancing(NewNode);
        }
    }

private:

    MyNode* InsertNewElement(const DataType& _Data)
    {
        MyNode* NewNode = nullptr;

        if (RootNode == nullptr)
        {
            NewNode = CreateNewNode(_Data);

            RootNode = NewNode;
            RootNode->Parent = NilNode;
            RootNode->Color = MyNode::NodeColor::Black;
        }
        else
        {
            MyNode* CurNode = RootNode;

            while (true)
            {
                if (_Data < CurNode->Data)
                {
                    if (CurNode->LeftChild == NilNode)
                    {
                        NewNode = CreateNewNode(_Data);

                        CurNode->LeftChild = NewNode;
                        NewNode->Parent = CurNode;

                        break;
                    }
                    else
                    {
                        CurNode = CurNode->LeftChild;
                    }
                }
                else if (_Data > CurNode->Data)
                {
                    if (CurNode->RightChild == NilNode)
                    {
                        NewNode = CreateNewNode(_Data);

                        CurNode->RightChild = NewNode;
                        NewNode->Parent = CurNode;

                        break;
                    }
                    else
                    {
                        CurNode = CurNode->RightChild;
                    }
                }
                if (_Data == CurNode->Data)
                {
                    return NewNode;
                }
            }
        }

        return NewNode;
    }

    MyNode* CreateNewNode(const DataType& _Data)
    {
        MyNode* NewNode = new MyNode();

        NewNode->Data = _Data;
        NewNode->Color = MyNode::NodeColor::Red;
        NewNode->LeftChild = NilNode;
        NewNode->RightChild = NilNode;
        
        return NewNode;
    }

    MyNode* Balancing(MyNode* _InsertedNode)
    {
        if (_InsertedNode->Parent == NilNode)
        {
            return _InsertedNode;
        }

        MyNode* UncleNode = nullptr;
        MyNode* ParentNode = _InsertedNode->Parent;
        MyNode* Ancestor = _InsertedNode->Parent->Parent;

        if (ParentNode == Ancestor->LeftChild)
        {
            UncleNode = Ancestor->RightChild;
        }
        else if (ParentNode == Ancestor->RightChild)
        {
            UncleNode = Ancestor->LeftChild;
        }

        MyNode* ReturnNode = nullptr;

        if (UncleNode->Color == MyNode::NodeColor::Black)
        {
            ReturnNode = Restructuring(_InsertedNode, UncleNode);
        }
        else if (UncleNode->Color == MyNode::NodeColor::Red)
        {
            ReturnNode = ReColoring(_InsertedNode, UncleNode);
        }

        return ReturnNode;
    }

    MyNode* ReColoring(MyNode* _InsertedNode, MyNode* _UncleNode)
    {
        _InsertedNode->Parent->Color = MyNode::NodeColor::Black;
        _UncleNode->Color = MyNode::NodeColor::Black;

        _InsertedNode->Parent->Parent->Color = MyNode::NodeColor::Red;

        RootNode->Color = MyNode::NodeColor::Black;

        return _InsertedNode->Parent->Parent;
    }

    MyNode* Restructuring(MyNode* _InsertedNode, MyNode* _UncleNode)
    {
        MyNode* ParentNode = _InsertedNode->Parent;
        MyNode* AncestorNode = _InsertedNode->Parent->Parent;

        if (ParentNode == AncestorNode->LeftChild && _InsertedNode == ParentNode->LeftChild)
        {
            if (ParentNode->RightChild != NilNode)
            {
                AncestorNode->LeftChild = ParentNode->RightChild;
                AncestorNode->LeftChild->Parent = AncestorNode;
            }

            ParentNode->RightChild = AncestorNode;
            ParentNode->Parent = AncestorNode->Parent;
            
            if (AncestorNode == RootNode)
            {
                RootNode = ParentNode;
            }
            else if (AncestorNode->Parent->LeftChild == AncestorNode)
            {
                AncestorNode->Parent->LeftChild = ParentNode;
            }
            else if (AncestorNode->Parent->RightChild == AncestorNode)
            {
                AncestorNode->Parent->RightChild = ParentNode;
            }

            AncestorNode->Parent = ParentNode;
            AncestorNode->LeftChild = NilNode;

            ParentNode->Color = MyNode::NodeColor::Black;
            ParentNode->LeftChild->Color = MyNode::NodeColor::Red;
            ParentNode->RightChild->Color = MyNode::NodeColor::Red;
        }
        else if (ParentNode == AncestorNode->LeftChild && _InsertedNode == ParentNode->RightChild)
        {
            _InsertedNode->LeftChild = ParentNode;
            _InsertedNode->RightChild = AncestorNode;

            ParentNode->RightChild = NilNode;
            AncestorNode->LeftChild = NilNode;

            _InsertedNode->Parent = AncestorNode->Parent;

            if (AncestorNode == RootNode)
            {
                RootNode = _InsertedNode;
            }
            else if (AncestorNode->Parent->LeftChild == AncestorNode)
            {
                AncestorNode->Parent->LeftChild = _InsertedNode;
            }
            else if (AncestorNode->Parent->RightChild == AncestorNode)
            {
                AncestorNode->Parent->RightChild = _InsertedNode;
            }

            ParentNode->Parent = _InsertedNode;
            AncestorNode->Parent = _InsertedNode;

            _InsertedNode->Color = MyNode::NodeColor::Black;
            _InsertedNode->LeftChild->Color = MyNode::NodeColor::Red;
            _InsertedNode->RightChild->Color = MyNode::NodeColor::Red;
        }
        else if (ParentNode == AncestorNode->RightChild && _InsertedNode == ParentNode->LeftChild)
        {
            _InsertedNode->LeftChild = AncestorNode;
            _InsertedNode->RightChild = ParentNode;

            ParentNode->LeftChild = NilNode;
            AncestorNode->RightChild = NilNode;

            _InsertedNode->Parent = AncestorNode->Parent;

            if (AncestorNode == RootNode)
            {
                RootNode = _InsertedNode;
            }
            else if (AncestorNode->Parent->LeftChild == AncestorNode)
            {
                AncestorNode->Parent->LeftChild = _InsertedNode;
            }
            else if (AncestorNode->Parent->RightChild == AncestorNode)
            {
                AncestorNode->Parent->RightChild = _InsertedNode;
            }

            ParentNode->Parent = _InsertedNode;
            AncestorNode->Parent = _InsertedNode;

            _InsertedNode->Color = MyNode::NodeColor::Black;
            _InsertedNode->LeftChild->Color = MyNode::NodeColor::Red;
            _InsertedNode->RightChild->Color = MyNode::NodeColor::Red;
        }
        else if (ParentNode == AncestorNode->RightChild && _InsertedNode == ParentNode->RightChild)
        {
            if (ParentNode->LeftChild != NilNode)
            {
                AncestorNode->RightChild = ParentNode->LeftChild;
                ParentNode->LeftChild->Parent = AncestorNode;
            }

            ParentNode->LeftChild = AncestorNode;
            ParentNode->Parent = AncestorNode->Parent;

            if (AncestorNode == RootNode)
            {
                RootNode = ParentNode;
            }
            else if (AncestorNode->Parent->LeftChild == AncestorNode)
            {
                AncestorNode->Parent->LeftChild = ParentNode;
            }
            else if (AncestorNode->Parent->RightChild == AncestorNode)
            {
                AncestorNode->Parent->RightChild = ParentNode;
            }

            AncestorNode->Parent = ParentNode;
            AncestorNode->RightChild = NilNode;

            ParentNode->Color = MyNode::NodeColor::Black;
            ParentNode->LeftChild->Color = MyNode::NodeColor::Red;
            ParentNode->RightChild->Color = MyNode::NodeColor::Red;
        }

        return nullptr;
    }

public:

	MyNode* NilNode = nullptr;
	MyNode* RootNode = nullptr;
	MyNode* EndNode = nullptr;

	size_t MySize = 0;
};

먼저, 처음 자료구조가 생성되면 NilNode를 만들어서 포인터를 저장해주었다.

그리고, 데이터가 삽입되면 양쪽 자식을 NilNode를 가리키게 하였고 루트노드라면 추가적으로 부모 노드또한 NilNode를 가리키도록 하였다.

데이터가 삽입되면, 먼저 크기에 따라 위치를 잡도록 하였다. 루트노드부터 시작해서 기준 노드보다 값이 작다면 왼쪽으로 값이 크다면 오른쪽으로 이동하도록 하였다.

이동이 완료되면 해당 노드와 해당 노드의 부모 노드의 색을 보고 정렬을 실시하도록 하였다. 만약, 해당 노드의 색이 Red이고 부모 노드의 색도 Red라면 레드블랙트리 알고리즘에선 균형을 잡는 과정을 거쳐야 하기 때문에 균형을 잡는 Balancing 함수를 실시하도록 하였다.

Balancing 함수 내부에선 삽입된 노드의 삼촌 노드를 확인하고, 삼촌 노드의 색에 따라 ReColoring혹은 ReStructuring 함수를 실시하도록 하였다.

Recoloring은 노드의 위치를 바꾸지 않고 색만 바꾸는 작업이고, ReStructuring는 노드의 위치를 바꾸는 작업이다.

두 함수를 통해 DoubleRed(빨간색 노드가 연속으로 이어진 상황)이 해결되고 나면 Insert 함수를 종료하도록 하였다.

원래는 node를 하나 만들어서 List와 Set,Map이 같이 사용하도록 하려했는데

당연하게도 둘이 사용해야 할 노드가 성격이 다르다.

그래서 Node를 외부로 빼서 TreeNode와 ListNode를 따로 만들어주었다. 하지만, 두 노드간의 일관적인 인터페이스가 있어야 양방향 이터레이터에서 동일한 방식으로 자료구조를 다룰 수 있기 때문에 Node라는 최상위 클래스를 만들어서 그 안에 순수 가상함수를 선언해놓고 이를 상속받도록 하였다.

#pragma once

template<typename DataType>
class Node
{
public:
    virtual void operator=(const Node<DataType>* _Node) = 0;

    virtual Node<DataType>* operator++() = 0;
    virtual Node<DataType>* operator++(int) = 0;
    virtual Node<DataType>* operator--() = 0;
    virtual Node<DataType>* operator--(int) = 0;

    virtual const DataType& Get() = 0;
};

template<typename DataType>
class ListNode : public Node<DataType>
{
public:
    void operator=(const Node<DataType>* _Node)
    {
        const ListNode<DataType>* CastedNode = dynamic_cast<const ListNode<DataType>*>(_Node);

        Data = CastedNode->Data;
        PrevNode = CastedNode->PrevNode;
        NextNode = CastedNode->NextNode;
    }

    ListNode<DataType>* operator++() override
    {
        *this = NextNode;
        return this;
    }

    ListNode<DataType>* operator++(int) override
    {
        ++(*this);
        return PrevNode;
    }

    ListNode<DataType>* operator--() override
    {
        *this = PrevNode;
        return this;
    }

    ListNode<DataType>* operator--(int) override
    {
        --(*this);
        return NextNode;
    }

    const DataType& Get() override
    {
        return Data;
    }

    DataType Data;
    ListNode<DataType>* PrevNode = nullptr;
    ListNode<DataType>* NextNode = nullptr;
};

template<typename DataType>
class TreeNode : public Node<DataType>
{
public:
    enum NodeColor
    {
        None,
        Red,
        Black,
    };

    void operator=(const Node<DataType>* _Node)
    {
    }

    TreeNode<DataType>* operator++() override
    {
        return this;
    }

    TreeNode<DataType>* operator++(int) override
    {
        return nullptr;
    }

    TreeNode<DataType>* operator--() override
    {
        return nullptr;
    }

    TreeNode<DataType>* operator--(int) override
    {
        return nullptr;
    }

    const DataType& Get() override
    {
        return Data;
    }

    DataType Data;
    
    NodeColor Color = NodeColor::None;

    TreeNode<DataType>* Parent = nullptr;
    TreeNode<DataType>* LeftChild = nullptr;
    TreeNode<DataType>* RightChild = nullptr;
};

TreeNode는 아직 함수 구현은 하지 않은 상태이다. 먼저 Set을 만들고 그에 맞게 구조를 맞춰볼 생각이다.

일단, 원래는 Node 클래스가 List 내부에 있었는데 이를 외부로 뺐다.

그리고 양방향 이터레이터, List, Map, Set이 모두 같은 Node클래스를 공유해서 구현되도록 할 예정이다.

이를 기반으로 양방향 이터레이터의 연산자를 몇개 오버로딩해보았다.

template<typename DataType>
class BidirectionalIterator
{
    using Node = typename Node<DataType>;
public:
    BidirectionalIterator(const Node* _Node)
    {
        NodePtr = const_cast<Node*>(_Node);
    }
    
    BidirectionalIterator(Node&& _Node)
    {
        NodePtr = _Node;

        _Node.PrevNode = nullptr;
        _Node.NextNode = nullptr;
    }

    const DataType& operator*()
    {
        return NodePtr->Data;
    }

    BidirectionalIterator& operator--()
    {
        NodePtr = NodePtr->PrevNode;
        return *this;
    }

    BidirectionalIterator operator--(int)
    {
        Node* ReturnNode = NodePtr;
        NodePtr = NodePtr->PrevNode;
        return BidirectionalIterator(ReturnNode);
    }

    BidirectionalIterator& operator++()
    {
        NodePtr = NodePtr->NextNode;
        return *this;
    }

    BidirectionalIterator operator++(int)
    {
        Node* ReturnNode = NodePtr;
        NodePtr = NodePtr->NextNode;
        return BidirectionalIterator(ReturnNode);
    }

private:
    Node* NodePtr = nullptr;
};

간단하게 추가를 했고, 제대로 사용하기 위해선 연산자가 좀 더 필요한데 일단 추후에 추가하기로 하고

List에도 이 이터레이터를 기반으로 Begin과 End를 추가하였다.

using Node = typename Node<DataType>;
using Iterator = typename BidirectionalIterator<DataType>;

일단 이렇게 using 구문을 추가해주고..

Iterator Begin()
{
    return Iterator(Head->NextNode);
}

Iterator End()
{
    return Iterator(Tail);
}

이렇게 begin과 end를 간단하게 추가하였다.,

Head와 Tail은 더미노드라서 Begin 은 Head의 NextNode를 해주었다.

End는 원래 마지막 데이터의 다음 노드를 가리키기 때문에 Tail을 그대로 리턴해주었다.

일단 테스트 해봤는데 컴파일도 잘되고 기능도 문제 없는듯 하다.

일단 다음에 연산자를 몇개 추가하고 List의 멤버함수를 좀 더 추가한 다음

Map과 Set을 구현해보아야겠다.

기존에는 커스텀예외객체만을 생성해놓고 try, catch는 모두 자료구조의 함수 안에서 실행하도록 했지만, 이젠 try catch를 호출하는 static 클래스를 만든 뒤, 자료구조에선 해당 함수를 호출하도록 하였다.

#pragma once
#include <cassert>
#include "CustomException.h"

enum class ExceptionType
{
    OutOfRange,
    EmptyContainer,
};

class ExceptionFunction
{
public:
    static void CheckException(bool _IsOccurred, bool _DoAssert, const char* _ClassName, ExceptionType _ExceptionType)
    {
        try
        {
            if (_IsOccurred == true)
            {
                ThrowException(_ClassName, _ExceptionType);
            }
        }
        catch (std::exception& _Error)
        {
            std::cerr << _Error.what() << std::endl;
            assert(_DoAssert);
        }
    }

private:
    static void ThrowException(const char* _ClassName, ExceptionType _ExceptionType)
    {
        switch (_ExceptionType)
        {
        case ExceptionType::OutOfRange:
            throw CustomException::OutOfLange(_ClassName);
            break;
        case ExceptionType::EmptyContainer:
            throw CustomException::EmptyContainer(_ClassName);
            break;
        }
    }
};

이렇게, 외부에선 CheckException 함수를 호출하여 파라미터를 잘 대입해준다면, 예외 발생 여부를 검사하고 그에 맞는 메세지를 출력하고 예외 객체를 던지고 assert하는 것까지 모두 해당 함수 내부에서 처리하도록 하였다.

virtual const bool& At(size_t _Index) 
{	
    try
    {
        if (_Index >= MySize)
        {
            throw CustomException::OutOfLange();
        }
    }
    catch (std::exception& _Error)
    {
        std::cerr << _Error.what() << std::endl;
        assert(false);
    }

    return MyElements[_Index];
}

위는 기존의 At 코드인데, 이 코드는 아래와 같이 바뀌었다.

virtual const bool& At(size_t _Index) 
{
    ExceptionFunction::CheckException(_Index >= MySize, true, typeid(*this).name(), ExceptionType::OutOfRange);
    return MyElements[_Index];
}

그리고, List도 일부 기능을 구현하였다.

먼저, List클래스 내부에서만 사용할 수 있는 Node 중첩 클래스를 선언하였고, 이를 통해 원소들이 연결되도록 하였다.

List는 Head와 Tail을 보유하고 있고, 더미노드를 생성하여 각각 더미노드를 가리키도록 하였다.

즉 List의 가장 앞의 원소는 Head의 다음 원소가 되는 셈이며, 가장 뒤의 원소는 Tail의 앞의 원소가 되는 것이다.

아래는 구현된 코드 전문이다.

#pragma once
#include "ExceptionFunction.h"

template <typename DataType>
class List
{
    class Node;
public:
    List()
    {
        CreateDummyNode();
    }

    List(size_t _Size)
    {
        CreateDummyNode();
        
        for (int i = 0; i < _Size; i++)
        {
            Push_Back(DataType());
        }
    }

    List(size_t _Size, const DataType& _Data)
    {
        CreateDummyNode();

        for (int i = 0; i < _Size; i++)
        {
            Push_Back(_Data);
        }
    }

    List(size_t _Size, DataType&& _Data)
    {
        CreateDummyNode();

        for (int i = 0; i < _Size; i++)
        {
            Push_Back(_Data);
        }
    }

public:
    void Push_Back(const DataType& _Data)
    {
        Node* NewNode = new Node();
        NewNode->DataPtr = _Data;

        Node* CurBackNode = Tail->PrevNode;
        CurBackNode->NextNode = NewNode;

        NewNode->PrevNode = CurBackNode;
        NewNode->NextNode = Tail;

        Tail->PrevNode = NewNode;

        MySize++;
    }

    void Push_Back(DataType&& _Data)
    {
        Node* NewNode = new Node();
        NewNode->DataPtr = _Data;

        Node* CurBackNode = Tail->PrevNode;
        CurBackNode->NextNode = NewNode;

        NewNode->PrevNode = CurBackNode;
        NewNode->NextNode = Tail;

        Tail->PrevNode = NewNode;

        MySize++;
    }

    const DataType& Front()
    {
        ExceptionFunction::CheckException(Head->NextNode == nullptr, true, typeid(*this).name(), ExceptionType::OutOfRange);
        return Head->NextNode->DataPtr;
    }

    const DataType& Back()
    {
        ExceptionFunction::CheckException(Tail->PrevNode == nullptr, true, typeid(*this).name(), ExceptionType::OutOfRange);
        return Tail->PrevNode->DataPtr;
    }

private:
    class Node
    {
    public:
        void operator=(const Node* _Node)
        {
            DataPtr = _Node->DataPtr;
            PrevNode = _Node->PrevNode;
            NextNode = _Node->NextNode;
        }

        const Node* operator++()
        {
            *this = NextNode;
            return *this;
        }

        const Node operator++(int)
        {
            Node ReturnNode = NextNode;
            ++(*this);
            return ReturnNode;
        }

        const Node* operator--()
        {
            *this = PrevNode;
            return *this;
        }

        const Node* operator--(int)
        {
            Node ReturnNode = PrevNode;
            --(*this);
            return ReturnNode;
        }

        DataType* DataPtr = nullptr;
        Node* PrevNode = nullptr;
        Node* NextNode = nullptr;
    };

private:
    void CreateDummyNode()
    {
        Node* DummyHead = new Node();
        Node* DummyTail = new Node();

        Head = DummyHead;
        Tail = DummyTail;

        DummyTail->PrevNode = Head;
        DummyHead->NextNode = Tail;
    }

private:
    Node* Head = nullptr;
    Node* Tail = nullptr;
    
    size_t MySize = 0;
};

기존에는 이터레이터가 벡터에 중첩클래스로 종속되어 있었고 이를 이용하는 형식이었는데, STL의 구조를 면밀히 살펴보니 Iterator은 완전히 별개의 클래스고 자료구조는 여기에 데이터를 담아 반환해줄 뿐인 것 같았다.

그래서 이터레이터를 아예 별개의 클래스로 분리해주었다.

이터레이터의 종류는 InputIterator, OutputIterator, forwardIterator, BiDirectionalIterator, RandomAccessIterator로 총 5가지가 있다고 하는데, 난 일단 벡터에서 사용할 RandomAccessIterator만 구현하였다.

template <typename DataType>
class RandomAccessIterator
{
public:
    RandomAccessIterator()
    {
    }

    RandomAccessIterator(const DataType* _DataPtr)
    {
        DataPtr = const_cast<DataType*>(_DataPtr);
    }

    RandomAccessIterator(const RandomAccessIterator& _Other)
    {
        DataPtr = _Other.DataPtr;
    }

    RandomAccessIterator& operator=(const RandomAccessIterator& _Other)
    {
        DataPtr = _Other.DataPtr;
        return *this;
    }

    RandomAccessIterator& operator=(RandomAccessIterator&& _Other) noexcept
    {
        DataPtr = _Other.DataPtr;
        _Other.DataPtr = nullptr;

        return *this;
    }

    bool operator==(const RandomAccessIterator& _Other)
    {
        return (DataPtr == _Other.DataPtr);
    }

    bool operator!=(const RandomAccessIterator& _Other)
    {
        return !(*this == _Other);
    }
    
    RandomAccessIterator& operator++()
    {
        (DataPtr)++;
        return *this;
    }

    RandomAccessIterator operator++(int)
    {
        RandomAccessIterator ReturnIter(*this);
        ++(*this);
        return ReturnIter;
    }

    RandomAccessIterator& operator--()
    {
        (DataPtr)--;
        return *this;
    }

    RandomAccessIterator operator--(int)
    {
        RandomAccessIterator ReturnIter(*this);
        --(*this);
        return ReturnIter;
    }
     
    RandomAccessIterator& operator+(int _Offset)
    {
        DataPtr += _Offset;
        return *this;
    }

    RandomAccessIterator& operator-(int _Offset)
    {
        DataPtr -= _Offset;
        return *this;
    }

    DataType& operator*()
    {
        return *(DataPtr);
    }

    void Debug()
    {
        std::cout << *(DataPtr);
    }

private:
    DataType* DataPtr = nullptr;
};

bool을 제외한 자료형에 대해서 위와 같이 선언해주었다. 기존의 이터레이터와 정의는 완전히 동일하다.

따로 수정을 안해도 될 것 같아서 그대로 외부로 꺼내기만 했는데, 이는 추후 테스트를 좀 해봐야 할 듯 하다.

bool타입이 문제가 좀 많았다. 먼저, *연산자를 사용하면 bool값을 반환해야 하는 동시에 *연산자로 반환된 데이터에 =연산자를 통해 값을 바꿀 수도 있어야 했다. 아무래도 bool 타입은 비트단위로 관리되다 보니 일반적인 포인터로 구현하는 것이 불가능했는데, 이를 중첩클래스를 활용해 해결하였다. 먼저 코드 전문을 보자.

template<>
class RandomAccessIterator<bool>
{
    class BitReference;

public:
    RandomAccessIterator()
    {
    }

    RandomAccessIterator(unsigned int* _DataPtr, size_t _BitIndex)
    {
        DataPtr = _DataPtr;
        BitIndex = _BitIndex;
    }

    RandomAccessIterator(const RandomAccessIterator& _Other)
    {
        DataPtr = _Other.DataPtr;
        BitIndex = _Other.BitIndex;
    }

    RandomAccessIterator& operator=(const RandomAccessIterator& _Other)
    {
        DataPtr = _Other.DataPtr;
        BitIndex = _Other.BitIndex;

        return *this;
    }

    RandomAccessIterator& operator=(RandomAccessIterator&& _Other) noexcept
    {
        DataPtr = _Other.DataPtr;
        BitIndex = _Other.BitIndex;
        _Other.DataPtr = nullptr;

        return *this;
    }

    bool operator==(const RandomAccessIterator& _Other)
    {
        return (DataPtr == _Other.DataPtr && BitIndex == _Other.BitIndex);
    }

    bool operator!=(const RandomAccessIterator& _Other)
    {
        return !(*this == _Other);
    }

    RandomAccessIterator& operator++()
    {
        BitIndex++;

        if (BitIndex >= 32)
        {
            BitIndex = 0;
            DataPtr++;
        }

        return *this;
    }

    RandomAccessIterator operator++(int)
    {
        RandomAccessIterator ReturnIter(*this);
        ++(*this);
        return ReturnIter;
    }

    RandomAccessIterator& operator--()
    {
        BitIndex--;

        if (BitIndex < 0)
        {
            BitIndex = 31;
            DataPtr--;
        }

        return *this;
    }

    RandomAccessIterator operator--(int)
    {
        RandomAccessIterator ReturnIter(*this);
        --(*this);
        return ReturnIter;
    }

    RandomAccessIterator operator+(int _Offset)
    {
        size_t ReturnBitIndex = BitIndex + _Offset;
        unsigned int* ReturnDataPtr = DataPtr;

        while (ReturnBitIndex >= 32)
        {
            ReturnBitIndex -= 32;
            ReturnDataPtr++;
        }

        return RandomAccessIterator(ReturnDataPtr, ReturnBitIndex);
    }

    RandomAccessIterator operator-(int _Offset)
    {
        size_t ReturnBitIndex = BitIndex - _Offset;
        unsigned int* ReturnDataPtr = DataPtr;

        while (ReturnBitIndex >= 32)
        {
            ReturnBitIndex += 32;
            ReturnDataPtr--;
        }

        return RandomAccessIterator(ReturnDataPtr, ReturnBitIndex);
    }

    BitReference operator*()
    {
        return BitReference(DataPtr, BitIndex);
    }

    void Debug()
    {
        std::cout << *(DataPtr);
    }

private:
    class BitReference
    {
    public:
        BitReference(const unsigned int* _DataPtr, size_t _BitIndex)
        {
            DataPtr = const_cast<unsigned int*>(_DataPtr);
            BitIndex = _BitIndex;
        }

        operator bool() const
        {
            return (*DataPtr) & (1 << BitIndex);
        }


        void operator=(bool _Value)
        {
            if (_Value == true)
            {
                (*DataPtr) |= (1 << BitIndex);
            }
            else
            {
                (*DataPtr) &= ~(1 << BitIndex);
            }
        }

    private:
        unsigned int* DataPtr = nullptr;
        size_t BitIndex = 0;
    };

private:
    unsigned int* DataPtr = nullptr;
    size_t BitIndex = 0;
};

먼저, *연산자를 호출하면 BitReference라는 클래스를 생성하여 이를 반환하도록 하였다. 그리고 BitReference 클래스 내부에 = 연산자를 오버로딩하여 이를 통해 값을 바꿀 수 있도록 하였다.

또한, *연산자를 통해 bool 값도 반환받을 수 있어야 하기 때문에 BitReference 클래스에 bool타입으로의 캐스팅 연산자를 오버로딩하여 값을 받을 수 있도록 하였다.

먼저, vector은 bool타입에 대해 특수화되어있다.

하지만, vector은 bool타입이라고 하더라도 동일한 인터페이스를 보유해야 한다.

그러므로, 상속을 통해 멤버함수들을 순수 가상함수로 선언해주었다.

template<typename DataType>
class VectorBase
{
public:
	class Iterator;

public:
	virtual void Reserve(const size_t _Capacity) = 0;
	virtual void Resize(const size_t _Size) = 0;
	virtual void Resize(const size_t _Size, const DataType& _Data) = 0;
	virtual void Resize(const size_t _Size, DataType&& _Data) = 0;
	
	virtual void Push_Back(const DataType& _Data) = 0;
	virtual void Push_Back(DataType&& _Data) = 0;
	virtual void Pop_back() = 0;
	
	virtual void Insert(const Iterator& _Where, const DataType& _Value) = 0;
	virtual void Clear() = 0;
	
	virtual const DataType& At(size_t _Index) = 0;
	virtual const DataType& Front() = 0;
	virtual const DataType& Back() = 0;
};

공통으로 구현해야 하는 함수들을 VectorBase라는 함수에 선언하였고, 이 클래스를 상속받도록 하였다.

또한, Iterator 클래스를 Vector이 아닌 VectorBase 내부로 이동시켜주었다.

이로 인해 템플릿 클래스의 중첩 클래스인 Iterator을 컴파일러가 혼동할 수 있으므로, Vector에는 아래의 구문을 추가해주었다.

using Iterator = typename VectorBase<DataType>::Iterator;

위의 구문으로 인해, 사용이 편해진 건 덤이다.  

그리고 이를 기반으로, bool 타입을 제외한 Vector의 멤버함수에 몇 가지 함수를 추가로 구현해주었다.

const DataType& Front() override
{
	return MyElements[0];
}

const DataType& Back() override
{
	return MyElements[MySize - 1];
}

void Clear() override
{
    MySize = 0;
    EndPtr = BeginPtr + 1;
}

void Pop_back() override
{
    if (MySize > 0)
    {
    	MySize--;
    	EndPtr--;
    }
}

void Insert(const Iterator& _Where, const DataType& _Value) override
{
    if (MySize + 1 >= MyCapacity)
    {
        Reserve(MyCapacity * 2);
    }

    Iterator EndIter = End();

    while (_Where != EndIter)
    {
        *EndIter = *(EndIter - 1);
    }
}

이제, Vector<bool> 타입에 대해 함수를 모두 구현해주면 Vector는 일단은 마무리이다.

디버깅을 위해 커스텀 예외처리 클래스를 만들었다. 물론 C++에서 제공하는 예외처리 클래스가 존재하지만, 그냥 만들어보았다. 별 것도 아니고 그냥 코드 몇 줄 적으면 되는거지만 아무튼 만들어보는게 도움이 될 것 같았다.

#pragma once
#include <exception>

class CustomException
{
public:
    class OutOfLange : public std::exception
    {
    public:
        OutOfLange()
        {

        }

        OutOfLange(const char* _ClassName)
        {
            ClassName = _ClassName;
        }

        const char* what() const noexcept override
        {
            static std::string ExMsg = "Exception is detected : OutOfLange\nClassName : " + ClassName;
            return ExMsg.c_str();
        }

    private:
        std::string ClassName = "";
    };
};

먼저, CustomException 클래스를 만들었고, 그 안에 예외처리 클래스를 넣어두었다.

CustomException은 일종의 네임스페이스처럼 사용되는 셈이다.

그 안에는 먼저, 범위를 초과할 때 사용될 OutOfLange 클래스를 만들었다. 해당 클래스는 std::excpetion 클래스를 상속받고 있으며 What 함수를 오버라이딩하였다.

생성자에서 클래스의 typeid를 받아 이를 저장하고, 예외처리 메세지에 사용하는 구조로 만들어주었다.

이 예외처리를 기반으로 Vector클래스 내부에 At함수를 만들었다.

DataType operator[](size_t _Index)
{
    return *(BeginPtr + _Index);
}

먼저, [] 연산자는 이렇게 예외처리없이 포인터에 접근하도록 하였다. 그렇기 때문에 사이즈를 벗어난 값이 인자로 들어오면 무슨 일이 발생할 지 예측할 수 없다.

DataType At(size_t _Index)
{
    try 
    {
        if (_Index >= MySize)
        {
            throw CustomException::OutOfLange(typeid(*this).name());
        }
    }
    catch (std::exception& _Error)
    {
        std::cerr << _Error.what() << std::endl;
    }

    return *(BeginPtr + _Index);
}

At함수에는 이처럼 예외처리를 해주었다.

인자가 벡터의 원소개수보다 크거나 같다면 예외를 반환하도록 하였다.

예외 객체는 위에서 만들었던 OutOfLange 클래스를 반환해주었다.

Catch에선 OutOfLange에서 오버라이딩한 what함수를 호출하여 에러메세지를 출력하도록 하였다.

벡터의 이터레이터를 구현하였다.

처음엔, IteratorBase를 구현하고 이를 모든 자료구조의 Iterator이 상속받도록 하여 Algorithm 함수가 다양한 Iterator에 대해 대응하도록 하고 싶었고, 또 순수가상함수를 이용해 이터레이터간의 공통적인 인터페이스를 구현하고 싶었다.

하지만, 공변의 문제로 가상함수화 하기 힘든 연산자들이 몇몇 있었다. 이 때문에 구조를 각 자료구조의 이터레이터에 맞게 Algorithm 함수를 여러개로 오버로딩하는 방식으로 하기로 하였다.

일단 벡터의 이터레이터는 아래와 같이 필요한 연산자만 구현해놓았다.

더 필요하다면 추가로 구현할 것이고, 일단은 이정도만 구현해놓았다.

template<typename DataType>
class Vector<DataType>::Iterator
{
public:
	Iterator()
	{
	}

	Iterator(const DataType* _DataPtr)
	{
		DataPtr = const_cast<DataType*>(_DataPtr);
	}

	Iterator(const Iterator& _Other)
	{
		DataPtr = _Other.DataPtr;
	}

	Iterator& operator=(const Iterator& _Other)
	{
		DataPtr = _Other.DataPtr;
		return *this;
	}

	Iterator& operator=(Iterator&& _Other)
	{
		DataPtr = _Other.ataPtr;
		_Other.DataPtr = nullptr;

		return *this;
	}

	bool operator==(const Iterator& _Other)
	{
		return (DataPtr == _Other.DataPtr);
	}

	bool operator!=(const Iterator& _Other)
	{
		return !(*this == _Other);
	}

	Iterator& operator++()
	{
		(DataPtr)++;
		return *this;
	}

	Iterator operator++(int)
	{
		Iterator ReturnIter(*this);
		++(*this);
		return ReturnIter;
	}
	 
	DataType operator*()
	{
		return *(DataPtr);
	}

	void Debug()
	{
		std::cout << *(DataPtr);
	}

private:
	DataType* DataPtr = nullptr;
};

벡터의 멤버함수에는 위의 이터레이터를 토대로 Begin과 End를 추가하였다.

Iterator Begin()
{
    return Iterator(BeginPtr);
}

Iterator End()
{
    return Iterator(EndPtr);
}

여러 자료구조간의 공통의 인터페이스를 구현하기 위해 상속을 사용할 필요는 있을 것 같은데, 아직은 어떤 식으로 디자인 할 지 감이 잘 안온다.

일단 벡터를 모두 마무리 하고, 리스트까지 만든 다음에 두 클래스의 구조를 비교하면서 고민해봐야 할 듯 하다.

STL의 vector 템플릿은 bool 자료형에 대해 특수화되어있다.

bool타입은 기본 1바이트를 사용하지만, 비트연산을 활용하면 1바이트에 8개의 boolean값을 저장할 수 있기 때문이다.

이로 인한 여러 문제들도 있다지만, STL을 모방하는 프로젝트인만큼 bool 타입에 특수화를 진행하였다. 

일단은 생성자 부분만 정의하였고, 정의된 내용은 아래 코드와 같다.

다음엔 [], * 등 연산자를 오버로딩할 것이며 이터레이터를 추가하여 begin, end 등의 함수를 정의할 것이다.

template <>
class Vector<bool>
{
public:
    //Default
    Vector() : MySize(0), MyCapacity(32)
    {
        if (MyElements == nullptr)
        {
            MyElements = new unsigned int[MyCapacity]();
            BeginPtr = MyElements;
        }
    }

    //Only Size
    Vector(const size_t _Size)
    {
        if (BeginPtr == nullptr)
        {
            MySize = _Size;
            MyCapacity = _Size + (32 - (_Size % 32));

            MyElements = new unsigned int[MyCapacity](0);
            BeginPtr = MyElements;
        }
    }
    
    //Size, Data
    Vector(const size_t _Size, const bool _Data)
    {
        if (BeginPtr == nullptr)
        {
            MySize = _Size;
            MyCapacity = _Size + (32 - (_Size % 32));

            MyElements = new unsigned int[MyCapacity](0);
            BeginPtr = MyElements;
            
            if (_Data == true)
            {
                RangedBitOn(0, 0, _Size / 32, _Size % 32);
            }
            else
            {
                RangedBitOff(0, 0, _Size / 32, _Size % 32);
            }
        }
    }

    ~Vector()
    {
        if (MyElements != nullptr)
        {
            delete[] MyElements;

            BeginPtr = nullptr;
            MyElements = nullptr;
        }
    }

private:
    void BitOff(size_t _Index, size_t _Bit)
    {
        MyElements[_Index] &= ~(1 << _Bit);
    }

    void BitOn(size_t _Index, size_t _Bit)
    {
        MyElements[_Index] |= (1 << _Bit);
    }

    void RangedBitOn(size_t _StartIndex, size_t _StartBit, size_t _EndIndex, size_t _EndBit)
    {
        size_t Start = _StartIndex * 32 + _StartBit;
        size_t End = _EndIndex * 32 + _EndBit;

        for (size_t i = Start; i < End; i++)
        {
            size_t Index = i / 32;
            size_t Bit = i % 32;

            MyElements[Index] |= (1 << Bit);
        }
    }

    void RangedBitOff(size_t _StartIndex, size_t _StartBit, size_t _EndIndex, size_t _EndBit)
    {
        size_t Start = _StartIndex * 32 + _StartBit;
        size_t End = _EndIndex * 32 + _EndBit;

        for (size_t i = Start; i < End; i++)
        {
            size_t Index = i / 32;
            size_t Bit = i % 32;

            MyElements[Index] &= ~(1 << Bit);
        }
    }

private:
    unsigned int* BeginPtr = nullptr;
    unsigned int* MyElements = nullptr;

    size_t MySize = 0;
    size_t MyCapacity = 0;
};

생성자, 소멸자를 정의하였고 reserve, resize, push_back, emplace_back 를 정의하였다.

기존에 알고 있던 STL의 작동 원리를 바탕으로 만들어보았다.

아래는 현재까지 작성된 코드 전문이다.

#pragma once
#include <memory>

template<typename DataType>
class Vector 
{
public:
    //Default
    Vector() : MySize(0), MyCapacity(4)
    {
        if (MyElements == nullptr)
        {
            MyElements = new DataType[MyCapacity]();
            
            BeginPtr = MyElements;
            EndPtr = MyElements;
        }
    }

    //Only Size
    Vector(const size_t _Size) : MySize(_Size), MyCapacity(_Size)
    {
        if (BeginPtr == nullptr)
        {
            MyElements = new DataType[MyCapacity]();

            BeginPtr = MyElements;
            EndPtr = BeginPtr + _Size;
        }
    }

    //Size, Data (L-Value)
    Vector(const size_t _Size, const DataType& _Data) : MySize(_Size), MyCapacity(_Size)
    {
        if (BeginPtr == nullptr)
        {
            MyElements = new DataType[MyCapacity];

            BeginPtr = MyElements;
            EndPtr = BeginPtr + _Size;

            for (size_t i = 0; i < _Size; i++)
            {
          	    MyElements[i] = _Data;
            }
        }
    }

    //Size, Data (R-Value)
    Vector(const size_t _Size, DataType&& _Data) : MySize(_Size), MyCapacity(_Size)
    {
        if (BeginPtr == nullptr)
        {
            MyElements = new DataType[MyCapacity];

            BeginPtr = MyElements;
            EndPtr = BeginPtr + _Size;

            for (size_t i = 0; i < _Size; i++)
            {
                MyElements[i] = std::forward<DataType>(_Data);
            }
        }
    }

    ~Vector()
    {
        if (MyElements != nullptr)
        {
            delete[] MyElements;

            BeginPtr = nullptr;
            EndPtr = nullptr;
            MyElements = nullptr;
        }
    }
    
public:
    void Reserve(const size_t _Capacity)
    {
        ReAllocate(_Capacity);
    }

    void Resize(const size_t _Size)
    {
        ReAllocate(_Size);
        MySize = _Size;
    }

    void Resize(const size_t _Size, const DataType& _Data)
    {
        ReAllocate(_Size);

        for (int i = MySize; i < _Size; i++)
        {
            MyElements[i] = _Data;
        }

        MySize = _Size;
    }

    void Resize(const size_t _Size, DataType&& _Data)
    {
        ReAllocate(_Size);

        for (size_t i = MySize; i < _Size; i++)
        {
            MyElements[i] = std::forward<DataType>(_Data);
        }

        MySize = _Size;
    }

public:
    template<typename... Valty>
    void Emplace_Back(Valty&&... _Value)
    {
        if (MySize == MyCapacity)
        {
            ReAllocate(MyCapacity * 2);
        }

        new (&MyElements[MySize]) DataType(std::forward<Valty>(_Value)...);

        ++MySize;
        ++EndPtr;
    }

    void Push_Back(const DataType& _Data)
    {
        if (MySize == MyCapacity)
        {
            ReAllocate(MyCapacity * 2);
        }
    
        MyElements[MySize] = _Data;
        
        ++MySize;
        ++EndPtr;
    }
    
    void Push_Back(DataType&& _Data)
    {
        if (MySize == MyCapacity)
        {
            ReAllocate(MyCapacity * 2);
        }
    
        MyElements[MySize] = std::forward<DataType>(_Data);
        
        ++MySize;
        ++EndPtr;
    }

private:
    void ReAllocate(const size_t _Capacity)
    {
        if (_Capacity <= MyCapacity)
        {
            return;
        }


        DataType* NewPtr = new DataType[_Capacity]();

        for (size_t i = 0; i < MySize; i++)
        {
            NewPtr[i] = std::move(MyElements[i]);
        }

        BeginPtr = NewPtr;
        EndPtr = BeginPtr + MySize;

        delete[] MyElements;

        MyElements = NewPtr;

        MyCapacity = _Capacity;
    }

private:
    DataType* BeginPtr = nullptr;
    DataType* EndPtr = nullptr;

    DataType* MyElements = nullptr;
    
    size_t MySize = 0;
    size_t MyCapacity = 0;
};