3. Array & Vector

array(어레이)는 C++11에 추가된 시퀀스 컨테이너로 C의 배열과 유사하다.

 

C++에서 헤더파일 <array>를 인클루드하면 array를 사용할 수 있다. 이 헤더파일에는 array 구조체가 정의되어 있다.

 

STL은 템플릿으로 구현되어 있기 때문에 STL 변수를 선언할 때는 typename을 명시해 주어야 한다. array의 경우 선언할 때 typename과 함께 array의 크기를 명시해야 한다.

array<int, 5> a;

이렇게 하면 크기가 $5$인 array가 선언된다. array는 배열과 마찬가지로 지역 변수로 선언할 경우 쓰레기값이 남아 있으므로 초기화를 해야 한다.

 

array의 멤버 함수는 다음과 같다:

a.front();	a의 첫 번째 원소를 참조한다.
a.back();	a의 마지막 원소를 참조한다.
a.size();	a에 들어 있는 원소의 개수를 반환한다.
a.empty();	a가 비었는지 확인한다.
a.begin();	a의 첫 원소를 가리키는 반복자를 반환한다.
a.end();	a의 끝을 가리키는 반복자를 반환한다.
a.rbegin();	a의 역 순차열의 첫 원소를 가리키는 반복자를 반환한다.
a.rend();	a의 역 순차열의 끝을 가리키는 반복자를 반환한다.
a.data();	a의 첫 원소를 가리키는 포인터를 반환한다.
a.at(i);	a의 i번째 원소를 참조한다.
a.max_size();	a가 담을 수 있는 원소의 최대 개수를 반환한다.
a.fill(x);	a의 모든 원소를 x로 바꾼다.
a.swap(b);	a와 b를 맞바꾼다.

array::at 함수와 []를 이용한 접근의 차이는 범위 검사 여부이다. array::at 함수는 범위 밖의 인덱스를 지정하면 에러가 발생한다. 또한 array::data 함수는 크기가 $0$인 array에서 사용하면 널포인터를 반환할 수 있다.

 

array는 함수의 인자로 전달될 때 포인터로 변환하지 않아도 되는 등의 장점이 있지만, 거의 대부분 이 컨테이너를 알게 되는 시점이 C의 정적 배열과 다음 문단에 나오는 std::vector에 이미 익숙해진 후라서 잘 사용하지 않는다. C++11 표준이라 그 이전 표준에서는 지원하지 않는다는 점도 사용 빈도가 낮은 이유 중 하나이다.

 

---

vector(벡터)는 가장 많이 사용되는 시퀀스 컨테이너로 array에 비해 더 많은 기능이 제공된다. 헤더파일 <vector>를 인클루드하면 vector를 사용할 수 있으며, vector 클래스의 정의는 <vector> 내부에서 인클루드하는 헤더파일 <bits/stl_vector.h>에 되어 있다.

 

벡터의 선언과 초기화는 크게 다섯 가지 방법으로 할 수 있다. 선언 방법과 각각의 초기화 방식은 다음과 같다.

1. vector<int> v;       // 빈 벡터
2. vector<int> v(n);    // n개의 기본값(일반적으로 0)으로 초기화된 벡터
3. vector<int> v(n, x); // n개의 x로 초기화된 벡터
4. vector<int> v(w);    // 벡터 w의 복사본
5. vector<int> v(b, e); // 반복자 구간 [b, e)의 원소들로 초기화된 벡터

1번과 같이 빈 벡터를 선언하는 경우는 흔하다. 빈 벡터는 엄연한 표준 문법으로, 크기가 0인 배열이 비표준 확장 문법이고 도무지 쓸 일이 없는 것과는 다르다. 5번 선언의 경우 시퀀스 컨테이너, 연관 컨테이너, 유사 컨테이너의 반복자 모두 초기화에 사용할 수 있다.

 

다음은 vector의 멤버 함수이다. array의 멤버 함수 중 array::fill 함수를 제외한 12개의 함수가 vector에도 내장되어 있고, 기능이 사실상 동일하므로 이 함수들에 대한 설명은 위쪽 문단을 참고하면 된다.

