카테고리 없음

C++ STL - Vector

dkuen 2026. 3. 11. 17:38

STL (Standard Template Library)은 C++ 표준 라이브러리의 일부로, 컨테이너, 알고리즘, 반복자 등의 템플릿 기반 구성 요소를 포함합니다.

STL을 활용하면 다양한 자료구조와 알고리즘을 직접 구현하지 않고도, 사용할 수 있습니다.

컨테이너

컨테이너는 데이터를 담는 자료구조를 말합니다.

데이터를 담는 방식이나 제공하는 메서드에 따라 여러 가지 컨테이너를 제공합니다.

  1. 모든 컨테이너는 템플릿으로 구현되어 있으므로, 다양한 타입의 데이터를 저장할 수 있습니다.
  2. 모든 컨테이너는 메모리 관리를 내부적으로 합니다. 따라서 사용 시 메모리 해제를 직접 고려하지 않아도 됩니다.
  3. 대부분 컨테이너는 반복자를 제공합니다. 따라서 내부 구현을 몰라도 동일한 방식으로 컨테이너를 순회할 수 있습니다.

벡터(Vector)

백터는 배열과 매우 유사한 컨테이너입니다.

대표적인 특징을 알아보면 다음과 같습니다.

  1. 템플릿 클래스로 구현되어 특정 타입에 종속되지 않습니다.
  2. 삽입되는 원소 개수에 따라 내부 배열의 크기가 자동으로 조정됩니다.
  3. 임의 접근이 가능합니다. (인덱스를 통해 특정 위치에 접근)
  4. 삽입 / 삭제는 맨 뒤에 하는 게 좋습니다.
    (중간 삽입 / 삭제는 배열 복사가 필요하므로 비효율적)

벡터의 선언

백터는 타입만 명시해서 선언하는 방법이 있고, 초기값까지 같이 선언하는 경우도 있습니다.

  1. 빈 벡터를 선언하거나 특정 값으로 초기화 하는 코드입니다.
    vec1는 빈 벡터이므로 크기가 0이고, vec2는 크기는 5이며 모든 값이 10 입니다.
#include <vector>
using namespace std;

// 1. 기본 생성 및 초기화 없이 선언
vector<int> vec1;

// 2. 특정 크기와 초기값으로 벡터 선언
vector<int> vec2(5, 10); // 크기 5, 모든 원소가 10으로 초기화
  1. 초기화 리스트를 사용하여 벡터를 선언하는 코드입니다. 특정 값으로 벡터를 초기화할 때 자주 사용됩니다.
    초기화 하는 원소의 개수가 적을 때 주로 활용합니다.
#include <vector>
using namespace std;

// 3. 리스트 초기화로 벡터 선언
vector<int> vec3 = {1, 2, 3, 4, 5};
  1. 다른 벡터를 복사하거나 대입하는 방법도 있습니다. 기존에 생성된 벡터의 복사본을 만들 때 많이 사용합니다.
#include <vector>
using namespace std;

// 다른 벡터를 기반으로 복사 초기화
vector<int> vec3 = {1, 2, 3, 4, 5};
vector<int> vec4(vec3); // vec3의 복사본 생성
//vector<int> vec4 = vec3 하면 대입이 됨
  1. 2차원 배열처럼 벡터를 사용하려면, 벡터의 타입을 벡터로 하면 됩니다. 아래와 같이 하면 2차원 벡터처럼 사용할 수 있습니다.
#include <vector>
using namespace std;

// 2차원 벡터 초기화
vector<vector<int>> vec2D(3, vector<int>(4, 7)); // 3x4 행렬, 모든 원소가 7로 초기화

벡터의 동작

