1장 리스트, 스택, 큐 - std::vector

C스타일의 배열이 향상된 버전인 std::array에는 단점이 존재한다.

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

이러한 문제를 해결하기 위해 std::array 사용할 수 있다.

 

가변 크기 배열

std::array는 C스타일 배열, std::array가 가지고 있는 고정 크기 배열 문제를 해결할 수 있다.

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

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

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

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

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

만약 벡터의 크기를 명시적으로 지정하지 않는 경우, 컴파일러 구현 방법에 따른 용량(capacity)을 갖는 벡터가 생성된다. 벡터의 크기는 벡터에 실제로 저장된 원소의 개수를 나타내는 용어이며, 용량과 다른 의미이다.

 

벡터에 새로운 원소를 추가하는 방식은 push_back(), insert()가 있다.

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

insert(): 삽입할 위치를 나타내는 반복자를 첫번째 인수로 받아 원하는 위치에 원소를 추가한다.

 

push_back()의 의사코드는 다음과 같다.

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

맨 뒤의 원소를 삽입할 때 뒤 쪽에 공간이 남아있다면 O(1)의 시간이 걸린다. 그러나 공간이 충분하지 않는다면 모든 원소를 복사, 이동해야하며 이때 O(n)의 시간이 걸린다. 대부분의 구현에서 용량이 부족할 때마다 벡터의 용량리 두 배로 늘어나는데 O(n)의 시간 동작은 n개의 원소를 추가한 후에만 발생되기 떄문에 이러한 경우가 많지 않다. 그러므로 push_back()의 평균 시간복잡도는 O(1)에 가깝다.

 

insert() 함수의 경우 지정한 반복자 위치 다음의 모든 원소를 이동시키는 연산이 필요하기 때문에 필요한 경우 메모리를 새로 할당하는 작업도 수행된다. 원소를 이동시키는 연산 때문에 insert() 함수는 O(n)의 시간이 걸린다.

std::vector<int> vec = {1, 2, 3, 4, 5};

//벡터의 맨 앞에 새로운 워소를 추가
vec.inset(vec.begin(), 0);

//1앞에 4추가
vec.insert(find(vec.begin(), vec.end(), 1), 4);

 

push_back(), insert() 함수의 경우 추가할 원소를 먼저 임시로 생성한 후에 벡터 버퍼 내부 위치로 복사 또는 이동을 수행한다. 이러한 단점은 새로운 원소가 추가될 위치에서 해당 원소를 생성하는 방식으로 최적화할 수 있으며, 이러한 기능이 emplace_back() 또는 emplace() 함수에 구현되어 있다. 이 경우 새 원소 위치에 곧바로 객체가 생성되기 때문에 이들 함수 인자에 생성된 객체를 전달하는 것이 아니라 생성자에 필요한 매개변수를 전달해야 한다. 그러면 emplace_back() 또는 emplace() 함수가 전달된 생성자 인자를 적절하게 사용하여 객체를 생성하고 삽입한다.

 

벡터에 원소 제거를 위해 pop_back(), erase() 함수를 제공한다.

pop_back(): 벡터의 맨 마지막 원소를 제거하며, 벡터의 크기를 1만큼 줄인다.

erase(): 두 가지 형태로 오버로딩 되어있다. 한 가지의 형태는 반복자 하나는 인자로 받아 해당 위치 원소를 제거하고, 다른 형태는 범위의 시작과 끝을 나타내는 반복자를 받아 시작과 끝 바로 앞 원소까지를 제거한다. 즉, 시작위치의 원소는 제거되고 끝 위치의 원소는 제거되지 않는다.

 

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

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

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

//맨 마지막 원소를 제거
vec.pop_back();

//맨 처음의 원소 제거
vec.erase(vec.begin());

//1번째 원소부터 4번째 원소까지 제거
vec.erase(vec.begin() + 1, vec.begin() + 4);

 

추가로 유용한 std::vector멤버 함수를 소개하겠다.

clear(): 모든 원소를 제거하여 완전히 비어있는 벡터로 만든다.

reserve(capacity): 벡터에서 사용할 용량을 지정한다. 매개변수로 지정한 값이 현재 용량보다 크면 메모리를 매개변수 크기만큼 재할당한다. 매개변수 값이 현재 용량보다 같거나 작으면 아무런 동작을 하지 않는다. 이 함수는 벡터의 크기를 변경하지는 않는다.

shrink_to_fit(): 여분의 메모리 공간을 해제하는 용도로 사용한다. 이 함수를 호출하면 벡터의 용량이 벡터 크기와 같게 설정된다. 벡터의 크기가 더 이상 변경되지 않을 때 사용하면 유용하다. 

 

할당자

std::vector는 템플릿 매개변수에서 데이터 타입 다음에 할당자(allocator)를 전달할 수 있다.

사용자 정의 할당자를 사용하려면 정해진 인터페이스를 따라야한다. 벡터는 메모리 접근과 관련된 대부분의 동작에서 할당자 함수를 사용하므로 할당자는 allocate(), dellocate(), construct(), destroy() 등의 함수를 제공해야한다.

할당자는 메모리 할당과 해제, 그리고 여타 동작에서 데이터를 손상시키지 않도록 주의해야한다.