배열 VS 동적배열 VS 연결리스트

C++컨테이너(데이터 저장 객체) 기초

임의 접근(Random Access) : 배열처럼 인덱스 넘버로 메모리를 한번에 접근하는 것을 말한다.

 

반복자(Iterator) : 컨테이너의 원소들을 가리키는 포인터 기능, 모든 컨테이너에서 Iterator를 통해 접근 가능하다.

Iterator는 포인터와 자신이 속한 컨테이너 정보를 표시하는 Myproxy로 이루어져 있어 일반 포인터처럼 v.erase(iterator)할 경우 프록시 정보가 없어져 다음 데이터를 가리키지 못하는 것에 주의해야 한다.

 

시퀀스 컨테이너(Sequence Container) : 데이터가 삽입 순서대로 나열되는 형태

연관 컨테이너(Associate Container) : key-value 처럼 관련있는 데이터를 하나의 쌍으로 저장하는 형태

 

 

배열(Array)

int arr[10];     // 고정된 메모리 공간 할당
arr[0] = 100;    // 0번 인덱스 임의 접근
arr[1] = 200;    // 1번 인덱스 임의 접근

- 사용할 메모리 크기를 고정해서 사용

- 메모리는 연속적으로 할당 받아서 사용

 

장점 : 연속된 메모리 공간으로 임의 접근(인덱스 넘버로 메모리 접근)가능

단점 : 할당된 메모리 추가나 축소 불가능

 

 

동적 배열(Vector, Dynamic Array)

for (int i = 0; i < 100; i++)
{
    v.push_back(i);
    cout << v.size() << " " << v.capacity() << endl;
}

v.clear();

벡터의 길이(v.size)와 여유공간(v.capacity)

- 사용할 메모리 크기를 유동적으로 변경 가능

- 연속된 메모리 공간 할당

 

*메모리 할당 정책

 첫 할당시 원본의 1.5~2배에 해당하는 메모리 공간을 여유를 두고 할당하여 혹시 모를 메모리를 더 증설해야 하는 상황을 줄였다. 증설을 위해 여유 공간을 1.5배를 두기 때문에 벡터의 크기가 커지면 커질 수록 증가하여 새로운 메모리 공간으로의 증설 횟수는 점점 적어지게 된다.

 1 * 1.5 = 1.5

 100 * 1.5 = 150

 여유분(Capacity)까지 꽉 찼다면, 새로운 메모리 공간을 증설하고 증설된 메모리로 원본을 옮긴다.

원본이 저장되어 있던 메모리는 지운다. vector의 메모리를 전부 할당 해제(clear)해도 여유공간(capacity)은 유지한다.

 

장점 : 유동적인 메모리 할당

단점 : 중간 삽입/삭제

 

 

연결리스트(List)

- 연속되지 않은 메모리를 사용

1번 데이터의 주소 -> 1

2번 데이터의 주소->5

3번 데이터의 주소->22

...

- 배열은 중간 데이터 추가하려면 추가 지점 뒤의 데이터를 한 칸씩 다 미루어야 함, 연결리스트는 각 메모리를 포인터로 연결해주기 때문에 삽입/삭제를 배열보다 효율적으로 할 수 있음

- vector보다 삽입/삭제는 효율적이지만 삽입/삭제를 하기위해 위치를 찾는 과정이 vector보다 느림

- 단일/이중/원형 리스트 있음

 

장점 : 중간 메모리 삽입/삭제 하는 부분에서 이점이 있음

단점 : 삭제할 메모리를 바로 접근하는 것이 불가능, 반복자를 통해 차례로 접근해야 함

 

 

< 구현 >

동적 배열

template<typename T>
class Vector
{
public:
    Vector() {}
    ~Vector()
    {
        if (_data)
            delete[] _data;
    }
    
    void push_back(int value)
    {
        // 용량이 꽉 차있다면 메모리 증설
        if (_size == _capacity)
        {
            int newCapacity = static_cast<int>(_capacity * 1.5);
            if (newCapacity == _capacity)
                newCapacity++;
            
            reserve(newCapacity);
        }
        
        // 공간 여유롭다면 데이터 삽입
        _data[_size] = value;
        
        // 다음 데이터 삽입을 위함
        _size++;
    }
    
    // 메모리 증설
    void reserve(int capacity)
    {
        // capacity 늘릴 필요 없는 상황이라면 증설 취소
        if (_capacity >= capacity)
            return;
        
        _capacity = capacity;
        
        // 더 큰 용량의 메모리 공간 생성
        T* newData = new T[_capacity];
        
        // 데이터 복사
        for (int i = 0; i < _size; i++)
            newData[i] = _data[i];
        
        // 기존의 메모리 해제
        delete[] _data;
        
        // 포인터 갱신
        _data = newData;
    }
    
    void clear()
    {
        // 데이터 없어도 capacity는 유지해야함
        if (_data)
        {
            delete[] _data;
            _data = new T[_capacity];
        }
        
        _size = 0;
    }

private:
    T* _data = nullptr;   // 배열을 가리키는 포인터
    int _size = 0;        // 메모리에 차 있는 크기
    int _capacity = 0;    // 총 메모리 크기
}