v.push_back(x);	v의 끝에 x를 추가한다.
v.pop_back();	v의 마지막 원소를 삭제한다.
v.assign(n,x);	v에 x 원소 n개를 할당한다.
v.assign(b,e);	v에 반복자 구간 [b,e)의 원소를 할당한다.
v.reserve(n);	v에 n개의 원소를 저장할 수 있는 공간을 예약한다.
v.resize(n);	v의 크기를 n으로 변경하고 추가되는 공간의 값들을 기본값으로 초기화한다.
v.resize(n,x);	v의 크기를 n으로 변경하고 추가되는 공간의 값들을 x로 초기화한다.
v.insert(p,x);	p가 가리키는 위치에 x를 삽입한다.
v.insert(p,n,x);	p가 가리키는 위치에 n개의 x를 삽입한다.
v.insert(p,b,e);	p가 가리키는 위치에 반복자 구간 [b,e)의 원소를 삽입한다.
v.capacity();	v에 할당된 공간의 크기를 반환한다.
v.clear();	v의 모든 원소를 삭제한다.
v.erase(p);	p가 가리키는 위치의 값을 삭제한다.
v.erase(b,e);	반복자 구간 [b,e)에 포함된 원소들을 삭제한다.
v.emplace(p,x);	p가 가리키는 위치의 바로 앞에 x를 삽입한다.
v.emplace_back(x);	v의 끝에 x를 추가한다.
v.shrink_to_fit();	v의 용량을 v의 원소의 수에 맞게 줄인다.
v.get_allocator();	v에 설정된 할당기를 반환한다.

벡터의 용량과 크기는 다른 개념이다. 벡터의 크기는 벡터 안에 있는 원소의 수와 같고, 벡터의 용량은 그 벡터가 저장할 수 있는 원소의 수와 같다. 따라서 벡터의 크기는 벡터의 용량보다 작거나 같다. vector::reserve 함수를 사용할 경우 벡터의 용량은 max(n,v.size())가 된다. 이때 새로 예약된 공간에는 쓰레기값이 남아 있다. vector::assign 함수를 사용할 경우 벡터의 크기는 $n$이 된다. vector::shrink_to_fit 함수를 사용할 경우 벡터의 용량은 벡터의 크기와 같아진다.

 

또 하나 유의할 점은 vector::push_back 함수는 그냥 쓰면 꽤 느릴 수 있다는 것이다. 아래 코드에서 $p$의 값을 바꿔 가면서 실행시간을 측정하면 $p = 1$일 때 시간이 가장 느리게 나오는 것을 알 수 있다.

#import<bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> a;
    deque<int> b;
    stack<int> c;
    queue<int> d;
    
    int p = 1;
    clock_t x = clock();
    
    if(p == 1)for(int i = 0; i < 6000000; i++)a.push_back(i);
    if(p == 2)for(int i = 0; i < 6000000; i++)b.push_back(i);
    if(p == 3)for(int i = 0; i < 6000000; i++)c.push(i);
    if(p == 4)for(int i = 0; i < 6000000; i++)d.push(i);
    
    cout << "Time : " << (clock() - x) / 1000.;
}

vector::reserve 함수를 이용하면 이러한 문제가 줄어들지만, 무심코 그냥 사용할 수도 있으니 주의해야 한다.

 

vector에 오버로딩된 연산자는 비교, 동등 연산자(<, <=, ==, !=, >, >=)와 [] 연산자이다. 비교 연산자는 두 벡터의 원소를 문자열처럼 비교해서 bool 값을 반환한다. v[i]와 v.at(i)의 값은 기본적으로 같지만 vector::at 함수는 i가 vector의 범위를 벗어나면 out_of_range 에러가 발생한다.

 

또한 C++20에서 <=>(삼단 비교 연산자; 우주선 연산자)이라는 새로운 비교 연산자가 추가되었다. C++17까지는 두 객체 a와 b를 비교했을 때 a<b, a==b, a>b의 세 가지 결과를 구별하기 위해서 비교를 두 번 해야 했지만 <=> 연산자를 쓰면 한 번의 비교로 세 가지 결과를 구별할 수 있다. 이 연산자를 쓰기 위해서는 <compare> 헤더파일을 인클루드해야 한다. 이 헤더파일 역시 C++20에서 새로 추가되었다.