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

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의 크기를 충분히 확보한 상태에서 사용하는 것이 유리하다.