[C++ STL] vector 컨테이너

 

💡 vector의 주요 인터페이스와 특징

 

vector 컨테이너는 대표적인 시퀀스 컨테이너로 배열과 비슷한 양상을 띄고 있습니다.

알고리즘 문제를 풀 때에 많이 사용되는 컨테이너 중 하나 입니다.

 

또한 vector는 시퀀스 컨테이너이기 때문에 원소의 저장 위치(순서)가 정해지며, 배열 기반 컨테이너이므로 원소가 하나의 메모리 블록에 할당됩니다.

vetor의 구조

시퀀스 컨테이너는

원소를 차례차례 추가하는 push_back()과 제거하는 pop_back() 연산과

첫 원소를 참조하는 front()와 마지막 원소를 참조하는 back() 연산

지정한 위치에 원소를 삽입할 수 있는 insert() 연산을 가집니다.

 

vector의 경우 앞쪽이 막혀있는 형태이기 때문에 앞 쪽에서 원소를 추가/제거를 할 수 없으며, 뒷 쪽에서만 원소를 추가/제거(push_back(), pop_back()) 할 수 있습니다.

 

---

 

💡 vector의 생성자

vector<T> v	v는 빈 컨테이너
vector<T> v(n)	v에 기본 값으로 초기화된 n개의 원소가 있다.
vector<T> v(n,x)	v에 x값으로 초기화 된 n개의 원소가 있다.
vector<T> v(v2)	v는 vector<T> v2의 복사본이다.
vector<T> v(b,e)	v는 반복자 구간 [b,e)로 초기화된 원소를 가진다.

 

---

 

💡 할당(크기와 메모리)

 

1. 크기를 반환하는 멤버 함수 - size(), capacity(), max_size()

vector<int> v;

v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);

cout << v.size() << endl;
cout << v.capacity() << endl;
cout << v.max_size();

[출력 결과]

5 // size(): 원소의 개수 
6 // capacity(): 할당된 메모리의 크기
1073741823 // max_size(): 최대 저장 가능한 원소의 개수

size()와 max_size()는 직관적으로 이해가 가능하지만, capacity()는 조금 다릅니다.

해당 멤버 함수를 이해하려면 vector에 대해 좀 더 알아볼 필요가 있습니다.

---

 

2. capacity()에 대하여

위에서 사용해봤던 size()와 max_size()는 모든 컨테이너가 가지는 멤버 함수입니다.

하지만 capacity()는 오직 vector 컨테이너만이 가지고 있는 멤버 함수입니다.

 

왜일까요?

이는 vector의 "메모리 할당 정책"과 관련이 있습니다.

 

vector는 push_back()을 통해서 원소를 계속해서 추가 할 수 있는 컨테이너 입니다.

(즉, 메모리의 크기가 계속해서 변할 수 있는 가능성이 있습니다.)

원소가 추가 될 때마다 메모리의 크기를 늘려줘야 한다는 이야기입니다.

 

원소가 추가 될 때, 메모리를 매번 재 할당하고 기존의 값들을 재 할당한 메모리에 복사한다면 너무 비효율적일 것입니다.

이를 보완하기 위해 만들어진 개념이 바로 capacity입니다.

원소가 추가될 때마다 메모리를 재할당하지 않고 미리 넉넉한 메모리를 확보한다면, 비용을 줄일 수 있습니다.

 

원소를 추가하려고 할 때,

  ⓐ 메모리의 크기(capacity) ≥ 원소의 개수(size)일 때, 메모리 재할당 수행 X

  ⓑ 메모리의 크기(capacity) ＜ 원소의 개수(size)일 때, 메모리 재할당 수행 O

     메모리 할당 정책은 컴파일러마다 조금씩 다르지만 대체로 이전 메모리 크기의 1/2만큼을 더 할당합니다. 

---

 

