1-3. std::vector

앞서 살펴본 바와 같이 std::array는 C 스타일 배열의 향상된 버전이다. 

그러나 std::array는 실제 응용 프로그램 개발에서 유용하게 사용할 수 있는 몇몇 기능을 제공하지 않는다는 단점이 있다. 

 

<std::array의 주요 단점>

• std::array의 크기는 컴파일 시간에 결정되는 상수여야 한다. 따라서 프로그램 실행 중에는 변경할 수 없다
• 크기가 고정되어 있어서 원소를 추가하거나 삭제할 수 없다. 
• std::array의 메모리 할당 방법을 변경할 수 없다. 항상 스택 메모리를 사용한다. 

이러한 문제를 std::vector가 해결할 수 있다. 

 

std::vector - 가변 크기 배열

제목에서 알 수 있듯이 std::vector는 C 스타일 배열 또는 std::array가 가지고 있는 가장 두드러진 문제 중 하나인 '고정 크기' 문제를 해결한다. 

std::vector는 초기화 과정에 데이터 크기를 제공하지 않아도 된다. 

 

//크기가 0인 벡터 선언
std::vector<int> vec;

//지정한 초깃값으로 이루어진 크기가 5인 벡터 선언
std::vector<int> vec = {1, 2, 3, 4, 5};

//크기가 10인 벡터 선언
std::vector<int> vec(10);

//크기가 10이고, 모든 원소가 5로 초기화된 벡터 선언
std::vector<int> vec(10, 5);

첫 번째 초기화 코드처럼 벡터는 원소 크기를 지정하지 않고 선언할 수 있다. 

만약 벡터의 크기를 명시적으로 지정하지 않거나 또는 초깃값을 지정하여 크기를 유추할 수 있게 코드를 작성하지 않을 경우, 컴파일러 구현 방법에 따른 용량(capacity)을 갖는 벡터가 생성된다. 

벡터의 크기는 벡터에 실제로 저장된 원소 개수를 나타내는 용어이며, 용량과는 다른 의미이다. 

첫 번째 초기화의 경우, 크기는 0이지만 용량은 0 또는 작은 양수일 수 있다. 

 

std::vector의 원소 삽입

벡터에 새로운 원소를 추가하려면 push_back() 또는 insert() 함수를 사용한다. 

push_back() 함수는 벡터의 맨 마지막에 새로운 원소를 추가한다. 

insert() 함수는 삽입할 위치를 나타내는 반복자를 첫 번째 인자로 받음으로써 원하는 위치에 원소를 추가할 수 있다. 

 

push_back()은 벡터에서 자주 사용되는 연산이며, 매우 빠르게 동작한다. 

push_back()의 동작을 의사코드(pseudocode)로 나타내면 다음과 같다. 

push_back(val):
	if size < capacity  //새 원소를 추가할 공간이 있는 경우
    -마지막 원소 다음에 val 저장
    -벡터 크기를 1만큼 증가
    -return;
	
    if vector is already full  //할당된 메모리 공간이 가득 차 있는 경우
    -2*size 크기의 메모리를 새로 할당
    -새로 할당한 메모리로 기존 원소 전부를 복사/이동
    -데이터 포인터를 새로 할당한 메모리 주소로 지정
    -마지막 원소 다음에 val을 저장하고, 벡터 크기를 1만큼 증가

맨 뒤에 원소를 삽입할 때, 뒤쪽에 남아 있는 공간이 있다면 O(1)의 시간이 걸린다. 

그러나 공간이 충분하지 않으면 모든 원소를 복사/이동해야 하며, 이때는 O(n)의 시간이 걸린다. 

대부분의 구현에서는 용량이 부족할 때마다 벡터 용량을 두 배로 늘린다. 

O(n) 시간 동작은 n개의 원소를 추가한 후에만 발생하며, 이러한 경우는 많지 않으므로 push_back() 연산의 평균 시간 복잡도는 O(1)에 가깝다. 

즉, push_back()은 매우 빠르게 동작하며, 이 때문에 벡터를 많이 사용한다. 

 

insert() 함수의 경우, 지정한 반복자 위치 다음의 모든 원소를 이동시키는 연산이 필요하다. 

필요한 경우 메모리를 새로 할당하는 작업도 수행된다. 

원소들을 이동하는 연산 때문에 insert() 함수는 O(n)의 시간이 걸린다. 

 

//벡터의 맨 앞에 새로운 원소 추가
std::vector<int> vec = {1, 2, 3, 4, 5};
vec.insert(vec.begin(), 0);

