[賢斌] vector<벡터>

40-1.벡터

40-1-가.벡터

벡터는 동일 타입의 자료 집합인 시퀀스 컨테이너의 대표이다. 템플릿 기반이므로 임의 타입을 요소로 가질 수 있으며 요소의 개수에 따라 자동으로 메모리를 관리한다. 즉 벡터는 임의 타입의 동적 배열로 정의할 수 있다. 구조가 단순하고 사용법이 쉬우며 몇 가지 경우를 제외하고 대부분의 경우 자료 관리에 탁월한 성능을 보이므로 STL 컨테이너 중 활용 빈도가 가장 높고 실용적이다.

STL의 컨테이너들은 대부분 비슷한 방식으로 추상화되어 있어 하나만 정성들여 공부해 놓으면 나머지는 차이점을 확인하는 정도만으로 쉽게 이해할 수 있다. 생성자도 거의 유사하며 멤버 함수의 이름은 물론이고 어떤 경우는 원형까지도 완전히 똑같다. 컨테이너라는 추상적인 실체가 유사하기 때문에 인터페이스도 유사할 수밖에 없다. 물론 완전히 같지는 않아서 각 컨테이너마다 약간씩의 차이점들도 존재한다. 이 절에서 벡터에 대해 아주 상세하게 연구하며 이후의 컨테이너들은 벡터와 다른 점을 위주로 설명하기로 한다. 컨테이너를 잘 이해하고 싶으면 우선 벡터부터 철저히 연구해 봐야 한다.

벡터의 내부적인 구성 원리는 C의 정적 배열과 거의 유사하며 특성과 장단점도 배열과 동일하다. 요소들의 크기가 똑같고 인접한 위치에 이웃하여 배치되므로 메모리를 적게 차지하며 임의 위치를 빠른 속도로 액세스할 수 있다. 최상위 레벨의 임의 접근 반복자를 제공하므로 STL의 모든 알고리즘을 사용할 수 있다. 그러나 삽입, 삭제시 요소의 인접 배치 원칙을 지키기 위해 요소를 이동시켜야 하는 번거로움이 있어 삽입, 삭제 속도가 느리다는 것이 단점이다. 삽입, 삭제가 아주 빈번할 때는 벡터보다는 리스트를 사용하는 것이 좋다.

벡터뿐만 아니라 STL의 모든 컨테이너는 클래스 템플릿으로 정의되어 있다. 그래서 템플릿으로 전달되는 임의의 인수 타입들을 저장할 수 있는 것이다. 벡터의 선언문은 다음과 같다.

template <class Type, class Allocator = allocator<Type> > class vector 

Type은 벡터에 저장되는 요소의 타입이며 벡터는 이 타입의 집합을 관리한다. 두 번째 인수 Allocator는 내부적인 메모리 관리에 사용되는 할당기인데 디폴트가 제공되므로 생략 가능하다. 특별한 경우가 아닌 한은 디폴트 할당기를 사용하므로 벡터의 인수로는 주로 요소의 타입만이 전달된다.

이 템플릿안에는 벡터를 관리하는 멤버 변수와 멤버 함수들이 포함되어 있다. 또한 컨테이너에서 사용하는 타입들도 typedef로 정의되어 있는데 이 타입은 STL의 모든 구성 요소들이 사용하는 일종의 약속이다. 모든 컨테이너는 자신이 정의하는 타입을 약속된 이름으로 제공해야 하며 반복자나 알고리즘은 컨테이너를 조작하기 위해 이 타입들을 사용한다.

타입	설명
value_type	컨테이너의 요소 타입이다.
(const_) pointer	요소를 가리키는 포인터 타입이다. 이하 4개의 타입은 상수 버전도 제공된다.
(const_) reference	요소의 레퍼런스 타입이다.
(const_) iterator	요소의 레퍼런스를 가리키는 반복자 타입이다.
(const_) reverse_iterator	역방향 반복자 타입이다.
difference_type	두 반복자의 차를 표현하는 타입이다. 통상 int이다.
size_type	크기를 표현하는 타입이다. 통상 unsigned이다.

 어떤 컨테이너 C의 요소 타입을 알고 싶다면 C에 정의되어 있는 value_type을 참조하면 된다. 앞 장에서 만들어 놓은 dump 함수에서 컨테이너 타입과 똑같은 출력 스트림 반복자를 만들기 위해 value_type을 사용했었다. 모든 컨테이너가 요소의 타입을 value_type이라는 이름으로 정의하고 있으므로 dump는 임의의 컨테이너를 출력할 수 있는 것이다.

