vector는 원소를 자신의 내부 동적 배열에 복사합니다. 이 원소들은 언제나 자기만의 순서를 가집니다.

그러므로 vector는 순서가 있는 컬렉션이죠. vector는 랜덤 엑세스를 지원하므로 모든 원소를 엑세스하는

작업은 상수 시간의 복잡도를 지닙니다. vector의 반복자는 랜덤 엑세스 반복자이기 때문에,

사용자는 STL의 모든 알고리즘을 사용할 수 있습니다.


vector는 끝에 원소를 추가하거나 제거한다면 정말로 놀라운 성능을 보여줍니다.

그러나 데이터를 중간이나 앞부분에 삽입한다면 성능은 매우 저하됩니다. 이유는, 기존의 원소들이

모두 이동되어야 하기 때문이죠. 따라서 할당 연산자는 삽입된 원소 다음에 존재하는 모든 원소에 대해서

호출되어 집니다.



사이즈와 용량

vector의 성능을 더 끌어올리는 방법은 원소를 저장하기 위해서 필요한 메모리보다 더 큰 메모리를 확보해

두는 것입니다. vector를 효율적으로 사용하기 위해서는 사이즈와 용량이 서로 어떻게 작용하는지

잘 알고 있어야 하죠.


vector는 기본적으로 사이즈를 위해 size(), empty(), max_size()들을 제공합니다.

vector의 사이즈와 관련된 추가적인 함수는 capacity()입니다. capacity()는 실제 메모리 안에

vector가 메모리의 재할당 없이 가질 수 있는 원소의 개수를 반환합니다.

만약 capacity()를 초과한다면 vector는 내부 메모리를 재할당해야만 한다.


vector의 용량은 다음의 2가지 이유 때문에 매우 중요합니다.

1. 재할당은 원소의 모든 레퍼런스와 포인터, 반복자를 무효화 시킵니다.

2. 재할당은 시간을 필요로 합니다.


그러므로 사용자가 vector 안의 포인터나 레퍼런스, 반복자를 관리하거나 또는 속도가 목표라면 용량을

먼저 확보하는 것이 매우 중요합니다.


재할당을 피하기 위해서는 reserve()를 사용하면 됩니다. 이 함수는 사용자가 원하는 만큼의 용량을

확보해 줍니다. 이런 방법을 사용함으로써, 모든 레퍼런스들이 유효함을 보장할 수 있습니다.

단, 용량을 초과하지 않는다는 가정하에서 말이죠.

std::vector<int> v; //빈 vector를 생성
v.reserve(80); //80개의 원소를 위해 메모리를 확보

재할당을 피하는 다른 방법은 생성자에 추가적인 인자를 제공하여 vector를 초기화하는 방법입니다.

예를 들어, 생성자의 파라미터로 수치값을 제공한다면, 원소 타입의 디폴트 생성자를 사용하여

수치 값만큼의 원소를 가진 vector를 생성할 것입니다.

물론, 이러한 방식은 주어진 원소가 디폴트 생성자를 제공한다는 사실을 전제로 합니다.

그러나 기억해야 할 점은, 디폴트 생성자가 제공되는 복잡한 타입에 대해서는 초기화에 시간이 걸린다는

사실입니다. 따라서 초기화를 하는 이유가 재할당을 피하려는 것이라면, 반드시 reserve()를 사용해야만 하죠.

vector의 용량에 대한 아이디어는 스트링의 용량에 대한 아이디어와 한 가지를 제외하고는 매우 유사합니다.

vector에서는 스트링과 달리, 용량을 줄이는 목적으로 reserve()를 호출하는 것이 불가능하죠.

현재의 용량보다 적은 값으로 reserve()를 호출하는 것은 아무런 동작도 하지 않습니다.

사실, 메모리의 단편화를 막기 위해서 대부분의 vector의 구현은 사용자가 reserve()를 호출하지 않는 한,

처음에 큰 메모리 블록을 할당합니다. 만약 사용자가 많은 vector를 사용하고 그 안에 적은 원소들만을

가지고 있다면, 이것은 많은 메모리를 낭비하는 것입니다.

vector의 용량은 절대로 줄어들 수 없기 때문에, 원소가 지워진 이후에도 모든 레퍼런스와 포인터,

반복자들은 유효하게 남아 있는 것을 보장합니다. 그러나 삽입은 레퍼런스와 포인터, 반복자들을 무효화하죠.

vector의 용량을 줄일 수 있는 간접적인 방법이 있습니다. 바로 다른 vector와 용량을 교체하는 것입니다.

다음의 함수는 vector의 원소들을 보호하면서 용량을 줄일 수 있습니다.

위의 함수말고도 다음과 같은 구문을 작성함으로써 vector의 용량을 줄일 수 있습니다.

그러나 swap() 이후에 기억해야 할 점은, 모든 레퍼런스와 포인터, 반복자들은 그들의 컨테이너와 같이

교체된다는 것입니다. 즉, 그들은 그들이 참조하였던 원소를 계속해서 참조한다는 것이죠.

그러므로 shrinkCapacity()는 모든 레퍼런스와 포인터, 반복자들을 무효화 시킵니다.