[자료구조/정리] 배열(Array)

[ 전체 코드 ] 

Array.h

#pragma once

#include <assert.h>
/*
    [assert()]
    경고창을 띄워줌.
*/

template <typename T>
class CArrayNode
{
    template <typename T>
    friend class CArray;
    template <typename T>
    friend class CArrayIterator;
private:
    CArrayNode()  // 생성자.
    {
        m_pNext = nullptr;  // nullptr로 초기화.
        m_pPrev = nullptr;  // nullptr로 초기화.
    }
    ~CArrayNode()  // 소멸자.
    {
    }
private:
    T m_Data;
    CArrayNode<T>* m_pNext;
    CArrayNode<T>* m_pPrev;
};

template <typename T>
class CArrayIterator
{
    template <typename T>
    friend class CArray;
public:
    CArrayIterator()
    {
        m_pNode = nullptr;  // nullptr로 초기화.
    }
    ~CArrayIterator()
    {
    }
private:
    CArrayNode<T>* m_pNode;
    CArrayNode<T>* m_pBegin;
    CArrayNode<T>* m_pEnd;
public:
    bool operator == (const CArrayIterator<T>& iter) const
    {
        return m_pNode == iter.m_pNode;
    }

    bool operator != (const CArrayIterator<T>& iter) const
    {
        return m_pNode != iter.m_pNode;
    }

    void operator ++ ()
    {
        m_pNode = m_pNode->m_pNext;
    }

    void operator ++ (int)
    {
        m_pNode = m_pNode->m_pNext;
    }

    void operator -- ()
    {
        m_pNode = m_pNode->m_pPrev;
    }

    void operator -- (int)
    {
        m_pNode = m_pNode->m_pPrev;
    }

    CArrayIterator<T> operator + (int iSize)
    {
        CArrayIterator<T> iter;

        iter.m_pNode = m_pNode;
        iter.m_pBegin = m_pBegin;
        iter.m_pEnd = m_pEnd;
    
        CArrayNode<T>* pLast = m_pEnd->m_pPrev;

        assert(!(pLast + 2 <= m_pNode + iSize));  // 메모리 주소가 잘못되었을 경우 경고창을 띄우고 종료시킴.

        if (pLast + 1 == m_pNode + iSize)
            iter.m_pNode = m_pEnd;
        else
            iter.m_pNode += iSize;

        return iter;
    }

    CArrayIterator<T> operator - (int iSize)
    {
        CArrayIterator<T> iter;
        iter.m_pNode = m_pNode;
        iter.m_pBegin = m_pBegin;
        iter.m_pEnd = m_pEnd;

        CArrayNode<T>* pFirst = m_pBegin->m_pNext;

        assert(!(pFirst - 2 >= m_pNode - iSize));  // 메모리 주소가 잘못되었을 경우 경고창을 띄우고 종료시킴.

        if (pFirst - 1 == m_pNode - iSize)
            iter.m_pNode = m_pBegin;
        else
            iter.m_pNode -= iSize;

        return iter;
    }

    void operator += (int iSize)
    {
        CArrayNode<T>* pLast = m_pEnd->m_pPrev;

        assert(!(pLast + 2 <= m_pNode + iSize));

        if (pLast + 1 == m_pNode + iSize)
            m_pNode = m_pEnd;
        else
            m_pNode += iSize;
    }

    void operator -= (int iSize)
    {
        CArrayNode<T>* pFirst = m_pBegin->m_pNext;
    
        assert(!(pFirst - 2 >= m_pNode - iSize));

        if (pFirst - 1 == m_pNode - iSize)
            m_pNode = m_pBegin;
        else
            m_pNode -= iSize;
    }

    T& operator * () const
    {
        return m_pNode->m_Data;
    }
};