3. reserve(), resize(), swap()

  1) 메모리 예약 함수 reserve()

     원하는 메모리의 크기를 매개변수로 전달하면 reserve()를 통해 capacity를 할당할 수 있습니다.

     size가 capacity를 초과하기 전까지는 메모리 재할당이 일어나지 않습니다.

     그러다가 원소가 더 추가되어 size가 capacity보다 더 커지면 그 때 메모리 재할당이 일어납니다.

    vector<int> v;
    v.reserve(4);
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    cout << v.capacity() << endl;

    v.push_back(50);
    cout << v.capacity();

[출력결과]

4
6

 

  2) 컨테이너의 크기(size) 변경 resize()

     컨테이너의 size를 매개 변수로 전달한 값으로 재조정합니다. 

     여기서 유의할 점은 ① size를 키울 때 capacity도 늘어나지만, ② size를 줄일 때에는 capacity가 같이 줄지 않는다는 점입니다.

     매개 변수를 두 개 전달하여 확장되는 원소에 초깃값을 지정할 수 있습니다.

     v.resize(20, 5)는 size를 20으로 늘리고, 추가되는 원소를 5로 초기화하라는 뜻입니다.

 

  3) swap()

     swap()을 이용한 할당 메모리 제거

    vector<int> v(5);
    // vector<int>(): 기본 생성자를 이용하여 임시 객체 생성(capacity: 0)
    // vector<int>().swap(v): 생성된 임시 객체와 v를 swap
    vector<int>().swap(v);

    두 컨테이너 안의 원소 교환

    vector<int> v1;
    v1.push_back(10);
    v1.push_back(20);
    
    vector<int> v2;
    v2.push_back(100);
    v2.push_back(200);
    
    v1.swap(v2);

---

 

4. empty(), clear()

   clear()는 vector 안에 있는 모든 원소를 비우라는 뜻이며, empty()는 컨테이너가 비었는지의 유무를 반환하는 함수입니다.

    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);

    cout << v.empty() << endl;

    v.clear();
    cout << v.empty();

[출력 결과]

0 // empty(): false
1 // empty(): true

 

---

 

💡 참조

1. 첫 번째 원소 참조 front(),  마지막 원소 참조 back()

    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);

    cout << v.front() << endl; // 첫 번째 원소 참조
    cout << v.back(); // 마지막 원소 참조

[출력 결과]

10
40

 

 

2. [], at()

시퀀스 컨테이너 중 배열 기반 컨테이너인 vector와 deque는 [] 연산자와 at() 멤버 함수를 사용할 수 있습니다.

 

[] 연산자와 at() 멤버 함수는 기능이나 결과는 같습니다. 

[] 연산자는 범위 점검을 하지 않지만, at() 멤버 함수는 범위 점검을 하며 동작한다는 차이점이 있습니다.

<at() 멤버 함수 사용 시, 범위를 넘어가는 경우 out_of_range 예외가 발생합니다.>

 

따라서 [] 연산자가 at() 멤버 함수보다 속도가 조금 더 빠릅니다.

    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);

    // [] 연산자와 at() 멤버 함수는 같은 결과를 가지고 온다.
    cout << v[2] << endl;
    cout << v.at(2);

[출력 결과]

30
30

 

---

 

💡 삽입

1. push_back()

   매개 변수로 전달한 인자를 해당 vector의 뒷 쪽에 삽입합니다.

    vector<int> v;
    v.push_back(100); // 100
    v.push_back(200); // 100 200

---

 