같은 원리로 컨테이너에 대한 반복자가 필요하면 컨테이너가 정의하는 iterator 타입을 사용하면 된다. 반복자도 물론 클래스 템플릿으로 정의되어 있는데 지원 컨테이너에 따라 반복자의 실제 구현은 상당히 다를 것이며 컨테이너별로 고유의 반복자를 정의할 것이다. 하지만 컨테이너가 iterator라는 약속된 이름으로 반복자 타입을 정의하고 있으므로 우리는 iterator라는 알려진 타입으로 변수만 선언하면 반복자를 만들어 쓸 수 있다.

벡터의 생성자는 다음 4 가지가 중복 정의되어 있다. 문서상의 원형에는 생성자의 마지막 인수로 const A& al = A()라는 할당기 인수가 하나 더 있는데 디폴트가 지정되어 있고 보통 생략하므로 원형에 적지 않기로 한다. 실용성도 없는데 괜히 원형만 복잡하게 만들 뿐이다. 이후의 컨테이너도 마찬가지로 할당기는 무시한다.

explicit vector();
explicit vector(size_type n, const T& v = T());
vector(const vector& x);
vector(const_iterator first, const_iterator last);

 첫 번째 생성자가 디폴트 생성자이다. 할당기를 인수로 받기는 하지만 생략 가능하므로 이 생성자가 디폴트 생성자 역할을 한다. 인수없이 벡터를 생성할 경우 요소를 가지지 않는 빈 벡터가 만들어진다. 최초 빈 상태로 생성하더라도 메모리가 자동으로 관리되므로 이후 얼마든지 요소를 추가할 수 있다.

두 번째 생성자는 벡터의 초기 크기를 지정하며 T 타입의 초기값을 지정할 수 있다. 초기값의 디폴트는 T의 디폴트 생성자가 만든 값으로 지정되어 있는데 통상 0, false, NULL, "" 등이 될 것이다. 물론 어디까지나 디폴트일 뿐이므로 초기값을 명시하면 지정한 값 n개를 가지는 벡터가 만들어진다. 이 생성자는 속도를 높이기 위해 첫 번째 요소만 생성한 후 나머지 n-1개의 요소는 복사 생성자를 호출하여 생성한다.
 두 번째 생성자는 정수값 하나만을 취하므로 변환 생성자이다. 그래서 explicit로 선언하여 명시적인 생성만을 허락한다. 만약 이 생성자가 explicit가 아니라면 vi=3 따위로 대입할 때 컴파일러는 정수 3으로부터 크기 3의 벡터를 생성하여 vi에 대입하려고 할 것이다. 또는 벡터를 인수로 취하는 함수에게 정수를 넘겨도 별다른 불만없이 정수로부터 벡터를 만들어 함수를 호출하려고 할 것이다. 정수와 벡터는 호환 타입이 아니므로 명시적으로 지정하지 않는 한 변환하지 않는 것이 바람직하며 그래서 이 생성자가 explicit로 선언되어 있는 것이다.

세 번째 생성자는 복사 생성자인데 다른 벡터로부터 똑같은 벡터를 만들어 낸다. 내부에서는 아마도 깊은 복사를 할 것이다. 네 번째 생성자는 반복자가 지정한 구간의 요소들을 가지는 새로운 벡터를 생성한다. 이때 반복자는 꼭 벡터의 반복자가 아니더라도 상관없다. 정적 배열이나 리스트의 반복자를 전달할 수도 있어 다른 컨테이너로부터 벡터를 초기화할 수 있다. 다음 예제는 벡터의 생성자 4 개를 테스트한다.

예 제 : vectorcon

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

