C++ 벡터 컨테이너 (std::vector)

std::vector는 C++ 표준 라이브러리가 제공하는 동적 배열(Dynamic Array) 컨테이너로, 원소를 힙(Heap)의 연속된 메모리에 저장하면서 크기가 자동으로 늘어난다. 인덱스 접근이 O(1)이고 끝에 추가하는 push_back이 분할 상환(Amortized) O(1)이라는 성능 특성을 가지며, 크기(size)와 용량(capacity)의 구분, 재할당(Reallocation)과 반복자 무효화(Iterator Invalidation)를 이해하는 것이 활용의 핵심이다.

내부 구조: size와 capacity

vector는 개념적으로 세 가지 정보를 가진다. 힙에 할당한 배열의 시작 주소, 현재 담긴 원소 개수인 size, 그리고 재할당 없이 담을 수 있는 최대 개수인 capacity다. size가 capacity에 도달한 상태에서 push_back을 호출하면, 더 큰 새 배열을 할당하고 기존 원소를 모두 옮긴 뒤 옛 배열을 해제하는 재할당이 일어난다. 이때 성장 배율은 구현마다 다르지만 보통 1.5배나 2배씩 늘린다. 매번 1칸씩 늘리면 추가마다 전체 복사가 필요해 O(n)이 되지만, 배수로 늘리면 재할당 비용이 여러 번의 추가에 분산되어 push_back의 평균 비용이 O(1)이 된다. 이것이 분할 상환 분석의 대표 사례다.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v;
    for (int i = 0; i < 10; i++) {
        v.push_back(i);
        std::cout << v.size() << " / " << v.capacity() << '\n';
    }
    /* size는 1씩 늘지만 capacity는 1, 2, 4, 8, 16처럼 배수로 는다 */
    return 0;
}

최종 원소 개수를 미리 안다면 reserve(n)으로 용량을 확보해 재할당과 복사를 아예 없앨 수 있다. resize(n)은 용량이 아니라 size 자체를 바꿔 원소를 실제로 만들거나 지운다는 점에서 reserve와 다르다. 원소를 지워도 capacity는 줄지 않으므로, 메모리를 돌려주고 싶으면 shrink_to_fit을 호출하거나 빈 vector와 swap하는 관용구를 쓴다.

주요 연산과 시간 복잡도

연산	복잡도	비고
인덱스 접근 v[i], at(i)	O(1)	at은 범위 검사 후 예외 발생
push_back, pop_back	분할 상환 O(1)	재할당 시에만 O(n)
중간 insert, erase	O(n)	뒤쪽 원소를 모두 이동
탐색(정렬 안 된 상태)	O(n)	정렬 후 이분 탐색은 O(log n)

연속 메모리라는 특성 덕분에 vector는 캐시 지역성(Cache Locality)이 뛰어나다. 순회할 때 인접 원소가 이미 캐시에 올라와 있으므로, 노드가 힙에 흩어져 있는 std::list보다 실제 순회 속도가 훨씬 빠르다. 중간 삽입과 삭제가 이론상 O(1)인 list가 실측에서는 vector에 지는 경우가 많은 이유이기도 하다. 이런 이유로 모던 C++(Modern C++) 진영에서는 특별한 근거가 없는 한 기본 컨테이너로 vector를 쓰라고 권장한다.

std::vector<int> v = {1, 2, 3, 4, 5, 6};
for (auto it = v.begin(); it != v.end(); ) {
    if (*it % 2 == 0) {
        it = v.erase(it);   /* 지운 다음 위치를 돌려받는다 */
    } else {
        ++it;
    }
}
/* C++20부터는 std::erase_if(v, 조건)로 한 줄에 처리할 수 있다 */