[C++] Vector의 메모리 할당 방식

 

 

알고리즘 복잡도와 반복자 무효화

Vector에 원소를 추가하거나 삭제하면 공간을 확보하거나 채우기 위해 남은 원소를 적절히 이동시킨다.

따라서 원소의 추가와 삭제 연산의 복잡도는 선형 시간이다. 또한 추가나 삭제 지점을 참조하는 반복자는 그 연산이

끝난 뒤에는 사용할 수 없다. Vector의 원소가 변경된 결과에 따라 반복자를 자동으로 조정해주지 않기 때문이다.

따라서 프로그래머가 적절히 대응해야 한다. 

 

또한 Vector의 내부에서 공간 재할당이 발생하면 추가나 삭제 대상이 되는 원소를 가리키는 반복자뿐만 아니라 다른 지점에 대한 기존 반복자들도 모두 무효가 된다.

 

 

Vector의 메모리 할당 방식

Vector에 원소를 추가할 때는 메모리가 자동으로 할당된다. 앞에서 설명했듯이 Vector는 표준 C 스타일 배열처럼 원소를

연속된 메모리 공간에 저장한다. Vector에 현재 할당된 메모리 공간 바로 뒤에 새 메모리를 요청할 수 없기 때문에 Vector에

원소를 추가하다가 공간이 모자라면 더 큰 공간을 새로 할당받아서 오래 걸리기 때문에 Vector를  구현할 때  재할당 발생 

가능성을 최소화하도록 실제로 필요한 양보다 더 많이 할당받는다.

 

1. 효율성: Vector의 메모리 할당 방식은 원소의 추가 연산에 대해 분할 상환 상수 시간의 복잡도를 보장한다. 다시 말해 대다수의 추가 연산은 상수 시간에 처리되지만 간혹 재할당이 발생할 때처럼 선형 시간의 복잡도를 가질 수 있다. 효율성이 중요하다면 Vector의 재할당 방식을 직접 관리하면 된다.

 

2. 반복자 무효화: 메모리 재할당이 발생하면 Vector의 원소를 참조하던 기존의 반복자들이 모두 무효가 된다.

 

Vector는 Vector의 재할당 상태를 조회하거나 직접 제어하는 인터페이스도 제공한다. 재할당 방식을 직접 제어하고 싶지

않다면 추가 연산으로 인해 재할당이 발생하여 기존 반복자가 모두 무효가 될 수 있다는 점을 염두에 두어야 한다.

 

 

정말 반복자가 무효화 될까?

먼저 Vector에 두 개의 원소를 넣고 반복자(Iterator)를 돌렸을 때 이상 없이 돌아가는 걸 확인할 수 있다. 

이번엔 기존 반복자(Iterator)을 유지한 상태에서 Vector에 새로운 원소를 넣어서 확인해보자

 

오류가 발생하는 것을 확인할 수 있고 오류 내용은 반복자를 사용할 수 없다 이런 느낌의 오류이다.

이러한 오류가 발생하는 이유는 Vector가 메모리를 재할당 하는 과정에서 메모리의 주소 값이 바뀌기 때문이다.

가장 좋은방법은 이러한 오류가 발생하지 않도록 하는 것이라고 생각한다.

 

후기

Vector의 매모리 재할당에 대해서 간단히 정리를 해보았다. STL 컨테이너는 아는 거 같으면서도 잘 모르는 거 같은 느낌이라 컨테이너 하나하나 메커니즘을 자세히 공부해야 할 거 같다.

 

출처 및 레퍼런스

Book: 전문가를 위한C++ 17