[자료구조] 동적 배열 특징

동적 배열 특징

배열의 특징

* 배열이라고 하면 기본적으로 생각하는 특징들이 있다.

 

* 인덱스를 사용해 요소에 접근한다.

 

* 메모리는 빈틈없이 이어져 있는 하나의 덩어리다.

 

* 데이터의 순서를 중요하게 생각하기 때문에 중간 삽입이나 삭제 시 비용이 크다.

  (순서유지를 위해 한 칸씩 밀어야 하기 때문에) 

 

* 유효한 데이터 사이에 쓰레기 값은 없다.

  (배열[10]일때 데이터를 5개 넣는다면 0~4까지 넣는다. )

  (1, 3, 6, 7, 8처럼 제멋대로 넣지 않는다.)

 

 

동적 배열

* 동적 배열은 너무나 자주 사용하기 때문에 대부분의 언어에서 공식 라이브러리로 지원한다.

 

* 위에 특징은 유지하며, 힙 메모리에 만들면 그게 동적 배열이다.

 

 

동적 배열 특징

* 힙 메모리에 할당하는 게 특징이다.

 

* 운영체제를 거치는 동적 할당이 매우 느리기 때문에 한번 할당하면 해제하지 않는다는 마인드로 생성해야 한다.

 

* 하지만 배열의 크기 상승은 언제나 있으며, 이때 정적 배열과 비교해 비용이 크다.

 

* 해결책으로 배열의 크기를 넉넉하게 잡으면 된다.

  멍청한 방식이 아니라 C++ STL vector의 경우, 크기 상승 시 필요한 크기보다 1.5배를 잡아버린다.  

  (크기 지정이 없을 시) 

 

 

C++ STL vector의 배열 크기 상승

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int lastCapacity = 0;
    vector<int> v;

    cout << "배열의 크기 상승" << endl;

    for (int i = 0; i < 94; i++) {
        v.push_back(i);
        if (lastCapacity != v.capacity()) {
            cout << endl;
            lastCapacity = v.capacity();
        }
        cout << v.capacity() << " ";
    }

    v.clear();
    cout << "\n\nclear 후 capacity 크기 : " << v.capacity() << endl;
}

* 동적 배열의 크기를 1로 시작해 

  크기 지정 없이 데이터를 계속 넣었다.

* 배열의 크기가 제멋대로 증가하는데 

  1.5배 크기로 여유를 두고 증가하는 규칙을 볼 수 있다.

 

 

결론

* 동적 배열은 동적 할당이 필요하기 때문에

  할당을 최대한 적게 하는 게 중요하다.

* 해결책으로 크기를 넉넉하게 잡자~

 

 

 

 

 

귀여운 그림은 낡은 창고님이 그리셨습니다.