template <typename T>
class CArray
{
public:
    CArray()  // 생성자.
    {
        m_iSize = 0;
        m_iCapacity = 4;

        m_pArray = new Node[m_iCapacity];

        m_pBegin = new Node;
        m_pEnd = new Node;

        m_pBegin->m_pNext = m_pEnd;
        m_pEnd->m_pPrev = m_pBegin;
    }
    ~CArray()  // 소멸자.
    {
        delete[] m_pArray;
        delete m_pBegin;
        delete m_pEnd;
    }
private:
    typedef CArrayNode<T> Node;
    typedef CArrayNode<T>* PNode;
public:
    typedef CArrayIterator<T> iterator;
private:
    PNode m_pArray;
    PNode m_pBegin;
    PNode m_pEnd;
    int m_iSize;  // 실제 추가된 개수.
    int m_iCapacity; // 할당된 전체 배열의 개수.

public:
    // 배열의 공간을 늘려줌.
    void resize(int iCapacity)
    {
        m_iCapacity = iCapacity;

        PNode pArray = new Node[m_iCapacity];  // 새로 배열을 할당.

        // 기존 배열에 있던 내용들을 새로 할당한 배열로 옮김.
        memcpy(pArray, m_pArray, sizeof(Node) * m_iSize);

        delete[] m_pArray;  // 기존 배열을 지움.

        m_pArray = pArray;  // 기존 배열을 새로운 배열로 바꿈.

        // begin과 배열을 연결해 줌.
        m_pBegin->m_pNext = m_pArray;
        m_pArray->m_pPrev = m_pBegin;

        // 노드를 연결해 줌. 
        for (int i = 0; i < m_iSize - 1; ++i)
        {
            m_pArray[i].m_pNext = &m_pArray[i + 1];
            m_pArray[i + 1].m_pPrev = &m_pArray[i];
        }

        // end와 배열을 연결해 줌.
        m_pArray[m_iSize - 1].m_pNext = m_pEnd;
        m_pEnd->m_pPrev = &m_pArray[m_iSize - 1];
    }

    // 추가.
    void push_back(const T& data)
    {
        // 배열의 공간이 꽉 찼을 경우 공간을 늘려줌.
        if (m_iSize == m_iCapacity)
            resize(m_iCapacity * 2);

        m_pArray[m_iSize].m_Data = data;  // 추가할 노드에 데이터를 넣음.

        PNode pPrev = m_pEnd->m_pPrev;  // 마지막 노드의 previous를 얻음.

        pPrev->m_pNext = &m_pArray[m_iSize];  // pPrev의 next에 추가할 노드의 주소를 넘김.
        m_pArray[m_iSize].m_pPrev = pPrev;  // 추가할 노드의 previous에 마지막 노드의 previous를 넣음.

        m_pArray[m_iSize].m_pNext = m_pEnd;  // 추가할 노드의 next에 end를 넣음.
        m_pEnd->m_pPrev = &m_pArray[m_iSize];  // end의 previous에 추가한 노드의 주소를 넘김.

        ++m_iSize;
    }

    // 지우기.
    void pop_back()
    {
        if (empty())
        {
            assert(false);  // 거짓(false)일 경우 경고창을 띄우고 종료 시킴.
        }

        PNode pPrev = m_pArray[m_iSize - 1].m_pPrev;  // 지울 노드를 얻어옴.

        --m_iSize;

        // pPrev와 End 연결.
        pPrev->m_pNext = m_pEnd;
        m_pEnd->m_pPrev = pPrev;
    }

    int size() const
    {
        return m_iSize;
    }

    int capacity() const
    {
        return m_iCapacity;
    }

    bool empty() const
    {
        return m_iSize == 0;
    }

    // 전체 지우기.
    void clear()
    {
        m_iSize = 0;  // 0으로 초기화해주면 0번 인덱스부터 새로 채움.

        // begin과 end 연결.
        m_pBegin->m_pNext = m_pEnd;
        m_pEnd->m_pPrev = m_pBegin;
    }

    T& operator [] (int idx)
    {
        assert(!(idx < 0 || idx >= m_iSize)); // 인덱스의 범위를 벗어났을 경우 경고창을 띄우고 종료시킴.

        return m_pArray[idx].m_Data;
    }

    iterator begin() const
    {
        iterator iter;

        iter.m_pBegin = m_pBegin;
        iter.m_pEnd = m_pEnd;
        iter.m_pNode = m_pBegin->m_pNext;

        return iter;
    }

