9-1. STL - Vector (1)

0. STL(Standard Template Library)

- C++ 프로그래밍 할 때 필요한 자료구조와 알고리즘을 템플릿으로 제공하는 라이브러리.

 

(1) 컨테이너(Container)

데이터를 저장하는 객체(자료구조 ; 자료를 어떻게 저장할 것인가?).

 

(2) 배열의 단점

추후에 추가적인 수요에 따라 배열을 확장하거나 축소할 수 없음.

 

(3) 동적 배열

크기가 동적으로 확장 또는 축소함.

 

 

1. 벡터(Vector) - 동적 배열 컨테이너 클래스

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> a;

    a.push_back(1);
    a.push_back(2);
    a.push_back(3);
    a.push_back(4);
    a.push_back(5);

    const int size = a.size();
    for(int i = 0; i < size; i++)
    {
        cout << a[i] << endl;
    }
}

vector는 기본적으로 배열과 동일한 역할을 수행한다.

그렇다면 배열을 어떻게 유동적으로 늘리고 줄일 수 있었을까?

 

1. 동작 원리(Size / Capacity)

 

Ⅰ. 여유분을 두고 메모리를 할당함.

 

Ⅱ. 여유분까지 꽉 차면 메모리 할당 영역을 1.5배 ~ 2배 확장(증설)함.

 

int main()
{
    vector<int> a;

for (int i = 0; i < 1000; i++)
{
    a.push_back(100);
    cout << a.size() << " " << a.capacity() << endl;
}
}

    vector<int> a(1000, 0);
    // size를 1000으로 설정하고 각 요소를 0으로 초기화

(1) Size ; 실제 사용한 데이터의 개수

1, 2, 3, 4 ... 한 개씩 증가.

 

(2) Capacity ; 여유분을 포함한 용량 개수

1, 2, 3, 4, 6, 9, 13, 19, 28, 42, 63 ... 이전 값의 1.5배씩 증가.

증가하지만 줄어들지는 않음.

 

ex) 동적 배열이 메모리를 확보하는 방법

(1) 할당된 메모리를 모두 사용

[할당된 메모리 ; 1 2 3 4 5]    [ 다른 곳에서 활용되는 메모리 ;             ]

[새로운 영역 ;                                ]

 

(2) 할당된 메모리 내의 데이터를 통째로 이사

[할당된 메모리 ; ]    [ 다른 곳에서 활용되는 메모리 ;             ] <- 다른 메모리 영역을 침범하지 않기 위해 통째로 이사

[새로운 영역 ;  1 2 3 4 5                              ]  <= 메모리가 이전 데이터 영역의 크기보다 1.5배 ~ 2배 커짐

 

ex-2) reserve 문법

a.reserve(1000);

데이터를 1000개 이내로 사용할 것이라고 명시적으로 선언하면 capacity가 1000으로 확정됨.

이후에 데이터가 1001개가 되면 capacity가 1500(이전의 1.5배)가 됨.

capacity를 미리 지정하여 확보하면 기존의 데이터를 복사하여 이동하는 작업이 생략되어 더 효율적으로 작동함.

 

ex-3) resize 문법

a.resize(1000);

resize를 사용하여 데이터를 1000개로 설정하면 size와 capacity가 1000개로 설정됨.

 

ex-4) clear 문법

a.clear();

동적 배열을 초기화하여 size는 0이 됨. capacity는 그대로 남음.

capacity 까지 초기화하고자 하면 임시로 만든 벡터와 스왑하면 된다.

vector<int>().swap(a);

 

2. 반복자(Iterator) ; 포인터와 유사함

컨테이너가 들고 있는 원소(데이터)를 가리키고 다음 또는 이전 원소로 이동할 수 있음.

int main()
{
    vector<int> v;

    for (vector<int>::size_type i = 0; i < v.size(); i++)
    v[i] = i;
    //~~~~

기본적으로 v.size는 unsigned int (양수인 정수)타입 이므로 오류가 발생한다.

따라서 i를 알맞은 타입으로 맞춰주도록 vector<int>::size_type 문법을 사용한다.

또는 static_cast를 사용하여 i를 캐스팅해줄 수 있다.

 

(1) 반복자와 포인터의 비교

    vector<int>::iterator it;
    int* ptr;

    it = v.begin();
    ptr = &v[0];
    
    cout << (*it) << " " << (*ptr) << endl;

반복자인 it는 벡터의 첫 값을 가지게 되고, 포인터인 ptr은 v 배열의 첫 요소의 값을 가지게 된다.

또한 it와 ptr은 같은 주소를 가리키고 있다.

 it는 동적 배열을 위한 포인터처럼 사용할 수 있다.

하지만 it는 어떤 컨테이너에 속하고 있는지에 대한 정보를 가지고 있지만 ptr는 그렇지 않다는 차이가 있다.

 

(2) 반복자 활용

it++;
++it;
// 반복자를 1만큼 증가시킴 -> 다음 데이터를 가리키게 함.

 

(3) 반복자의 처음과 끝

vector<int>::iterator itBegin = v.begin();
vector<int>::iterator itEnd = v.end();

itBegin은 배열의 첫 값을 가지고 있지만, itEnd는 유효하지 않은 끝 값인 쓰레기 값을 가지고 있음에 유의한다.

 

(4) 반복자를 활용하는 방법

for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) // it != v.end() 끝이 아닐 때까지 반복
{
	cout << (*it) << endl;
}
// 임시 값을 복사하는 과정이 없는 ++it가 조금 더 효율적.

배열의 끝까지 각 배열의 요소(데이터)값을 출력하게 반복하도록 한다.

 

반복자는 벡터 뿐 아니라 다른 컨테이너에서도 공통적으로 사용하기 때문에, i를 증가시키는 방법보다 반복자를 활용하는 것이 더 추천된다.

 

(5) const_iterator

값을 변경하지 않는 반복자를 사용할 때 사용할 수 있음.

vector <int>::const_iterator cit1 = v.cbegin();

 

(6) 역방향 반복자 ; reverse_iterator

for (vector<int>::reverse_iterator it = v.rbegin(); it != v.rend(); ++it)
{
}

맨 뒤의 요소부터 앞의 요소로 진행하게 만들 수 있음.