std::vector

vector의 본질

핵심 정리

• vector는 연속 메모리(Contiguous Memory)에 요소를 저장합니다.
• 그래서 배열처럼 인덱스 접근(v[i])이 빠르고, 캐시 친화적입니다.
• STL에서 가장 자주 쓰이는 기본 컨테이너입니다.

왜 기본 선택인가?

• 순회 성능이 좋고 사용법이 단순합니다.
• 끝 삽입(push_back)이 평균적으로 빠릅니다.
• 대부분의 게임/서버 로직에서 "순차 처리 + 빠른 조회" 요구에 잘 맞습니다.

---

size / capacity / 재할당

용어

항목	의미
size()	실제 원소 개수
capacity()	현재 확보된 버퍼 크기

동작 예시

vector<int> v{1, 2, 3, 4, 5};
cout << v.size() << ", " << v.capacity() << '\n'; // 5, (구현체마다 다름)

v.reserve(10);
cout << v.size() << ", " << v.capacity() << '\n'; // 5, 10 이상

v.push_back(6);
cout << v.size() << ", " << v.capacity() << '\n'; // 6, 10 이상

reserve vs resize vs shrink_to_fit

함수	size 변화	capacity 변화	핵심 용도
reserve(n)	그대로	최소 n까지 증가	재할당 횟수 줄이기
resize(n)	n으로 변경	필요 시 증가	원소 개수 자체 변경
shrink_to_fit()	그대로	줄이기 요청(비강제)	여유 메모리 반환 요청

vector<int> v{1, 2, 3};
v.reserve(100);   // size=3, capacity>=100
v.resize(5, 0);   // size=5 (뒤에 0,0 추가)
v.clear();        // size=0, capacity는 보통 유지
v.shrink_to_fit(); // capacity 축소 "요청"

---

시간 복잡도와 성능 감각

연산	복잡도	비고
push_back	평균 O(1)	재할당 시 한 번 O(N) 가능
pop_back	O(1)	끝 원소 제거
v[i], at(i)	O(1)	at은 범위 검사 포함
중간 삽입/삭제	O(N)	뒤 원소 이동 필요
전체 순회	O(N)	캐시 친화적이라 실제 체감 좋음

push_front가 없는 이유

• 앞 삽입은 모든 원소를 밀어야 해서 O(N)입니다.
• 이 작업이 주 요구라면 deque나 list를 고려합니다.

emplace_back vs push_back

• push_back(obj)는 객체를 넣습니다.
• emplace_back(args...)는 컨테이너 내부에서 직접 생성해 불필요한 복사/이동을 줄일 수 있습니다.

---

복사 / 참조 / 이동

복사는 깊은 복사

vector<int> a{1, 2, 3};
vector<int> b = a;   // 깊은 복사
b[0] = 100;          // a[0]은 그대로 1

함수 인자 권장

void ReadOnly(const vector<int>& v); // 읽기 전용: const 참조
void Modify(vector<int>& v);         // 수정 필요: 참조
void Take(vector<int> v);            // 복사 비용 감수

• 큰 vector를 값으로 받으면 복사 비용이 큽니다.
• 읽기 전용은 기본적으로 const vector<T>&를 권장합니다.

이동 시맨틱

• vector는 move를 지원하므로 임시 객체 전달/반환 시 복사 비용을 줄일 수 있습니다.
• 다만 move 후 원본 상태에 의존하지 않는 습관이 필요합니다.

---

무효화(invalidation) 규칙 (중요)

vector에서 재할당이나 중간 삽입/삭제가 발생하면 포인터/참조/이터레이터가 무효화될 수 있습니다.

대표 상황:

• push_back 중 capacity 증가(재할당) 발생 -> 기존 이터레이터/포인터/참조 대부분 무효화
• erase -> 삭제 지점 이후 이터레이터 무효화

auto it = v.begin();
v.push_back(10); // 재할당이 일어나면 it 무효화 가능

• 이 규칙을 모르고 쓰면 크래시/데이터 꼬임으로 이어집니다.
• 다음 Part 7~8에서 이터레이터/erase 패턴을 더 자세히 다룹니다.

---

자주 쓰는 초기화 패턴

vector<int> a = {1, 2, 3, 4, 5}; // initializer_list
vector<int> b(5, -1);            // 크기 5, 값 -1
vector<int> c(10);               // 크기 10, 기본값(0)
vector<int> d;                   // 빈 벡터

실전 팁:

• 예상 원소 수가 크면 초반에 reserve로 capacity를 잡아 재할당을 줄이세요.

---

자주 하는 실수 + 체크 질문

자주 하는 실수

실수	문제
reserve 후 v[i] 바로 접근	size는 그대로라 범위 밖 접근
erase 후 기존 이터레이터 계속 사용	무효화로 UB/크래시
큰 벡터를 값 전달 남발	불필요한 복사 비용
clear()가 메모리까지 완전 반환된다고 오해	capacity는 보통 유지

체크 질문 (스스로 답해보기)

• 왜 vector가 기본 컨테이너로 자주 권장될까?
• reserve와 resize의 차이를 코드로 설명할 수 있는가?
• push_back이 평균 O(1)인 이유(상각 분석)를 설명할 수 있는가?
• 어떤 연산이 이터레이터를 무효화하는지 알고 있는가?

---