[Vector / Array] Vector Capacity(용량)과 Memory

 

 

벡터의 Capacity와 reserve()

이번 시간에는 벡터의 Capacity(용량) 개념과 reserve() 함수의 역할, 그리고 벡터가 재할당(Reallocation)될 때 발생하는 동작에 대해 알아보겠습니다.

1. 벡터의 O(1) 삽입은 항상 보장되지 않습니다.

이전 시간에는 벡터의 마지막에 원소를 추가하거나 제거하는 연산(push_back, emplace_back, pop_back)이 평균적으로 O(1)이라고 설명했습니다.

하지만 이는 항상 O(1)이 보장되는 것은 아닙니다. 벡터의 저장 공간이 부족해지는 순간에는 새로운 메모리를 할당해야 하므로 O(N)의 시간이 발생할 수 있습니다.

 

 

 

2. 벡터가 관리하는 정보

벡터 객체는 단순히 데이터를 저장하는 것이 아니라 다음과 같은 정보를 함께 관리합니다.

• 데이터의 시작 주소(Pointer)
• 현재 원소 개수(Size)
• 확보된 메모리 크기(Capacity)

예를 들어

std::vector<int> nums;

를 생성하면

• Size는 0
• Capacity도 0

으로 시작합니다.

 

 

 

3. Size와 Capacity의 차이

벡터에 원소를 추가해 보겠습니다.

nums.push_back(1);
...
nums.push_back(5);

이 경우

• Size = 5
• Capacity = 5

가 될 수 있습니다.

여기서 원소를 하나 더 추가하면

nums.push_back(6);

결과는 다음과 같이 변할 수 있습니다.

• Size = 6
• Capacity = 10

즉,

• Size는 현재 저장된 원소의 개수
• Capacity는 벡터가 확보해 둔 메모리의 크기

를 의미합니다.

Capacity가 더 크면 새로운 원소를 추가할 때 별도의 메모리 할당 없이 바로 저장할 수 있습니다.

 

 

 

4. Capacity가 부족하면 어떻게 될까요?

Capacity가 가득 찬 상태에서 새로운 원소를 추가하면 다음 과정이 발생합니다.

1. 더 큰 메모리 공간을 새로 할당합니다.
2. 기존의 모든 원소를 새 공간으로 이동(move)하거나 복사(copy)합니다.
3. 기존 메모리를 해제합니다.
4. 새로운 원소를 추가합니다.

이 과정에서는 모든 원소를 이동해야 하므로 O(N)의 시간이 필요합니다.

대부분의 구현에서는 Capacity를 약 2배 정도 증가시켜 이러한 재할당 횟수를 줄입니다.

 

 

 

5. reserve()의 역할

재할당을 줄이기 위해 사용하는 함수가 **reserve()**입니다.

nums.reserve(100000);

이처럼 미리 충분한 메모리를 확보해 두면

• Capacity는 100000
• Size는 여전히 현재 원소 개수

가 됩니다.

이후 Capacity를 넘지 않는 범위에서는 새로운 원소를 추가해도 재할당이 발생하지 않으므로 대부분 O(1)의 성능을 유지할 수 있습니다.

다만 Capacity를 지나치게 크게 잡으면 메모리를 불필요하게 많이 사용하므로, 예상되는 최대 크기 정도만 확보하는 것이 좋습니다.

 

 

 

6. 재할당 시 발생하는 Move와 Copy

Capacity가 부족해지면 벡터 전체가 새로운 메모리 공간으로 이동합니다.

이때 C++은 가능한 경우 Move를 사용하고, Move를 사용할 수 없으면 Copy를 사용합니다.

예를 들어 Cat 객체를 저장하는 벡터에서 Capacity가 부족하면

• 새로운 메모리를 할당하고
• 기존 Cat 객체들을 모두 Move 또는 Copy하여 옮긴 뒤
• 기존 메모리를 해제합니다.

따라서 객체의 Move 생성자가 효율적이라면 재할당 비용도 줄어듭니다.

 

 

 

7. noexcept의 중요성

사용자가 Move 생성자와 Move 대입 연산자를 직접 구현했다면 noexcept를 함께 선언하는 것이 매우 중요합니다.

Cat(Cat&& other) noexcept;

Move 연산이 noexcept가 아니면

• 예외 발생 가능성을 고려하여
• 컴파일러가 Move 대신 Copy를 선택하는 경우가 있습니다.

반면 noexcept를 지정하면 벡터는 재할당 과정에서 Move를 적극적으로 사용하여 더 효율적으로 동작할 수 있습니다.

 

 

 

8. 가장 좋은 방법

벡터에 많은 데이터를 넣을 것이 예상된다면

1. reserve()로 충분한 Capacity를 미리 확보하고
2. 객체는 emplace_back()으로 생성하며
3. Move 생성자에는 noexcept를 붙이는 것

이 가장 효율적인 방법입니다.

 

 

 

정리

• 벡터는 Pointer, Size, Capacity 정보를 관리합니다.
• Size는 현재 원소 개수, Capacity는 확보된 메모리 크기입니다.
• Capacity가 부족하면 새로운 메모리를 할당하고 기존 원소를 모두 이동해야 하므로 O(N)의 비용이 발생합니다.
• reserve()를 사용하면 재할당을 줄여 대부분의 삽입 연산을 O(1)로 유지할 수 있습니다.
• 재할당 시에는 가능한 경우 Move가 사용되며, Move 생성자에 noexcept를 선언하면 성능 향상에 도움이 됩니다.
• 많은 데이터를 저장할 예정이라면 reserve()를 먼저 호출하는 습관을 들이는 것이 좋습니다.