[C++] vector 정리

1. vector의 정체

vector는 연속된 메모리를 사용하는 동적 배열(dynamic array)이다.

---

2. 핵심 특징: 연속성

vector의 모든 원소는 메모리상에 나란히 붙어 있다.

✅ 장점

• v[i] 접근 시 O(1)의 속도를 보장한다.
• Cache-friendly: 데이터가 인접해 있어 CPU 캐시 효율이 높고 순회 속도가 빠르다.

❌ 단점

• 중간에 원소를 삽입하거나 삭제할 경우, 뒤쪽 원소들을 전부 이동시켜야 한다.

---

3. size vs capacity

• size: 현재 벡터에 실제로 들어있는 원소 개수다.
• capacity: 재할당 없이 담을 수 있는 최대 개수다.

📌 capacity ≥ size는 항상 참이다.

왜 capacity가 필요한가

push_back을 할 때마다 매번 메모리를 새로 할당(realloc)하면, 기존 원소를 복사하는 비용()이 매번 발생하여 성능이 저하된다. 따라서 vector는 미래를 대비해 미리 여유 공간을 할당해 둔다.

---

4. push_back과 재할당

capacity가 가득 찬 상태에서 push_back을 호출하면 내부적으로 다음과 같은 일이 벌어진다.

1. 더 큰 메모리 공간 할당 (보통 기존의 2배).
2. 기존 원소를 전부 복사.
3. 기존 메모리 해제 및 새 원소 추가.

⏱ 비용: 📌 따라서 push_back()은 평균적으로는 O(1)이지만, 최악의 경우  O(N)이 될 수 있다.

---

5. reserve vs resize

두 함수는 목적이 다르므로 반드시 구분해서 사용해야 한다.

함수	size 변화	값 생성	목적
reserve	❌	❌	재할당 방지(메모리만 예약)
resize	⭕	⭕	원소 개수 변경 (실제 값 생성)

---

6. 안전한 접근 방법

• operator[]: 속도가 빠르지만 범위 체크를 하지 않는다. 잘못된 인덱스 접근 시 UB(Undefined Behavior)가 발생한다.
• at(): 범위를 체크하고 예외를 발생시킨다. 디버깅 단계에서 유용하다.

---

7. 삭제가 느린 이유

v.erase(v.begin() + i)를 호출하면 해당 위치 뒤의 모든 원소를 한 칸씩 앞으로 당겨야 한다.

• 비용:
• 주의: 반복문 안에서 erase를 남발하면 O(n^2)이 되어 시간 초과의 주범이 된다.

---

8. 사용 가이드

• 적합한 경우: 순차 접근이 많을 때, 끝에서만 삽입/삭제할 때, 랜덤 액세스가 필요할 때.
• 부적합한 경우: 중간 삽입/삭제가 빈번할 때, 큐(Queue) 구조가 필요할 때.

---

코딩 테스트 필수 함수 정리

🟢 1단계: 필수 핵심

• 생성: vector<int> v(n, x); (크기 을 로 초기화)
• 크기 확인: v.empty() 사용을 습관화한다. size_t(unsigned) 타입 관련 실수를 방지하고 가독성을 높여준다.
• 안전 패턴: front(), back() 접근 전에는 반드시 !v.empty()를 확인한다.

🟡 2단계: 성능 및 실수 방지

• reserve(N): 대량의 데이터를 push_back 하기 전에 미리 호출하여 재할당 비용을 제거한다.
• erase: 특정 위치 삭제는 O(n)임을 명심한다.

🟠 3단계: 유용한 패턴

• Remove-Erase Idiom: 특정 값 를 전부 제거할 때 사용한다.

v.erase(remove(v.begin(), v.end(), x), v.end());

이 패턴을 사용하면 O(n)에 깔끔하게 삭제 가능하다.

• remove : size 변화 없이 값을 앞으로 땡김 ( 뒤쪽은 쓰레기값으로)
• erase : 쓰레기 구간 삭제, 실제 size 감소
• cf) 잘못된 접근 

for (...) {
if (v[i] == x)
        v.erase(v.begin() + i);
}

 

• assign (초기화 대체)

v.assign(n, x);

= clear + resize + fill

• swap:
  • 내부 포인터만 교환 , 원소 복사 ❌ -> O(1)
  • 두 벡터를 O(1)에 교체하거나
  • 빈 벡터와 swap하여 메모리(capacity)를 즉시 해제할 때 사용한다. ( capacity까지 해제됨)
  • cf) clear() : size만 0, cpacity는 유지 

---