5.1 vector 데이터 추상(data abstraction)
vector 컨테이너 클래스는 기존 C 배열의 개념을 일반화시킨 것이다. 배열과 마찬가지로, vector도 첨자로 접근이 가능하며, 이 때 첨자의 범위는 0부터 (원소의 갯수 - 1)까지이다. 또한 [] 연산자를 이용해서 vector에 값을 대입하거나 vector로부터 값을 추출할 수 있다. 그러나, 이러한 공통점외에 배열과 vector는 다음과 같은 차이점을 가지고 있다.
- vector는 일반 배열보다 자신에 관한 정보를 더 많이 가지고 있다. 특히, vector의 크기나 잠정적으로 가질 수 있는 원소의 갯수에 관한 정보를 얻을 수 있다.
- vector의 크기는 동적으로 변할 수 있다. 새로운 원소를 vector의 끝이나 중간에 삽입할 수 있다. 메모리 관리도 효율적이고 자동적으로 이루어진다. 그러나, vector 중간에 원소를 삽입할 때는 list처럼 효율적이지 않다는 점에 주목해야 한다. 삽입 연산을 많이 수행하는 경우라면, vector보다는 list를 사용하는 것이 좋다.
표준 라이브러리의 vector 컨테이너 클래스는 7장에서 다룰 deque('덱'이라고 발음한다.)과 여러모로 비교가 된다. vector와 같이 deque도 인덱싱이 가능한 자료구조이다. 이 둘의 가장 큰 차이점은 deque은 컨테이너의 앞과 끝에서의 삽입이 효율적인 반면에, vector는 끝에서 삽입할 때만 효율적이라는 것이다. 대개는 둘중 어느 것을 사용해도 상관없지만, 일반적으로 vector를 사용하는 것이 좀더 작은 실행화일을 만들 수 있는 반면에, deque은 수행되는 연산의 종류에 따라 조금 빠른 프로그램을 만들기도 한다.
5.1.1 Include 화일
vector를 사용하려면 vector 헤더화일을 포함시켜야 한다.
#include <vector>
5.2 벡터 연산
이 절에서는 vector가 제공하는 멤버 함수들에 관해 좀 더 자세히 살펴본다. 앞으로도 계속 언급하겠지만, 멤버함수는 기초적인 연산들을 제공하는 반면에, 13장과 14장에서 소개할 generic 알고리듬을 사용함으로써 표준 라이브러리가 제공하는 자료구조들을 보다 유용하게 사용할 수 있게 된다.
5.2.1 벡터의 선언과 초기화
vector는 템플릿 클래스이므로 vector에 담을 원소의 타입을 명시해 주어야 한다. 원소의 타입은 integer나 double과 같은 primitive 타입이나, 포인터 타입이 될 수도 있고, 사용자 정의 타입이 될 수도 있다. 사용자 정의 타입의 경우에는 기본 생성자가 반드시 정의되어 있어야 한다. 복사 생성자도 명시적으로든 묵시적으로든 반드시 존재해야 한다.
|
배열과 마찬가지로, vector도 자신이 담게 될 원소의 갯수를 정수 인자로 하여 선언하는 것이 가장 흔한 경우다.
vector<int> vec_one(10);
(이와 같은 상황에서 vector를 생성하기 위해 사용되는 생성자는 키워드 explicit로 선언된다. 이렇게 함으로써 이 생성자가 변환 연산자로 사용되는 것을 막을 수 있다. 이렇게 하지 않으면, 본의아니게 정수를 vector로 변환하는 경우가 발생할 수 있기 때문이다.)
vector를 생성하기 위해서 사용할 수 있는 생성자에는 여러가지가 있다. vector의 사이즈 뿐만 아니라, vector의 원소들을 초기화하는데 사용되는 상수값을 제공하는 생성자도 있다. 사이즈가 명시되지 않으면, vector는 아무런 원소를 포함하지 않은 상태로 생성되게 되며, 원소가 추가될 때 자동적으로 사이즈가 증가하게 된다. 복사 생성자는 다른 vector로부터 클론을 생성할 수 있다.
vector<int> vec_two(5, 3); // 복사 생성자 vector<int> vec_three; // 가장 일반적인 형태 vector<int> vec_four(vec_two); // 대입에 의한 초기화
시작 반복자와 끝 반복자 pair를 사용하여 다른 콜렉션의 원소들로 vector를 초기화할 수 있다. 이들 인자로 들어가는 반복자의 형태는 아무것이나 가능하며, 반복자를 제공하는 컨테이너에 담긴 값들이기만 하면 이들 값들을 가지고 초기화가 가능하다.
vector<int> vec_five(aList.begin(), aList.end());
| ▶ 생성자와 반복자 |
| Because it requires the ability to define a method with a template argument different from the class template, some compilers may not yet support the initialization of containers using iterators. In the mean time, while compiler technology catches up with the standard library definition, the Rogue Wave version of the standard library will support conventional pointers and vector iterators in this manner. |
vector간의 대입도 가능하며, 이때 대입 연산자의 좌변은 우변 vector의 복사본을 가지게 된다.
vec_three = vec_five;
assign() 멤버함수는 대입 연산자와 비슷하지만, 더 기능이 많다. 인자가 더 많을 경우도 있다. 대입과 마찬가지로, 컨테이너에 담긴 값들은 인자로 명시된 값들로 바뀌게 된다. 두가지 형태의 assign()이 있는데, 첫번째는 다른 컨테이너의 서브 시퀀스를 가리키는 두개의 반복자를 취한다. 이 서브 시퀀스로부터의 값들은 받는 쪽에서의 새로운 값들이 된다. assign()의 두번째 형태는 갯수와 컨테이너 원소 타입의 값이(이것은 생략 가능) 인자로 제공된다. 함수호출을 한뒤에는 count로 명시된 갯수의 원소들만 가지게 되고, 이 원소들은 기본값과 같거나, 명시한 초기값과 같게 된다.
vec_six.assign(list_ten.begin(), list_ten.end()); vec_four.assign(3, 7); // '7'을 3개 대입 vec_five.assign(12); // '0'을 12개 대입
원소의 타입이 소멸자를 정의하고 있다면, 콜렉션으로부터 이들 원소가 삭제될 때, 이 소멸자를 호출하게 된다.
마지막으로, swap() 연산자를 통해 두 vector간에 각자 가지고 있던 원소들을 모조리 바꿔치기 할 수도 있다. 인자로 들어가는 컨테이너는 수신자의 값들을 가지게 되고, 수신자는 인자로 들어가는 컨테이너의 값들을 가지게 된다. 이 swap()은 매우 효율적이기 때문에, 원소별로 전송할 때는 반드시 이것을 사용해야 한다.
vec_three.swap(vec_four);
5.2.2 타입 정의
vector 클래스는 많은 수의 타입 정의를 포함하고 있다. 이들은 선언문에서 가장 많이 사용된다. 예를 들어, 정수 vector의 반복자는 다음과 같이 선언할 수 있다.
vector<int>::iterator location;
iterator 뿐만 아니라 다음과 같은 타입들도 정의되어 있다.
| value_type | 벡터가 관리하는 원소들의 타입 |
| const_iterator | 하부 시퀀스를 변경할 수 없는 반복자 |
| reverse_iterator | 역 이동 반복자 |
| const_reverse_iterator | 위 두가지 성질을 동시에 가지는 반복자 |
| reference | 벡터 원소에 대한 참조 |
| const_reference | 원소를 변경할 수 없는 참조 |
| size_type | 컨테이너의 사이즈를 참조할 때 사용되는 비부호 정수형 |
| difference_type | 반복자간의 거리차를 나타낼 때 사용되는 부호 정수형 |
| allocator_type | 벡터의 메모리를 관리하는데 사용되는 할당기 타입 |
5.2.3 벡터의 첨자 연산
특정 인덱스 위치에서 vector가 관리하는 값을 접근하거나 변경할 때는 첨자 연산자를 사용하며, 이는 일반 배열과 동일하다. 또한, 인덱스 값의 유효성에 대한 검사를 하지 않는다. 상수 vector를 인덱싱하면 상수 레퍼런스가 생성된다. 유요한 인덱스 범위를 벗어나는 vector를 인덱싱할 때는 어떤 결과가 나올지 예측할 수 있다.
cout << vec_five[1] << endl; vec_five[1] = 17;
첨자 연산자를 대신해서, 멤버함수 at()을 사용할 수 있다. 이 함수는 첨자 연산자와 동일한 인자를 가지고 동일한 값을 반환한다.
front() 멤버 함수는 vector의 맨 앞에 있는 원소를 반환하고, back()은 맨 마지막 원소를 반환한다. 이 두 함수 모두 상수 vector에 적용하면, 상수 레퍼런스를 반환한다.
cout << vec_five.front() << " ... " << vec_five.back() << endl;
5.2.4 확장 연산과 사이즈 변환 연산
일반적으로 vector에는 세가지의 서로 다른 '사이즈'가 존재한다. 첫째로, 현재 vector가 가지고 있는 원소의 갯수이다. 둘째로 새로운 메모리 할당없이 vector가 확장될 수 있는 최대 사이즈이다. 세째는 vector가 가질 수 있는 사이즈의 상한선이다. 이들 세값들은 각각 size(), capacity(), max_size() 멤버함수에 의해 얻을 수 있다.
cout << "size: " << vec_five.size() << endl; cout << "capacity: " << vec_five.capacity() << endl; cout << "max_size: " << vec_five.max_size() << endl;
max_size()는 사용가능한 메모리의 양 또는 size_type 자료형이 나타낼 수 있는 최대값에 의해 제한된다. 현재 사이즈와 capacity를 규명하기가 더 어렵다. 다음 절에서 살펴보겠지만, 다양한 방법으로 vector로부터 원소들을 추가하거나 삭제할 수 있다. vector로부터 원소들을 제거할 때, vector에 대한 메모리는 반환되지 않으며, 따라서, size는 줄어도 capacity는 그대로이다. 기존에 확보된 capacity를 넘지 않으면, 삽입으로 인해 새로 메모리를 할당하지는 않는다.
Memory Management
삽입으로 인해 capacity가 넘치게 되면, vector 원소들을 담을 새로운 블럭을 할당하게 된다. 그리고 나서, 원소 타입에 대한 대입 연산자를 사용하여 값들을 새로 할당된 메모리로 복사하고, 예전 메모리는 삭제한다. 이는 상당히 비싼 연산이므로, vector 데이터 타입은 프로그래머에게 vector의 capacity를 정할수 있는 방법을 제공한다. reserve() 멤버 함수는 vector가 적어도 주어진 사이즈까지는 자라날 것이라는 것을 나타내는 vector에 대한 지시자이다. reserve() 인자로 주어진 값이 현재 capacity보다 크면, 메모리 반환이 일어나고, 인자로 주어진 값이 새로운 capacity가 된다. (??) capacity가 이미 인자값을 초과하고 있다면, 메모리 반환은 일어나지 않는다. reserve()를 호출해도 vector의 사이즈와 원소값들은 바뀌지 않는다.(단, 메모리 반환이 일어나면 원소값들을 이동하는 경우는 제외한다.)
vec_five.reserve(20);
메모리 반환이 일어나면, vector들의 원소를 참조하는 모든 레퍼런스, 포인터, 반복자들은 모두 무효가 된다.
empty() 멤버 함수는 현재 vector의 사이즈가 0일 때 참이 된다. (vector의 capacity와는 무관하다.) 이함수를 사용하는 것이 size()의 리턴값과 0을 비교하는 것보다 훨씬 효과적이다.
cout << "empty is " << vec_five.empty() << endl;
resize() 멤버 함수는 vector의 사이즈를 인자값으로 만들어버린다. 이때 필요하다면 vector의 끝부분의 원소값들이 삭제되거나 첨가된다. 옵션인 두번째 인자는 새로운 원소가 추가될 때의 초기값들로 사용된다. 만약 원소 타입에 대한 소멸자가 정의되어 있다면, 콜렉션으로부터 제거되는 원소값들에 대해 소멸자가 호출된다.
// become size 12, adding values of 17 if necessary vec_five.resize (12, 17);
5.2.5 원소의 삽입과 삭제
앞에서 언급했던 바와 같이, vector 클래스는 사이즈가 증가하거나 감소할 수 있다는 점에서 일반 배열과 다르다. 삽입으로 인해 vector의 원소의 수가 현재 원소값들을 담는데 사용되는 메모리 블럭의 capacity를 초과하게 되면, 새로운 메모리 블럭이 할당되어 이곳으로 원소값들을 복사한다.
Costly Insertions
push_back()을 사용하면 vector의 끝에 새 원소를 첨가할 수 있다. 현재 할당된 메모리에 공간이 남아 있다면, 이 연산은 매우 효율적이다(상수시간).
vec_five.push_back(21); // add element 21 to end of collection
이에 대응되는 삭제 연산으로 pop_back()이 있다. 이 연산은 vector의 사이즈를 줄이고, capacity에는 변화를 주지 않는다. 컨테이너 타입이 소멸자를 정의하고 있다면, 삭제되는 원소에 대해 소멸자를 호출하게 된다. pop_back() 연산도 매우 효율적이다. (deque 클래스는 콜렉션의 앞과 뒤에서 삽입과 삭제를 허용한다.) 이들 함수들은 deque를 자세히 설명하고 있는 7장에서 설명한다.
insert() 멤버 함수를 사용하면 좀더 일반적인 삽입 연산을 행할 수 있다. 삽입할 위치는 반복자로 지정하고, 삽입은 명시된 위치의 바로 앞에서 일어난다. 정해진 갯수의 상수 원소들은 단 한번의 함수 호출로 삽입될 수 있다. 한번의 호출로 한블럭의 원소들을 삽입하는 것은 하나씩 삽입하는 것보다 훨씬 효율적이다. 한번의 호출로 기껏해야 한번의 할당만 수행하면 되기 때문이다.
// find the location of the 7 vector<int>::iterator where = find(vec_five.begin(), vec_five.end(), 7); vec_five.insert(where, 12); // then insert the 12 before the 7 vec_five.insert(where, 6, 14); // insert six copies of 14
vec_five.insert(where, vec_three.begin(), vec_three.end());
vector의 마지막 원소를 삭제하는 pop_back() 멤버 함수뿐만 아니라, 위치를 지정하는 반복자를 이용하여 vector의 중간에서 원소들을 삭제하는 함수들도 있다. erase()가 바로 그 함수이다. 두가지 형태가 있는데, 첫째는 한개의 반복자를 인자로 받아 한개의 원소값을 제거하고, 둘째는 한쌍의 반복자를 인자로 받아 이 반복자가 가리키는 범위내의 모든 값들을 삭제한다. vector의 사이즈는 줄어들고, capacity는 줄어들지 않는다. 컨테이너 타입이 소멸자를 정의하고 있다면, 삭제되는 값에 대해 소멸자를 호출한다.
vec_five.erase(where); // erase from the 12 to the end where = find(vec_five.begin(), vec_five.end(), 12); vec_five.erase(where, vec_five.end());
5.2.6 반복자
begin()과 end() 멤버 함수는 컨테이너에 대한 임의접근 반복자를 리턴한다. 이들 연산들이 반환하는 반복자들도 원소를 삽입하거나 삭제한 뒤에 무효가 될 수 있다. rbegin()과 rend() 멤버 함수는 앞과 비슷한 반복자를 반환하지만, 이들 반복자는 반대방향으로 원소들을 접근한다. 만약 컨테이너가 상수로 선언되어 있다거나, 대입 연산자의 대상이나 인자가 상수라면, 이들 연산들은 상수 반복자들을 반환할 것이다.
5.2.7 소속 검사 연산
vector는 자신이 특정값을 포함하고 있는지를 결정하는데 사용되는 연산을 직접 제공하지 않는다. 그러나, find()나 count()(13.3.1절과 13.6.1절) generic 알고리듬들이 이러한 목적으로 사용될 수 있다. 예를 들어, 다음 명령문들은 정수 vector가 17이라는 수를 포함하고 있는지를 검사하고 있다.
int num = 0; count (vec_five.begin(), vec_five.end(), 17, num); if (num) cout << "contains a 17" << endl; else cout << "does not contain a 17" << endl;
5.2.8 정렬 연산
vector는 자신이 관리하는 원소들을 자동으로 순서를 유지시키지 않는다. 그러나, sort() generic algorithm을 사용하여 vector내의 원소들을 순서대로 나열할 수 있다. 가장 간단한 형태의 정렬은 비교할 때 원소타입에 대해 less-than 연산자를 사용한다. 또다른 generic 알고리듬은 프로그래머가 명시적으로 비교 연산자를 지정할 수 있도록 하고 있다. 에를 들어, 다음은 오름차순이 아닌 내림차순으로 원소들을 배치하고 있다.
// sort ascending sort(aVec.begin(), aVec.end()); // sort descending, specifying the ordering function explicitly sort(aVec.begin(), aVec.end(), greater<int>() ); // alternate way to sort descending sort(aVec.rbegin(), aVec.rend());
14장에서 설명하고 있는 많은 연산들이 ordered 콜렉션을 담고 있는 vector들에 적용될 수 있다. 예를 들어, 두개의 vector가 merge() generic 알고리듬을 사용하여 합쳐질 수 있다. (14.6절)
// merge two vectors, printing output merge(vecOne.begin(), vecOne.end(), vecTwo.begin(), vecTwo.end(), ostream_iterator<int,char>(cout, " "));
vector를 정렬할 때는 find()와 같이 선형 순회 알고리듬 대신에 보다 효과적인 이진 검색 알고리듬을 사용한다.(?)
5.2.9 유용한 generic 알고리듬들
13장에서 설명하는 대부분의 알고리듬들이 vector와 같이 사용될 수 있다. 다음 표는 이들중에서 보다 유용한것들만을 모아놓은 것이다. 예를 들어, vector에서의 최대값은 다음과 같이 알아낼 수 있다.
vector<int>::iterator where = max_element (vec_five.begin(), vec_five.end()); cout << "maximum is " << *where << endl;
|
|
|
| 주어진 초기값으로 벡터를 채운다. | fill |
| 수열을 복사한다. | copy |
| 발생기(generator)가 생성한 값을 벡터에 집어넣는다. | generate |
| 조건을 만족하는 원소를 찾는다. | find |
| 연속적으로 중복된 원소를 찾는다. | adjacent_find |
| 벡터내에서 서브 시퀀스를 찾는다. | search |
| 최대 또는 최소 원소를 찾는다. | max_element, min_element |
| 원소의 순서를 뒤집는다. | reverse |
| 원소들을 새로운 값들로 대치한다. | replace |
| 가운데점을 중심으로 원소들을 순환시킨다. | rotate |
| 원소들을 두그룹으로 쪼갠다. | partition |
| 순열(permutation)을 생성한다. | next_permutation |
| 벡터내에서의 ... | inplace_merge |
| 벡터내의 원소들을 임의로 섞는다. | random_shuffle |
| 조건을 만족하는 원소들의 갯수를 센다. | count |
| 벡터로부터의 정보를 가지고 하나의 값을 만들어 낸다. | accumulate |
| 두 벡터의 내적을 구한다. | inner_product |
| 두벡터를 한쌍씩 비교하여 같은지를 검사한다. | equal |
| 사전식 비교 | lexicographical_compare |
| 벡터에 변환을 적용한다. | transform |
| 값들의 부분합을 구한다. | partial_sum |
| 이웃하는 값들의 차를 구한다. | adjacent_difference |
| 각 원소들에 대해 함수를 수행한다. | for_each |
5.3 부울 벡터
비트값들의 벡터는 표준 라이브러리에서는 특별한 경우로 취급하여, 값들이 효과적으로 pack될 수 있다. 부울 벡터, vector<bool>을 위한 연산들은 일반 벡터 연산의 superset이고, 단지 구현이 더 효율적이다.
부울 벡터에서는 flip()이란 멤버 함수가 추가되었다. 호출되었을 때, 이 함수는 벡터의 모든 비트를 뒤집는다. 또한 부울 벡터는 내부값을 레퍼런스로 리턴하며, 이 레퍼런스에 대해서도 flip() 멤버 함수를 지원한다. 아래 코드의 세번째 줄이 이를 설명하고 있다.
vector<bool> bvec(27); bvec.flip(); // 모든 비트를 flip bvec[17].flip(); // 17번 비트를 flipvector<bool>은 추가적으로 swap() 멤버 함수를 지원하는데, 이 함수는 한쌍의 레퍼런스가 가리키는 두개의 값을 서로 바꾼다.
bvec.swap(bvec[17], bvec[16]);★ 주의: 위에서 설명한 멤버 함수 flip()과 swap()이 실제로 위와 같이 지원되는지 아직 확인하지 못했으니, 착오 없으시기 바랍니다. 현재 g++ 2.8.1에서는 swap()이 지원하지 않고 있고, 모든 비트를 flip하는 경우도 지원하지 않는 것 같습니다. 따라서, 이것이 표준에서 지원되지 않는 이유때문인지, g++이 아직 이부분을 구현에 반영하지 않은 것인지는 좀더 살펴봐야 하겠습니다. 이점에 관해 아시는 분은 연락주시면 고맙겠습니다.
5.4 예제 프로그램 - 에라토스테네스의 체
이절에서 설명할 예제는 '에라토스테네스의 체'라고 하는 솟수를 찾는데 사용하는 아주 전통적인 알고리즘이다(제 또래 분들은 아마 예전 중학교 수학 시간에 배웠을 것임). 일단 솟수를 찾고자 하는 범위까지의 수들을 정수 vector에 담기로 한다. 이 알고리즘의 아이디어는 소수가 될 수 없는 수들을 하나씩 지워 나가면 (0으로 세팅), 가장 마지막에 남는 수들이 솟수가 된다는 것이다. 이를 위해서는 루프를 돌면서 각각의 값들이 1로 세팅된 수들의 배수인 것들을 하나씩 지워나가면 된다. 바깥쪽 루프가 끝나면 남아있는 수들이 솟수가 되는 것이다. 이 알고리즘의 프로그램은 다음과 같다.
int main()
{
// 각 숫자들을 1로 모두 세팅한다.
const int sievesize = 100;
vector<int> sieve(sievesize, 1);
// 1로 세팅된 값들 각각에 대해 이 수의 배수들을 0으로 세팅한다.
for (int i = 2; i * i < sievesize; i++)
if (sieve[i])
for (int j = i + i; j < sievesize; j += i)
sieve[j] = 0;
// 1로 세팅된 숫자들만 출력한다.
for (int j = 2; j < sievesize; j++)
if (sieve[j])
cout << j << " ";
cout << endl;
}