벡터에서 제공하는 메서드 중에 많이 사용하는 메서드에 대해 알아보겠습니다.

  1. push_back
    벡터의 맨 끝에 원소를 추가하는 메서드입니다.
    원소의 개수가 늘어남에 따라 크기는 자동으로 증가하므로, 별도의 메모리 관리를 신경 쓸 필요가 없습니다.
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> vec;
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);

    cout << "Vector after push_back: ";
    for (int num : vec) {
        cout << num << " ";
    }
    return 0;
}
// 출력: Vector after push_back: 10 20 30
  1. pop_back
    벡터의 맨 끝에 원소를 제거하는 메서드입니다.
    맨 끝 원소가 제거되면 벡터 크기가 자동으로 줄어듭니다.
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> vec = {10, 20, 30};
    vec.pop_back();  // 마지막 요소(30) 제거

    cout << "Vector after pop_back: ";
    for (int num : vec) {
        cout << num << " ";
    }
    return 0;
}
// 출력: Vector after pop_back: 10 20
  1. size
    현재 벡터의 크기(원소 개수)를 확인할 때 사용하는 메서드입니다.
    보통 벡터의 전체 원소를 대상으로 반복문을 돌릴 때 유용하게 쓰입니다.
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> vec = {10, 20, 30};
    cout << "Size of vector: " << vec.size() << endl;

    vec.push_back(40);
    cout << "Size after push_back: " << vec.size() << endl;

    vec.pop_back();
    cout << "Size after pop_back: " << vec.size() << endl;

    return 0;
}
// 출력:
// Size of vector: 3
// Size after push_back: 4
// Size after pop_back: 3
  1. erase
    특정 위치(또는 구간)의 원소를 제거하는 함수입니다.
    벡터는 내부적으로 배열을 사용하므로, 중간 원소를 삭제할 때, 많은 원소를 옮겨야 할 수 있습니다.
    따라서 시간 복잡도가 커질 수 있으므로, 자주 사용하지 않는 것이 좋습니다.
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> vec = {10, 20, 30, 40, 50};

    // 두 번째 요소 제거 (index 1)
    vec.erase(vec.begin() + 1);

    cout << "Vector after erasing second element: ";
    for (int num : vec) {
        cout << num << " ";
    }
    cout << endl;

    // 2~4 번째 요소 제거 (index 1~3)
    vec.erase(vec.begin() + 1, vec.begin() + 3);

    cout << "Vector after erasing range: ";
    for (int num : vec) {
        cout << num << " ";
    }
    return 0;
}
// 출력:
// Vector after erasing second element: 10 30 40 50
// Vector after erasing range: 10 50

 

벡터의 크기 개념

vector에는 크기 개념이 두 가지 있습니다.

  • size : 실제 들어있는 원소 개수
  • capacity : 현재 확보된 메모리 공간

예를 들면, vector<int> vec1;을 하면 size = 0, capacity = 0일 확률이 높습니다.

만약 vec1.push_back(10); 을 했을 때,

size < capacity 라면 시간복잡도는 O(1)입니다. 할당된 공간이 더 크니까 그냥 추가하면 됩니다. 하지만

size == capacity 라면 재할당이 발생합니다.

 

재할당

capacity를 2배로 늘립니다.

만약 capacity 4, size 4일 때, 다섯번째 push_back()이 들어온다면,

capacity를 2배만큼인 8로 메모리를 재할당합니다.

그리고 기존의 값을 추가하고 새 원소를 추가합니다.

마지막으로 기존 메모리를 해제하는 방식으로 작동합니다.

위와같이 복사비용이 발생하기 때문에

재할당 = O(n)의 시간복잡도를 가집니다.

 

위와 같은 상황을 예방하기 위해서는

reserve(100)를 사용하면 매개변수 값 만큼 미리 메모리를 할당해 놓습니다.

2배씩 늘리는 이유는?

만약 capacity가 부족 할 때마다 매번 1칸씩 늘리면 > O(n) * n = O(n^2)의 시간복잡도가 발생합니다.

n번인 이유는, push_back의 반복 횟수 입니다.

 

위와같은 상황인 size = 4, capacity = 4를 가지고 있는데, n번의 push_back콜이 들어온다면,

1칸씩 늘어 날 때는 매 번 재할당이 이루어져 O(n^2)인 반면

2배씩 늘리면 재할당 횟수가 log n번으로 줄어듦니다.

 

그래서 2배씩 늘어나면 push_back은 평균 O(1)의 시간복잡도를 가지고

이를 분할 상환 분석이라고 합니다.

 

분할 상환 분석은..

한 번의 연산이 아닌, 여러번의 연산이 이루어 졌을때 이루어지는 평균적으로 소요되는 시간을 분석하는것을 의미합니다.

 

위 상황과 같이 결국 push_back을 하기 위해서는 재할당이 이루어지며 O(n)이 소요되지만, 여러번의 연산 중 한 번의 연산이기 때문에 평균 O(1)이라 말합니다.

연산 시간 복잡도 왜?
push_back 평균 O(1) 뒤에 추가만 하면 됨
pop_back O(1) 마지막 원소만 제거
v[i] O(1) 연속 메모리, 바로 접근
insert(중간) O(1) 뒤의 원소를 전부 밀어야
erase(중간) O(n) 뒤의 원소를 전부 당겨야

 

 

'카테고리 없음'의 다른글

  • 현재글C++ STL - Vector

티스토리툴바