template<typename C> void dump(const char *desc, C c) {
      cout.width(12);cout << left << desc << "==> ";
      copy(c.begin(),c.end(),ostream_iterator<typename C::value_type>(cout," ")); cout << endl; }

void main()
{
     vector<string> v1;dump("v1",v1);
     vector<double> v2(10);dump("v2",v2);
     vector<int> v3(10,7);dump("v3",v3);
     vector<int> v4(v3);dump("v4",v4);
     int ar[]={1,2,3,4,5,6,7,8,9};
     vector<int> v5(&ar[2],&ar[5]);dump("v5",v5);
}

4 가지 생성자를 모두 호출하여 여러 가지 방법으로 벡터를 만들어 보았다. 잘 생성되겠지만 화면에 출력해 보지 않으면 예제가 의심스러우므로 앞장에서 만들었던 dump 함수를 사용하여 벡터 전체를 출력해 보았다. 앞으로도 컨테이너를 출력할 때는 이 함수를 종종 애용할 것이다. 실행 결과는 다음과 같다.

 v1          ==>
v2          ==> 0 0 0 0 0 0 0 0 0 0
v3          ==> 7 7 7 7 7 7 7 7 7 7
v4          ==> 7 7 7 7 7 7 7 7 7 7
v5          ==> 3 4 5

 각각의 생성자가 벡터를 어떻게 생성해 놓았는지 점검해 보자. v1은 디폴트 생성자로 인수없이 선언했으므로 빈 벡터로 만들어진다. 내부에 요소를 전혀 가지지 않지만 삽입, 추가 함수로 얼마든지 요소를 저장할 수 있다.

v2는 크기 10의 실수형 벡터이되 초기값을 주지 않았으므로 실수의 디폴트값인 0.0으로 초기화될 것이다. v2(10,1.2)로 초기값을 주면 10개의 요소들은 모두 1.2의 값을 가진다. v3는 정수형의 벡터이되 크기는 10이고 초기값 7을 주었으므로 7이 열 개 들어 있는 상태로 생성된다. v4는 v3를 복사해서 만들어졌으므로 완전히 똑같은 모양을 가진다. 물론 생성 단계에서만 같을 뿐이며 각자는 서로 독립적으로 수정될 수 있다.

마지막 v5는 반복자 구간을 받아들이는 생성자로 다른 컨테이너의 구간으로부터 초기값을 받아온다. 예제에서는 정수 배열 ar의 일부 구간을 취해 생성하도록 했는데 리스트나 데크 또는 이미 만들어진 다른 벡터의 구간으로부터 생성할 수도 있다. v5 벡터가 생성되는 과정은 다음과 같다. 반복자 구간의 끝은 항상 제외된다는 점을 주의하도록 하자.

벡터는 요소 저장을 위한 메모리를 자동으로 관리한다. 요소가 삽입될 때는 벡터 크기를 신축적으로 늘리고 벡터가 파괴될 때 할당한 메모리도 알아서 정리한다. 그래서 별도로 벡터 정리 코드를 작성할 필요가 없다. 벡터의 메모리 관리 기능은 알아서 동작하도록 자동화되어 있지만 가끔은 개발자가 직접 개입하여 크기를 관리해야 할 필요도 있다.

벡터의 메모리 관리 함수들은 string의 관리 함수들과 거의 유사하다. string이 사실상 문자의 벡터이기 때문에 비슷할 수밖에 없다. 이런 걸 두고 일관성이라고 하며 STL 전체에 일관되게 나타난다. 그래서 앞에서 공부를 잘 해 놓으면 뒤쪽 공부가 쉬워질 수 있는 것이다. 마찬가지로 벡터를 잘 공부해 놓으면 리스트나 데크는 누워서 햄버그 먹기만큼이나 쉽다. 

함수	설명
size	요소 개수를 조사한다.
max_size	벡터가 관리할 수 있는 최대 요소 개수를 조사한다.
capacity	할당된 요소 개수를 구한다.
resize(n)	크기를 변경한다. 새 크기가 더 클 경우 벡터의 원래 내용은 유지하며 새로 할당된 요소는 0으로 초기화된다.
reserve(n)	최소한의 크기를 지정하며 메모리를 미리 할당해 놓는다. 새 크기가 더 클 경우 벡터의 원래 내용은 유지한다. 새로 할당된 요소는 초기화되지 않는다.
clear(n)	모든 요소를 삭제한다.
empty	비어 있는지 조사한다.

