🧠 CS/자료구조

[자료구조] C++ Container Library : Sequential Containers - vector

청월누리 2025. 4. 26. 12:50

C++ 표준 라이브러리(STL)의 일부인 컨테이너 라이브러리 중 순차 컨테이너(Sequential Containers)에 해당하는 std::vector에 대해 정리한 글입니다.


📚 순차 컨테이너 (Sequential Container)

📖 순차 컨테이너란?

  • 순서가 있는 데이터 집합을 관리하는 컨테이너
  • "순서대로" 저장하고, 저장된 순서에 따라 탐색, 수정, 삽입, 삭제를 할 수 있음
  • 내부적으로 배열이나 연결 리스트(Linked List)를 기반으로 동작
구현이 단순하기 때문에 가볍고 빠르다는 특징이 있다. 저장할 데이터가 정렬 상태를 유지할 필요가 없을 때 사용하기 적합하다.

📌 대표 컨테이너

  • std::vector : 가변 크기 배열 | 동적 배열
  • std::deque : 양쪽 삽입 및 삭제가 빠름 | 블록 배열 (복합 구조)
  • std::list : 이중 연결 리스트 | 노드 기반 이중 링크
  • std::forward_list : 단방향 연결 리스트 (메모리 절약) | 노드 기반 단방향 링크
  • std::array : 고정 크기 배열 | 정적 배열 (컴파일 타임 크기 고정)

📚 std::vector

📖 std::vector

  • 가변 크기 동적 배열
  • 기본적으로 배열처럼 연속적인 메모리 공간을 사용
  • 배열과 다르게 크기를 자동으로 조절할 수 있다.
#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> v = {1, 2, 3};

    v.push_back(4);  // 끝에 4 추가

    for (int i : v) {
        cout << i << " ";  // 1 2 3 4
    }
    
    return 0;
}

📖 std::vector의 내부 동작 구조

  • vector는 동적 메모리를 사용해서 연속된 공간을 확보
  • 새 원소를 추가할 때, 공간이 부족하면 더 큰 배열을 새로 할당하고 복사 ➡️ 일반적으로 2배 크기로 늘림 (implementation마다 다를 수 있음)
  • push_back()을 반복하면 평균적으로 $ O(1) $ 시간이지만, 크기 확장 시 $ O(N) $ 시간이 필요
implementation (표준 라이브러리 구현체)
➡️
C++ 표준(STL)은 인터페이스(기준)만 정해져 있고, 실제로 std::vector, std::list 등과 같은 자료구조를 구현하는 건 각 컴파일러나 라이브러리 제작자이다. 따라서 implementation(표준 라이브러리 구현체)은 일반적으로 컴파일러가 사용하는 표준 라이브러리 코드를 의미하며, GNU libstdc++, LLVM libc++, MSVC STL 등이 여기에 해당한다.

📌 std::vector 내부 구조

배열의 내부 구조

  • vector는 내부적으로 3개의 포인터로 동작
    • 시작 포인터 (start) : vector의 첫 번쨰 원소를 가리키는 포인터 (vect.begin()에 해당)
    • 다음 데이터가 삽입될 위치 포인터 (finish) : vector의 마지막 원소 다음을 가리키는 포인터 (vect.end()에 해당)
    • 배열의 마지막 포인터 (end_of_storage) : 할당된 메모리 공간의 끝을 가리키는 포인터
  • push_back() 함수가 동작하면, finish 위치에 새로운 원소가 추가되고, finish가 가리키는 포인터가 한칸 이동
    • 만약, finish == end_of_storage ➡️ 메모리 재할당

📖 std::vector의 시간복잡도

  • push_back() : 평균 $ O(1) $ / 최악 $ O(N) $
  • pop_back() : $ O(1) $
  • operator[], at() 접근 : $ O(1) $
  • 임의 삽입 및 삭제 (insert(), erase()) : $ O(N) $ (이동 필요)
vector에서 일반적으로 새로운 원소를 맨 끝에 삽입하거나 맨 끝의 원소를 삭제하는 경우, 매우 빠르게 동작한다. 하지만 새로운 원소를 중간에 삽입하거나 중간에 있는 원소를 삭제하는 경우, 원소들의 이동이 필요(연속적인 메모리 공간에 배치되기 떄문)하기 때문에 느리다.

📖 vector의 주요 함수

  • push_back(val) : 끝에 원소(val) 추가
  • pop_back() : 끝 원소 제거
  • size() : vector에 저장된 원소 개수 반환
  • capacity() : vector의 크기 반환
  • resize(n) : vector의 크기를 n으로 조정 (기존 데이터는 살리고, 크기만 변경)
  • assign(n, val) : vector의 크기를 n으로 조정하고, 모든 원소를 val로 설정 (기존 데이터가 삭제되고, 주어진 값으로 새로 구성)
  • clear() : 모든 원소 제거 (원소만 삭제되고, 메모리는 그대로 유지됨)
  • insert(pos, val) : 해당 인덱스(pos)에 원소(val) 삽입
  • erase(pos) : 해당 인덱스(pos)의 원소 제거
capacity()size()의 차이
capacity() : vector가 현재 확보해놓은 전체 크기 (end_of_storage - start)
size() : vector에 들어있는 원소 개수 (finish - start)
➡️ capacity()size()가 반환하는 값이 같을 수도 있고, 다를 수도 있다.

📖 vector 사용 시 주의할 점

  • 중간에 삽입 혹은 삭제가 많은 경우, std::vector 사용은 적합하지 않음 ➡️ std::list 추천
  • vector는 항상 메모리 연속성을 보장 ➡️ 메모리 공간이 부족해져 재할당(reallocation)이 일어나는 경우, 새롭게 메모리를 할당하기 떄문에 기존 원소들의 메모리 주소(포인터)가 모두 바뀜
  • 포인터 혹은 참조가 무효화될 수 있음 ➡️ capacity가 변하는 순간 포인터 혹은 참조가 깨짐

⭐ 알고리즘 문제 적용 시 팁

vector는 일반적으로 원소를 삽입하거나 삭제할 때 상수 시간복잡도를 가지지만, 할당된 공간이 모두 차면 재할당이 발생하며 많은 시간이 소요된다. 따라서, 알고리즘 문제를 풀 때 vector의 크기를 충분히 확보한 상태에서 사용하는 것이 유리하다.