[C++] STL vector - size/capacity부터 iterator invalidation까지

1. STL이란?

STL (Standard Template Library)은 프로그래밍에 필요한 자료구조와 알고리즘을 템플릿 형태로 제공하는 C++ 표준 라이브러리다.

• 컨테이너 (Container): 데이터를 저장하는 자료구조 (vector, list, map 등)
• 반복자 (Iterator): 컨테이너의 원소를 순회하기 위한, 포인터와 유사한 개념의 인터페이스
• 알고리즘 (Algorithm): sort, find 등 컨테이너에 독립적으로 동작하는 함수들

---

2. 배열의 한계와 vector의 등장

C 스타일 배열은 크기가 고정이라는 한계가 있다.

const int MAX_SIZE = 10;
int arr[MAX_SIZE] = {};

이 한계를 보완한 것이 vector, 즉 동적 배열이다. vector는 크기가 가변적이라는 점만 빼면 배열과 동일하게 동작한다. 원소가 하나의 연속된 메모리 블록에 저장된다는 특징도 배열과 같다.

---

3. size와 capacity

vector를 이해하는 핵심은 size와 capacity를 구분하는 것이다.

구분 의미

size()	실제로 사용 중인 데이터의 개수
capacity()	재할당 없이 담을 수 있는 최대 개수 (여유분 포함)

vector가 내부적으로 동작하는 원리는 다음과 같다.

1. 여유분을 두고 메모리를 할당한다.
2. 여유분까지 꽉 차면 메모리를 증설(재할당)한다.
3. 기존 데이터보다 큰 새 메모리 블록을 동적 할당하고, 기존 데이터를 복사(또는 이동)한 뒤 기존 메모리를 해제한다.

capacity 관련 함수

• reserve(n): capacity만 n으로 확보한다. size는 그대로이며, 원소를 생성하지 않는다. 순수하게 메모리만 미리 확보하는 용도.
• resize(n): capacity와 함께 size도 n으로 변경된다. 새로 생기는 원소는 기본값으로 초기화(value-initialize)된다는 점이 reserve와의 결정적 차이.
• clear(): 원소를 모두 소멸시켜 size를 0으로 만든다. capacity는 변하지 않는다.

⚠️ resize로 공간을 미리 잡아두면, 이미 size에 포함된 상태이므로 push_back이 아니라 operator[]로 접근해야 한다. (push_back은 항상 size 뒤에 추가하기 때문)

reserve를 미리 해두는 이유

capacity가 변할 때마다(재할당) 기존 원소를 복사 또는 이동하는 비용이 발생한다. 최종적으로 필요한 크기를 미리 안다면 reserve로 재할당 횟수 자체를 줄여 비용을 아낄 수 있다.

증설 배수 (Growth Factor)

메모리가 꽉 찼을 때 얼마나 증설할지는 표준에 정해져 있지 않고 구현체마다 다르다.

• MSVC: 보통 1.5배
• GCC libstdc++: 보통 2배

실험 코드로 직접 확인해볼 수 있다.

vector<int> s;
for (int i = 0; i < 1001; i++) {
    s.push_back(100);
    cout << s.size() << " | " << s.capacity() << endl;
}

주의사항 정리

1. 재할당(capacity 증가)이 발생하면 기존의 iterator/pointer/reference는 전부 무효화된다.
2. 재할당 시 원소가 복사되느냐 이동되느냐는 원소 타입의 이동 생성자가 noexcept인지에 따라 갈린다. noexcept 이동 생성자가 있으면 move, 없으면 예외 안전성 때문에 copy로 처리될 수 있다.

---

4. Iterator (반복자)

Iterator는 포인터와 유사한 개념으로, 컨테이너의 원소를 가리키는 역할을 한다.

vector<int> v(10);
for (vector<int>::size_type i = 0; i < v.size(); i++)
    v[i] = i;

vector<int>::iterator itBegin = v.begin(); // v[0]을 가리킴
vector<int>::iterator itEnd = v.end();     // 마지막 원소의 "다음" 주소 (쓰레기값)

순회 방법:

// 정방향
for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
    cout << (*it) << endl;
}

// 역방향
for (vector<int>::reverse_iterator it = v.rbegin(); it != v.rend(); ++it) {
    cout << (*it) << endl;
}

포인터처럼 ++, --, += 등의 연산이 가능하지만, 어디까지나 컨테이너 내부 구현에 맞춰 동작이 정의된 별도의 타입이라는 점에서 포인터와 구분된다.

---

5. 중간 삽입/삭제 vs 처음·끝 삽입/삭제 vs 임의 접근

vector를 실무에서 쓸 때 가장 중요한 성능 특성이다.

연산 성능

임의 접근 (operator[])	O(1) — 좋음
끝에서 삽입/삭제 (push_back/pop_back)	O(1) (amortized) — 좋음
중간/처음 삽입/삭제 (insert/erase)	O(n) — 나쁨

원소가 연속된 메모리에 저장되기 때문에, 중간에 원소를 끼워 넣으려면 뒤의 원소들을 전부 한 칸씩 밀어야 한다.

[0][1][2][3][4][ ][ ]   // 인덱스 2에 5를 삽입하고 싶은 상황
[0][1][ ][2][3][4][ ]   // 2,3,4를 한 칸씩 뒤로 밀고
[0][1][5][2][3][4][ ]   // 빈 공간에 삽입

삭제도 마찬가지로, 삭제한 자리를 뒤 원소들로 당겨와 연속성을 유지해야 하므로 O(n) 비용이 든다.

vector<int>::iterator insertIt = v.insert(v.begin() + 2, 5);
vector<int>::iterator eraseIt1 = v.erase(v.begin() + 2);
vector<int>::iterator eraseIt2 = v.erase(v.begin() + 2, v.begin() + 4); // [2,4) 범위 삭제, 4는 미포함

---

6. erase 후 iterator 무효화 - 조건부 삭제 패턴

erase는 실행된 순간 해당 iterator를 무효화시킨다. 삭제 후 그 iterator를 그대로 ++ 하면 이미 유효하지 않은 iterator를 참조하게 되어 크래시로 이어진다.

// 잘못된 코드
for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
    if (*it == 3) {
        v.erase(it); // erase 후 it은 무효! 다음 루프의 ++it에서 문제 발생
    }
}

올바른 패턴은 erase의 반환값으로 iterator를 갱신하고, for문의 ++it는 제거하여 삭제하지 않은 경우에만 증가시키는 것이다.

for (vector<int>::iterator it = v.begin(); it != v.end(); /* ++it 제거 */) {
    int data = *it;
    if (data == 3) {
        it = v.erase(it); // erase가 반환하는, 삭제된 자리를 가리키는 새 iterator로 갱신
    } else {
        ++it;
    }
}

⚠️ v.clear()를 호출하면 모든 iterator가 무효화되므로, clear 이후에는 반드시 루프를 break해야 한다.