이중 개수를 조사하는 size와 용량을 미리 확보하는 reserve가 특히 많이 사용된다. 간단한 테스트 예제를 작성하여 각 멤버 함수가 어떤 값을 조사하는지 확인해 보자.

예 제 : vectormem

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

void main()
{
     vector<int> vi;

     printf("max_size = %d\n",vi.max_size());
     printf("size = %d, capacity = %d\n",vi.size(),vi.capacity());
     vi.push_back(123);
     vi.push_back(456);

     printf("size = %d, capacity = %d\n",vi.size(),vi.capacity());
     vi.resize(10);
     printf("size = %d, capacity = %d\n",vi.size(),vi.capacity());
     vi.reserve(20);
     printf("size = %d, capacity = %d\n",vi.size(),vi.capacity());
}

 실행 결과는 다음과 같다.

max_size = 1073741823
size = 0, capacity = 0
size = 2, capacity = 2
size = 10, capacity = 10
size = 10, capacity = 20
 
최대 크기는 무려 10억개나 되는데 정수형 10억개이므로 4G까지 벡터 크기를 늘릴 수 있다는 얘기이다. 이 크기는 이론상의 크기일 뿐 실제로는 운영체제의 메모리 제공 능력에 영향을 받는데 대부분의 환경에서 주소 공간의 부족으로 인해 절반 정도밖에 확장할 수 없다. 그렇다고 하더라도 5억개는 실로 엄청난 개수인데 무한하다고 표현해도 틀리지 않을 정도다.
 
 빈 벡터로 만들면 크기 0으로 생성되며 요소를 두 개 추가하면 크기가 2로 늘어난다. resize는 지정한 크기로 요소 수를 늘리며 새로 생겨난 요소는 타입의 디폴트값으로 초기화되는데 vi는 정수형 벡터이므로 int()값인 0으로 초기화될 것이다. capacity는 할당되어 있는 메모리양인데 이 크기는 size보다 크거나 같다. 벡터는 메모리가 부족할 경우 현재 용량의 2배씩 메모리를 늘려 나가며 앞으로 추가될 요소를 고려하여 약간의 여유분을 미리 할당해 놓는다. capacity() - size()는 할당된 메모리에서 실제 사용한 양의 차이이며 별도의 재할당없이도 이만큼을 더 저장할 수 있다. 
 
 reserve는 미리 메모리를 할당해 놓는 함수인데 재할당의 불이익과 반복자 무효화를 피하기 위해 가끔 이 함수가 꼭 필요하다. 벡터가 계속 늘어날 경우 메모리가 재할당되며 이때 뒤쪽의 자유 영역이 충분하지 않을 경우 전체를 다른 위치로 옮겨 복사하기도 해야 하는데 이는 아주 느린 동작이다. 백만개의 요소를 연속적으로 추가하면 19번 정도 재할당이 일어나는데 이렇게 되면 전체적인 삽입 속도가 심하게 떨어질 것이다. 미리 필요한 메모리양을 안다면 자동으로 메모리를 늘리도록 내버려 두지 말고 reserve로 필요한 메모리를 미리 확보해 놓는 것이 유리하다.
 
 clear는 벡터를 비우고 empty는 벡터가 비어 있는지 점검한다. empty는 size() == 0 조건을 점검하는데 이 두 조건이 논리적으로는 같지만 실제로는 굉장한 차이가 있을 수도 있다. size는 정확한 개수를 구하므로 요소가 많을 경우 일일이 세어 봐야 한다. 특히 리스트같은 컨테이너는 개수를 구하기 위해서도 순회가 필요하므로 size의 속도는 다소 느리다. 하지만 empty는 0인지 아닌지만을 점검하며 훨씬 더 빠른 속도로 컨테이너가 비어 있는지를 점검해내므로 가급적이면 empty를 사용하는 것이 유리하다.