std::vector<int> vec;  //비어 있는 벡터 생성 : {}
vec.push_back(1);  //맨 뒤에 1 추가 : {1}
vec.push_back(2);  //맨 뒤에 2 추가 : {1, 2}
vec.insert(vec.begin(), 0);  //맨 앞에 0 추가 {0, 1, 2}
vec.insert(find(vec.begin(), vec.end(), 1), 4); // 1 앞에 4 추가 : {0, 4, 1, 2}

 

push_back() 또는 insert() 함수와 비교하여 좀 더 효율적인 원소 추가 방법에 대해 알아보자. 

push_back() 또는 insert() 함수의 단점 중 하나는 이들 함수가 추가할 원소를 먼저 임시로 생성한 후, 벡터 버퍼 내부 위치로 복사 또는 이동을 수행한다는 점이다. 

이러한 단점은 새로운 원소가 추가될 위치에서 해당 원소를 생성하는 방식으로 최적화할 수 있으며,

이러한 기능이 emplace_back() 또는 emplace() 함수에 구현되어 있다. 

그러므로 push_back()과 insert() 같은 일반적인 삽입 함수 대신 emplace_back() 또는 emplace() 함수를 사용하는 것이 성능 향상에 도움이 된다. 

 

이 경우 새 원소 위치에서 곧바로 객체가 생성되기 때문에 이들 함수 인자에 생성된 객체를 전달하는 것이 아니라 생성자에 필요한 매개변수를 전달해야 한다. 

그러면 emplace_back() 또는 emplace() 함수가 전달된 생성자 인자를 적절하게 사용하여 객체를 생성하고 삽입한다. 

 

std::vector의 원소 제거

std::vector는 원소 제거를 위해 pop_back()과 erase() 함수를 제공한다. 

pop_back() 함수는 벡터에서 맨 마지막 원소를 제거하며, 그 결과 벡터 크기는 1만큼 줄어든다. 

 

erase() 함수는 두 가지 형태로 오버로딩 되어 있다. 

1. 반복자 하나를 인자로 받아 해당 위치 원소를 제거
2. 범위의 시작과 끝을 나타내는 반복자를 받아 시작부터 끝 바로 앞 원소까지 제거한다(시작 위치 원소는 제거되지만 끝 위치 원소는 제거되지 않는다)

erase()와 pop_back() 함수 동작 시 c++ 표준에서는 벡터의 용량이 감소할 필요가 없지만, 컴파일러 구현에 따라 달라질 수 있다. 

 

pop_back() 함수는 남아 있는 위치를 조정할 필요가 없으므로 매우 빠르게 동작하고, 시간 복잡도는 O(1)이다. 

그러나 erase() 함수는 특정 위치 원소를 삭제한 후, 뒤쪽의 원소들을 모두 앞으로 이동해야 하기 때문에 O(n)의 시간이 소요된다. 

 

	시간복잡도
push_back(), pop_back()	O(1)
insert(), erase()	O(n) - 특정 위치 원소를 삽입/삭제 후 이동시켜야 하기 때문

 

 

std::vector<int> vec = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

//맨 마지막 원소 하나를 제거한다 : {0, 1, 2, 3, 4, 5, 6, 7, 8}
vec.pop_back();

//맨 처음 원소를 제거 : {1, 2, 3, 4, 5, 6, 7, 8}
vec.erase(vec.begin());

//1번째 원소부터 4번째 앞 원소까지 제거한다 : {1, 5, 6, 7, 8}
vec.erase(vec.begin()+1, vec.begin()+4);

 

몇 가지 유용한 std::vector 멤버 함수

• clear() : 모든 원소를 제거하여 완전히 비어있는 벡터로 만든다
• reserve(capacity) : 벡터에서 사용할 용량을 지정한다. 매개변수로 지정한 값이 현재 용량보다 크면 매개변수 크기만큼 재할당한다. 매개변수 값이 현재 용량보다 같거나 작으면 아무런 동작을 하지 않는다. 이 함수는 벡터의 크기를 변경하지는 않는다.
• shrink_to_fit() : 여분의 메모리 공간을 해제하는 용도로 사용된다. 이 함수를 호출하면 벡터의 용량이 벡터 크기와 같게 설정된다. 벡터 크기가 더 이상 변경되지 않을 때 사용하면 유용하다. 

결론

std::vector는 std::array에 대한 정말 좋은 대안이고, 크기, 증분 등의 관점에서 더욱 많은 유연성을 제공한다. 

배열과 벡터에서 공통으로 제공하는 기능은 서로 같은 점근적 시간 복잡도를 갖는다. 

다만 추가적인 기능에 대해서는 합리적인 수준의 추가 연산 비용이 필요하다.

평균적으로 벡터의 성능은 배열에 비해 그리 나쁘지 않다. 

그러므로 std::vector는 성능과 유연성으로 인해 실전에서 널리 사용되는 STL 컨테이너 중 하나이다.