4.1 vector 구현

이제 STL의 vector를 모델로 정의한 vector를 구현합시다.

vector에는 자료를 보관하는 저장소를 동적으로 생성하여 자료를 관리합니다. 자료를 보관할 저장소의 위치 정보를 기억할 멤버 필드를 추가하세요.

저장소의 크기를 기억할 멤버를 추가하세요.

저장소의 크기를 기억할 멤버를 추가하세요.

보관한 자료 개수를 기억할 멤버를 추가하세요.

배열에 보관한 자료를 순차적으로 탐색할 수 있는 반복자를 구현합시다.

현재 탐색할 위치를 기억할 멤버 필드를 추가하세요.

생성자를 정의합시다.  반복자에서 가리킬 데이터 정보를 입력 인자로 받게 하며 디폴트 매개변수 값을 0으로 지정하세요.

입력 인자로 전달받은 위치를 멤버 필드에 설정하세요.

반복자는 간접 연산을 통해 보관한 개체를 접근할 수 있게 합시다.

보관하거나 삭제할 때 상대적 거리로 저장소에 접근할 필요가 있어요. 이를 위해 -연산을 제공하세요.

전위 증가 연산은 자신을 증가한 뒤에 자신을 반환하세요.

후위 증가 연산은 자신을 복제한 후에 자신의 위치를 증가한 후에 복제한 값을 반환하세요.

비교 연산은 가리키는 위치가 같은지 여부로 판변합니다.

생성자에서는 저장소가 없는 상태이며 저장소의 크기와 보관 개수가 0인 상태로 설정하세요. 실제 vector는 여기서 구현하는 것보다 훨씬 복잡합니다.

소멸자에서는 저장소가 유효하면 저장소를 소멸하세요.

resize 메서드는 첫 번째 인자 개수만큼 vector에 자료를 보관한 상태로 변경하는 메서드입니다. 이미 보관 중인 자료를 제외한 나머지는 두 번째 인자로 전달받은 값으로 설정합니다. 먼저 nsize가 저장소의 크기보다 크면 저장소를 확장하며 이 부분은 별도의 메서드로 정의합시다. 그리고 보관 개수가 nsize가 될 때까지 data를 순차보관하세요.

저장소의 크기를 배정하는 reserve 메소드를 정의합시다.

먼저 입력 인자로 전달받은 크기의 저장소를 생성하고 저장소의 크기를 변경하세요.저장소의 크기 배정

보관한 자료가 있으면 보관한 개수만큼 새로 생성한 버퍼에 복사하고 기존 저장소를 소멸하세요.기존 저장소의 보관 데이터 복사 후에 기존 저장소 소멸

base에 새로운 저장소를 대입하세요.

순차 보관은 맨 뒤에 보관하는 것입니다. vector에서는 탐색하기 위해 시작 반복자와 끝 반복자를 구하는 메서드를 제공합니다. 여기서 시작 반복자는 저장소의 시작 위치이며 끝 반복자는 마지막 자료를 보관한 다음 위치입니다.

시작 반복자 위치부터 끝 반복자 위치가 나올 때까지 반복하여 탐색하게 작성하였으며 끝 반복자는 탈출 조건을 위해 만든 것입니다. 따라서 끝 반복자는 실제 마지막 자료를 보관한 위치가 아니라 그 다음 위치입니다. 따라서 맨 뒤에 보관하는 것은 end() 앞에 data를 보관하면 되겠죠.vector 버퍼의 구조와 begin(), end()

특정 위치에 보관하는 insert 메서드를 구현합시다.

꽉 차면 저장소의 크기를 늘려야 합니다. 반복자는 이전 저장소에 자료를 저장한 위치여서 저장소를 확장하면 기존에 위치 정보는 아무런 가치가 없습니다. 따라서 입력 인자로 전달받은 반복자의 위치가 저장소와의 상대적 거리를 계산하세요.

특정 위치에 자료를 지우는 기능입니다. 여기에서 할 일은 보관한 자료의 개수를 1 줄이는 것 뿐만 아니라 지울 위치 뒤에 있는 자료들을 한 칸씩 앞으로 당기는 작업을 수행합니다.

먼저 보관한 자료를 줄이세요. 그리고 입력 인자로 전달받은 반복자의 상대적 위치를 구하세요. 그리고 인덱스가 보관한 자료 개수보다 작으면 인덱스 뒤에 자료를 인덱스 위치에 복사하는 것을 반복하세요.

vector의 erase 동작 원리

인덱스 연산을 구현합시다. 인덱스 연산은 대입 연산자 왼쪽에 올 수 있어야 하기 때문에 값을 반환하지 않고 보관한 자료 자체를 반환하기 위해 참조 형식으로 반환하게 정의하였습니다.

상수화 메서드에서 접근할 수 있는 인덱스 연산자도 같은 원리로 구현하세요.

탐색에 사용할 시작 반복자를 구하는 begin에서는 저장소의 위치를 갖는 반복자를 반환합니다.

탐색에 사용할 끝 반복자를 구하는 end는 base+bsize를 갖는 반복자를 반환합니다. 끝 반복자는 탐색 반복문에서 탈출 조건으로 사용할 것이므로 맨 뒤에 보관한 다음 위치를 반환하는 것입니다.

상수화 메서드에서 사용하기 위한 메서드도 구현은 같습니다.

보관한 원소 개수를 구하는 기능을 구현하세요.

저장소의 크기를 구하는 기능을 구현하세요.

 

이번에는 find_if 알고리즘을 구현합시다.

이제 3장에서 STL에서 제공하는 vector를 사용했던 프로그램에서 여기서 만든 vector와 find_if를 사용하게 헤더 파일 포함문과 using 문을 변경하여 테스트 해 보세요.

이처럼 내부를 파헤치는 작업을 internal이라 부릅니다. 보통 internal 작업은 만드는 것이 목적이 아니라 내부를 이해하기 위한 것입니다. 지금처럼 비슷하게 구현할 수도 있지 논리적으로 분석할 수도 있겠죠.