2. insert()

  1) q = v.insert(p, x)

     여기서 p과 q는 반복자입니다.

     p가 가리키는 자리에 값 x를 삽입하고, 삽입한 x의 위치를 반복자로 반환하여 q에 전달해줍니다.

    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);

    vector<int>::iterator iter = v.begin() + 2;
    vector<int>::iterator iter2;

    // iter가 가리키는 곳에 100을 삽입한다.
    // iter2: 삽입된 100을 가리키는 반복자
    // insert 이후: 10 20 100 30 40
    iter2 = v.insert(iter, 100);
    
    for(iter = v.begin(); iter != v.end(); iter++){
        // *iter를 통해 값을 가리킬 수 있다.
        cout << *iter << " ";
    }
    cout << endl;
    cout << "iter 2: " << *iter2;

  2) v.insert(p, n, x)

     p는 반복자, n은 삽입할 원소의 갯수, x는 삽입할 원소의 값입니다.

     p가 가리키는 곳에 값이 x인 원소 n개를 삽입하라는 뜻입니다.

    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);

    vector<int>::iterator iter = v.begin() + 2;

    // iter가 가리키는 곳에 정수 100개를 3개 삽입
    // insert 이후: 10 20 100 100 100 30 40
    v.insert(iter, 3, 100);

  3) v.insert(p, b, e)

     p는 반복자, b와 e는 구간입니다.

     p가 가리키는 곳에 구간 [b, e)의 원소를 삽입하라는 뜻입니다.

    vector<int> v;
    v.push_back(100);
    v.push_back(200);
    
    vector<int>::iterator iter = v.begin() + 1;

    // iter 위치에 [v.begin(), v.end()) 구간의 원소를 삽입입
    // insert 후: 100 100 200 200
    v.insert(iter, v.begin(), v.end());

---

 

💡 제거

1. pop_back()

   매개 변수가 따로 없으며, 해당 멤버 함수를 실행하면 vector의 제일 뒤에 있는 원소가 제거된다.

    vector<int> v;
    v.push_back(100);
    v.push_back(200); // 100 200
    
    v.pop_back(); // 100
    v.pop_back(); // empty

2. erase()

  1) q = v.erase(p)

     q와 p 모두 반복자입니다.

     p가 가리키고 있는 위치의 원소를 제거합니다. 제거된 원소의 다음 원소를 가리키는 반복자를 반환하여 q에 전달합니다.

    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50); // 10 20 30 40 50

    vector<int>::iterator iter = v.begin() + 1; // 20의 위치를 가리킴
    vector<int>::iterator iter2;

    iter2 = v.erase(iter); // 10 30 40 50

  2) q = v.erase(b, e)

     q는 반복자, b와 e는 구간을 뜻합니다.

     구간 [b, e)의 원소를 제거합니다. 제거한 원소의 다음 원소를 가리키는 반복자를 반환하여 q에 전달합니다.

    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50); // 10 20 30 40 50

    vector<int>::iterator iter;

    // [v.begin(), v.begin() + 2) 구간: 10, 20의 원소를 제거
    iter = v.erase(v.begin(), v.begin() + 2); // 30 40 50

---

💡 vector 컨테이너 주요 특징 정리

1. vector는 시퀀스 컨테이너이며 배열 기반 컨테이너 입니다. 

2. 배열 기반 컨테이너이기 때문에 원소가 추가 되거나 삽입될 때 메모리 재할당이 일어날 수 있고, 이때 상당한 비용이 들게 됩니다.

3. capacity()를 통해 메모리 할당 크기가 얼마인지 확인할 수 있습니다.

4. reserve()를 통해 메모리의 크기(capacity)를 할당(예약)할 수 있습니다.

5. 원소가 연속하게 저장되므로 [], at()와 같이 특정 원소에 임의로 접근할 수 있으며 속도가 빠른 편입니다.

   []는 범위 검사를 하지 않는 대신 속도가 조금 더 빠르고, at()는 범위 검사를 하는 대신 속도가 조금 더 느립니다.

   하지만 insert(), erase(), push_back() 등이 빈번하게 호출되어야하는 프로그램이라면 다른 컨테이너 사용을 고려해야 합니다.

6. 시퀀스 기반 컨테이너 이므로 front(), back(), push_back(), pop_back() 멤버 함수를 지원합니다.

   하지만 동시에 배열 기반 컨테이너이므로 앞 쪽에서 작동하는 멤버 함수는 지원하지 않습니다. 이는 vector 컨테이너에서 비효율적이기 때문입니다.

 

 

 

참고 책 : 뇌를 자극하는 C++ STL