프로젝트/STL 자료구조 구현

STL 자료구조 구현 (2) _ Vector<bool> 특수화

오의현 2024. 7. 21. 19:25

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;
};