    iterator end() const
    {
        iterator iter;

        iter.m_pBegin = m_pBegin;
        iter.m_pEnd = m_pEnd;
        iter.m_pNode = m_pEnd;

        return iter;
    }

    iterator erase(const iterator& iter)
    {
        if (iter.m_pNode == m_pEnd)
            return end();

        // 인덱스를 구함.
        // ((가지고 있는 주소) - (시작 주소)) / (배열 1칸의 크기)을 하면 인덱스가 나옴.
        int iIndex = ((int)iter.m_pNode - (int)m_pArray) / sizeof(Node);

        // 뒤의 데이터를 앞으로 가져옴.
        for (int i = iIndex; i < m_iSize - 1; ++i)
        {
            m_pArray[i].m_Data = m_pArray[i + 1].m_Data;
        }

        --m_iSize;

        // m_pArray의 마지막과 end 연결.
        m_pArray[m_iSize - 1].m_pNext = m_pEnd;
        m_pEnd->m_pPrev = &m_pArray[m_iSize - 1];

        return iter;
    }

    // 범위 삭제.
    iterator erase(const iterator& first, const iterator& second)
    {
        iterator iterStart = first;
        iterator iterEnd = second;

        if (iterStart.m_pNode == m_pBegin)
            iterStart.m_pNode = m_pBegin->m_pNext;
            
        if (iterEnd.m_pNode == m_pEnd)
            --iterEnd;

        PNode pPrev = iterStart.m_pNode->m_pPrev;
        PNode pNext = iterEnd.m_pNode;

        int iStartIndex = ((int)iterStart.m_pNode - (int)m_pArray) / sizeof(Node);  // 범위 시작 인덱스.
        int iEndIndex = ((int)iterEnd.m_pNode - (int)m_pArray) / sizeof(Node);  // 범위 끝 인덱스.

        // 뒤의 데이터를 앞으로 가져옴.
        int iCount = m_iSize - iEndIndex - 1;

        for (int i = 0; i < iCount; ++i)
        {
            m_pArray[i + iStartIndex].m_Data = m_pArray[iEndIndex + i + 1].m_Data;  // 범위 시작 인덱스에 범위 끝 인덱스의 다음 인덱스를 차례로 넣어줌.
        }

        int iDeleteCount = iEndIndex - iStartIndex + 1;

        m_iSize -= iDeleteCount;

        m_pArray[m_iSize - 1].m_pNext = m_pEnd;
        m_pEnd->m_pPrev = &m_pArray[m_iSize - 1];

        iterator iter;

        iter.m_pBegin = m_pBegin;
        iter.m_pEnd = m_pEnd;
        iter.m_pNode = m_pArray + (m_iSize - 1);

        return iter;
    }

    // 정렬.
    void Sort(bool (*pFunc)(const T&, const T&))
    {
        for (int i = 0; i < m_iSize - 1; ++i)
        {
            for (int j = i + 1; j < m_iSize; ++j)
            {
                if (pFunc(m_pArray[i].m_Data, m_pArray[j].m_Data))
                {
                    T Temp = m_pArray[i].m_Data;
                    m_pArray[i].m_Data = m_pArray[j].m_Data;
                    m_pArray[j].m_Data = Temp;
                }
            }
        }
    }
};

 

main.cpp

#include <iostream>
#include <time.h>
#include "Array.h"

bool SortInt(const int& iSrc, const int& iDest)
{
    return iSrc < iDest;
}

