[C++] vector, deque 의 차이 - 메모리는 어떻게 관리할까?

서론

 vector에 대한 이야기는 많이 있습니다. 가장 많이 접하게 되는 컨테이너기도 하고 vector만 있으면 대부분의 상황에서 큰 문제가 없거든요. vector와 비슷한 deque는 뒤로만 넣는 vector와 다르게 push_front(), pop_front() 의 함수가 있어 앞, 뒤로 사용할 수 있다는 장점이 있는 컨테이너입니다. 뭐 이런 차이에 대해서는 누구나 알고 있는 부분이라고 생각됩니다. 그래서 오늘은 메모리 관점에서 vector와 deque는 어떻게 다른 방식을 취하는지 알아보도록 하겠습니다.

 

 

 

vector는 재할당, deque는 쪼개져 있다

 vector의 경우 메모리 내에서 연속적인 위치에 있는 방식을 취하고 있습니다. 만일 기존에 사용하던 용량이 가득찬 채로 원소를 추가적으로 삽입하면 새 메모리에 위치를 잡고 이곳으로 기존 원소를 '복사'하는 과정이 있습니다. 이로 인해서 평소 reverse를 잘 하거나 move 연산 등을 통해 복사에 대한 대비를 할 필요가 있는게 vector이죠.

 

 그런데 deque는 조금 다른 방식을 취하게 됩니다. 어떻게 보면 조금 list와도 비슷한가 싶기는 한데 일단 원소들이 메모리에 연속적으로 존재하지 않습니다. 어떤 방식이냐면 원소들은 각 블록에 있고 이 흩어진 블록들을 가리키는 포인터 블록이 있습니다.

블록 1을 향한 포인터

블록 2를 향한 포인터

블록 3을 향한 포인터

이런 컨트롤 블록이 있고

블록 1
블록 2
블록 3

이런식으로 블록이 따로 흩어져 있는 것이죠. 즉 여러 벡터들이 흩어져 있는 것과 같죠. 이로 인해서 '흩어진 벡터들을 잘 관리' 해주기만 하면 되기에 삽입, 삭제에서 벡터보다 비용이 상당히 싸게 나오게 됩니다.