vector
C++ STL의 vector에 대해서 정리했습니다.
vector는 STL의 대표적인 컨테이너이자 자주 사용되는 컨테이너다.
vector는 시퀀스 컨테이너로 컨테이너 내부의 원소들이 순차적인 순서로 저장된다.
또한 배열 기반 컨테이너이기 때문에 임의 접근 반복자([])를 사용할 수 있다.
컨테이너 구조
vector는 앞이 막혀있고 뒤가 뚫려 있어 순차적으로 뒤에 원소에 추가된다.
앞이 막혀있는 이유는 vector가 배열 기반 컨테이너임에 기인한다.
vector의 앞에 원소를 추가한다면 크기만큼의 메모리를 다시 할당하며 원소들을 모두 복사해야 하는 비효율적인 연산이 발생한다.
인터페이스
생성자
vector는 다음과 같은 생성자를 가지고 있다.
vector(); // 빈 vector를 생성한다.
vector(n); // 기본값으로 초기화된 n개의 원소를 가진 vector를 생성한다.
vector(n, x); // x로 초기화된 n개의 원소를 가진 vector를 생성한다.
vector(v); // 다른 vector로부터 복사 생성한다.
vector(b, e); // 특정 반복자 구간의 원소들로 vector를 생성한다.
삽입/삭제
vector는 다른 시퀀스 컨테이너와 동일하게 push_back()과 pop_back()이 가능하다.
push_back()을 이용하면 vector의 맨 뒤에 원소를 삽입할 수 있다.
pop_back()을 이용하면 vector의 맨 뒤 원소를 삭제할 수 있다.
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
vector<int> vec;
vec.push_back(10);
vec.push_back(20);
vec.push_back(30); // 이 시점에 벡터는 10, 20, 30을 가진다.
vec.pop_back();
vec.pop_back(); // 이 시점에 벡터는 10을 가진다.
}
크기/용량
vector는 다른 컨테이너와 동일하게 size()와 max_size()를 가진다.
size()는 vector의 현재 원소의 개수를, max_size()는 vector에 저장할 수 있는 최대 원소의 개수를 반환한다.
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
vector<int> vec;
vec.push_back(10);
vec.push_back(20);
vec.push_back(30);
cout << "vector's size: " << vec.size() << endl;
cout << "vector's max size: " << vec.max_size() << endl;
}
또한 다른 컨테이너와는 달리 vector는 capacity() 인터페이스를 가지는데 이는 벡터의 용량을 반환한다.
capacity()가 필요한 이유는 vector가 배열 기반 컨테이너이기 때문이다.
맨 뒤에 원소를 삽입할 때마다 메모리를 할당하고 이전 원소를 복사하는 작업이 동반되기 때문에
메모리를 재할당하는 횟수를 줄여야만 한다.
따라서 capacity()는 기본적으로 증가 전략을 가지고 있다.
어느 시스템에서는 size() + 1/2·size()만큼씩, 다른 시스템에서는 size() + 2·size()만큼씩 증가한다.
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
vector<int> vec;
vec.push_back(10); // size: 1, capacity: 1
vec.push_back(20); // size: 2, capacity: 2
vec.push_back(30); // size: 3, capacity: 4
}
vector의 크기와 size_type
vector가 가지고 있는 현재 원소의 개수는 int가 아니다.
vector의 크기는 unsigned int며, std::size_t로 typedef 정의되어 있다.
이는 다시 vector에서 vector::size_type으로 typedef 정의되어 있다.
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
vector<int> vec;
vec.push_back(10);
vec.push_back(20);
vec.push_back(30);
vec.push_back(40);
vec.push_back(50);
for(vector<int>::size_type i = 0; i < vec.size(); i++)
cout << vec[i] << ' ';
cout << endl;
}
사전 크기 할당 및 용량 설정
앞서 말한 이유로 push_back()은 메모리 재할당 및 이전 원소 복사를 동반하므로 효율적이지 않다.
따라서 resize()를 통해 사전에 용량을 필요한 만큼 늘려서 사용하거나 생성자를 통하여 사전에 크기를 할당하는 편이 효율적이다.
#include <iostream>
#include <vector>
int main(void)
{
// 생성자를 이용한 사전 크기 할당
vector<int> vec1(3);
vec1[0] = 10;
vec2[1] = 20;
vec3[2] = 30;
// resize()를 이용한 용량 설정
vector<int> vec2;
vec2.resize(3);
vec2.push_back(10);
vec2.push_back(20);
vec2.push_back(30);
}
스왑과 용량 감소 설정
push_back()을 통해서 늘어난 capacity()는 pop_back()을 이용하여 다시 줄일 수 없다.
capacity()만큼 늘어날 가능성이 높고, capacity()를 줄이려면 메모리의 재할당과 이전 원소 복사가 동반되기 때문이다.
하지만 다시 늘어날 이유가 없다면, swap()을 이용하여 capacity()를 초기화할 수 있다.
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
vector<int> vec;
vec.push_back(10); // capacity: 1
vec.push_back(20); // capacity: 2
vec.push_back(30); // capacity: 4
vec.push_back(40); // capacity: 4
vec.push_back(50); // capacity: 8
// 임시 벡터와의 swap()을 통해 capacity를 0으로 재설정한다.
vector<int>().swap(vec);
}
모든 요소 삭제와 확인
vector를 포함한 모든 컨테이너는 clear()와 empty()를 제공한다.
clear()는 컨테이너의 모든 원소를 삭제하며, empty()는 컨테이너가 비어있는지의 유무를 반환한다.
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
vector<int> vec;
vec.push_back(10);
vec.push_back(20);
vec.push_back(30); // 이 시점에 vector는 10, 20, 30을 가진다.
vec.clear(); // 이 시점에 vector는 비어있다.
// 벡터가 비어있다면 아래의 문자열이 콘솔에 출력된다.
if(vec.empty())
cout << "vector is empty." << endl;
}
원소의 참조
vector를 비롯한 시퀀스 컨테이너는 원소를 순차적으로 저장하기 때문에 front()와 back()을 제공한다.
front()는 맨 앞의 원소에 대한 참조를, back()은 맨 뒤의 원소에 대한 참조를 반환한다.
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
vector<int> vec;
vec.push_back(10);
vec.push_back(20);
vec.push_back(30);
cout << vec.front() << endl; // 10이 출력된다.
cout << vec.back() << endl; // 30이 출력된다.
// 원소에 대한 참조이므로 변경이 가능하다.
vec.front() = 100;
vec.back() = 300;
cout << vec.front() << endl; // 100이 출력된다.
cout << vec.back() << endl; // 300이 출력된다.
}
임의 접근
vector와 deque과 같은 배열 기반 컨테이너들은 임의 접근 반복자를 가진다.
따라서 []를 이용하여 개별 원소에 접근하거나 at()을 이용하여 개별 원소에 접근한다. 둘의 유일한 차이는 at()은 범위 체크를 하며 이 때문에 속도가 느리다는 점이다.
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
vector<int> vec(5);
vec[0] = 10;
vec[1] = 20;
vec[2] = 30;
vec[3] = 40;
vec[4] = 50;
for(vector<int>::size_type i = 0; i < vec.size(); i++)
cout << vec[i] << ' ';
cout << endl;
vec.at(0) = 50;
vec.at(1) = 40;
vec.at(2) = 30;
vec.at(3) = 20;
vec.at(4) = 10;
for(vector<int>::size_type i = 0; i < vec.size(); i++)
cout << vec.at(i) << ' ';
cout << endl;
}
vector와 반복자
vector를 포함한 모든 컨테이너는 반복자를 이용하여 개별 원소를 순회 및 참조할 수 있다.
반복자는 포인터와 유사한 개념으로 *을 통해 원소를 역참조하거나 포인터 연산과 비슷하게 ++, --, +=, -=을 통해 이동할 수 있다.
vector를 포함한 모든 컨테이너는 반복자를 위한 인터페이스를 제공한다.
begin()은 맨 앞의 원소를 가리키는 반복자를 반환한다.
end()은 맨 뒤를 지칭하는 반복자를 반환한다.
주의해야 하는 점은 end()가 맨 뒤의 원소를 가리키는 반복자가 아니라는 점이다.
따라서 [begin, end)의 구간을 가지게 된다.
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
vector<int> vec;
vec.push_back(10);
vec.push_back(20);
vec.push_back(30);
vec.push_back(40);
vec.push_back(50);
// vector의 맨 앞 원소를 가리키는 반복자를 생성한다.
vector<int>::iterator iter = vec.begin();
iter += 2; // 반복자를 +2 만큼 이동시킨다. 즉, 30을 가리킨다.
cout << *iter << endl;
// 반복자를 이용한 순회
for(iter = vec.begin(); iter != vec.end(); iter++)
cout << *iter << ' ';
cout << endl;
}
역방향 반복자
기본적으로 반복자는 순차적으로 원소에 접근한다. 하지만 역순으로 원소에 접근할 필요가 있을 수도 있다.
역방향 반복자는 역순으로 원소에 접근할 때 사용한다.
vector를 포함한 모든 컨테이너는 역방향 반복자를 위한 인터페이스를 제공한다.
rbegin()은 마지막 원소를 가리키는 반복자를 반환한다.
rend()는 첫 부분을 가리키는 반복자를 반환한다.
주의해야 할 점은 반복자를 이용하여 역방향 반복자를 생성하는 경우에 역방향 반복자는 반복자의 위치 - 1만큼의 위치를 가진다.
이는 이상하게 보이지만 연산의 호환성 측면에서 보면 -- 대신 ++만으로 정방향 순회 및 역방향 순회를 할 수 있게끔 만든다.
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
vector<int> vec;
vec.push_back(10);
vec.push_back(20);
vec.push_back(30);
vec.push_back(40);
vec.push_back(50);
vector<int>::reverse_iterator riter = vec.rbegin();
// 역방향으로 vector를 순회한다.
for(; riter != vec.rend(); riter++)
cout << *riter << ' ';
cout << endl;
}
상수 반복자
원소를 순회만 하고 값을 변경할 이유가 없다면 상수 반복자를 사용하는 편이 더 안전하다.
상수 반복자는 const와 포인터의 관계와 동일하다.
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
vector<int> vec;
vec.push_back(10);
vec.push_back(20);
vec.push_back(30);
vector<int>::iterator iter; // 반복자
vector<int>::const_iterator citer; // 상수 반복자, 현재 원소의 값을 변경할 수 없다.
const vector<int>::iterator iterc; // const 반복자, 위치를 변경할 수 없다.
const vector<int>::const_iterator citerc; // const 상수 반복자, 위치를 변경할 수 없고, 현재 원소의 값을 변경할 수도 없다.
}
원소의 중간 삽입/삭제
반복자를 이용한다면 vector의 중간에 원소를 삽입하거나 삭제할 수 있다.
insert()는 컨테이너 중간에 원소를 삽입할 때 사용하며, erase()는 컨테이너 중간의 원소를 삭제할 때 사용한다.
insert()는 삽입된 원소의 반복자를 반환하며, erase()는 삭제된 원소의 다음 원소의 반복자를 반환한다.
insert(iter, x); // iter 위치에 x를 삽입한다.
insert(iter, r, x); // iter 위치에 x를 r개 삽입한다.
insert(b, e); // 반복자를 통해 iter 위치에 [b, e] 구간을 삽입한다.
erase(iter); // iter 위치의 원소를 삭제한다.
erase(b, e); // 반복자를 통해 [b, e] 구간의 원소를 삭제한다.
정리
vector는 시퀀스 컨테이너이자, 배열 기반의 컨테이너다.vector의push_back()은 메모리 재할당 및 원소 복사를 동반한다.vector는 임의 접근 반복자를 사용하므로[]을 사용할 수 있다.- 반복자로 값을 변경할 의도가 없다면
const_iterator를 사용한다.