int main()
{
    // [ memset ]
    // : 메모리를 원하는 값으로 채워줄 때 사용.
    // 1번 인자에 값을 채워줄 메모리의 시작 주소를 지정.
    // 2번 인자에 채워줄 값을 지정.
    // 3번 인자에 값을 채워줄 바이트 크기를 지정.
    // 메모리를 채울 때 1번 인자의 주소부터 3번 인자의 크기만큼을 채우게 되는데 2번 인자에 들어간 값으로 1바이트 단위로 채워줌.
    // int iArray[10] = {};
	
    //memset(iArray, 1, sizeof(int) * 10);

    //std::cout << iArray[0] << std::endl;

    CArray<int> arrInt;

    for (int i = 0; i < 100; ++i)
    {
        arrInt.push_back(i);  // 0 1 2 3 4 ... 99
    }

    for (int i = 0; i < arrInt.size(); ++i)
    {
        std::cout << arrInt[i] << " ";  // 0 1 2 3 4 ... 99 출력.

        if (i % 10 == 0 && i != 0)
            std::cout << std::endl;
    }

    CArray<int>::iterator iter = arrInt.begin();
    CArray<int>::iterator iterEnd = arrInt.end();

    int i = 0;
    std::cout << std::endl << std::endl;
    for (; iter != iterEnd; ++iter)
    {
        std::cout << *iter << " ";  // 0 1 2 3 4 ... 99 출력.

        i++;
        if (i % 10 == 0 && i != 0)
            std::cout << std::endl;
    }

    iter = arrInt.begin() + 30;  // 0 + 30 >> 30

    std::cout << std::endl << *iter << std::endl;  // 30

    iter = arrInt.erase(iter);

    std::cout << std::endl << "erase Next : " << *iter << std::endl;  // 31

    std::cout << std::endl;
    for (int i = 0; i < arrInt.size(); ++i)
    {
        std::cout << arrInt[i] << " ";  // 0 1 2 3 ... 29 31 32 ... 99 출력.

        if (i % 10 == 0 && i != 0)
            std::cout << std::endl;
    }

    iter = arrInt.begin() + 10;  // 10
    iterEnd = arrInt.begin() + 50;  // 50

    iter = arrInt.erase(iter, iterEnd);

    std::cout << std::endl << std::endl << "erase Next : " << *iter << std::endl;  // 51

    std::cout << std::endl;
    for (int i = 0; i < arrInt.size(); ++i)
    {
        std::cout << arrInt[i] << " ";  // 0 1 2 3 ... 52 53 54 ... 99 출력.

        if (i % 10 == 0 && i != 0)
            std::cout << std::endl;
    }

    std::cout << std::endl << std::endl << "================= 정렬 ================" << std::endl;

    arrInt.clear();

    srand((unsigned int)time(0));
    rand;

    for (int i = 0;i < 20; ++i)
    {
        arrInt.push_back(rand());
    }

    std::cout << std::endl;
    for (int i = 0; i < 20; ++i)
    {
        std::cout << arrInt[i] << "\t";

        if ((i + 1) % 5 == 0)
            std::cout << std::endl;
    }

    arrInt.Sort(SortInt);

    std::cout << std::endl << std::endl;
    for (int i = 0; i < arrInt.size(); ++i)
    {
        std::cout << arrInt[i] << "\t";  

        if ((i + 1) % 5 == 0)
            std::cout << std::endl;
    }

    std::cout << std::endl;

    return 0;
}

[ 결과 ]

0 1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99

0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49
50 51 52 53 54 55 56 57 58 59
60 61 62 63 64 65 66 67 68 69
70 71 72 73 74 75 76 77 78 79
80 81 82 83 84 85 86 87 88 89
90 91 92 93 94 95 96 97 98 99

30

erase Next : 31

0 1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 31
32 33 34 35 36 37 38 39 40 41
42 43 44 45 46 47 48 49 50 51
52 53 54 55 56 57 58 59 60 61
62 63 64 65 66 67 68 69 70 71
72 73 74 75 76 77 78 79 80 81
82 83 84 85 86 87 88 89 90 91
92 93 94 95 96 97 98 99

erase Next : 99

0 1 2 3 4 5 6 7 8 9 52
53 54 55 56 57 58 59 60 61 62
63 64 65 66 67 68 69 70 71 72
73 74 75 76 77 78 79 80 81 82
83 84 85 86 87 88 89 90 91 92
93 94 95 96 97 98 99

================= 정렬 ================
18466   3841    13373   8051    13251
236     5974    17883   25266   23021
30250   6683    2299    7728    9027
18277   31900   1292    3248    1885

31900   30250   25266   23021   18466
18277   17883   13373   13251   9027
8051    7728    6683    5974    3841
3248    2299    1885    1292    236

 

[ 설명 ]