CPP Module 08

개발새발·2022년 7월 19일

42cursus algorithm container iterator

42Cursus

목록 보기

22/29

CPP Module 08

해당 과제를 진행하는데 있어 필요한 사전 지식들을 정리하였습니다.

1. STL

STL이란 Standard Template Library의 약자로 템플릿을 적용한 라이브러리이다. 임의의 타입에 대해 Container, Iterator, Algorithm을 모두 지원한다.

1-1. Conatainer

같은 타입의 여러 객체를 저장하는 일종의 집합과 비슷한 개념이다.
Container의 각 요소에 iterator(반복자)를 통해 접근할 수 있다.
Container내 요소 추가 및 제거를 포함한 다양한 작업을 도와주는 여러 멤버 함수를 포함하고 있다.
STL Container는 크게 세 가지 유형으로 구분된다.
- 1) Sequence Container
  - 데이터를 선형으로 저장하며, 특별한 제약이나 규칙이 없는 가장 일반적인 컨테이너
  - 삽입된 요소의 순서 그대로 유지
  - 명확한 순서가 유지되는 요소들이므로, 특정 위치를 참조하는 연산이 가능해야 함
  - ex) vector, deque, list, forward_list
- 2) Associative Container
  - key와 value처럼 관련 있는 데이터를 하나의 쌍으로 저장하는 컨테이너
  - ex) set, multiset, map, multimap
- 3) Adapter Container
  - 간결함과 명료성을 위해 인터페이스를 제한한 Sequence Container나 Associative Container의 변형
    - Iterator를 지원하지 않으므로 STL Algorithm에서는 사용할 수 없음
    - ex) stack, queue, priority_queue

1-2. Iterator

STL Container에 저장된 요소를 반복적으로 순회하여, 각각 요소에 대한 접근을 제공하는 객체이다.
포인터 개념과 유사하며, 모든 자료구조의 원소에 대한 동일한 접근 방법 제공한다.

1-3. Algorithm

반복자들을 가지고 일련의 작업을 수행한다.
정렬, 삭제, 검색, 연산 등을 해결하는 일반화된 방법을 제공하는 함수 템플릿이다.
ex) sort, swap, find

2. ex00 (Easy find)

여기서 구현해야하는 easyfind라고 하는 함수는 Container에서 특정 값을 찾는 함수이다. easyfind(container T, int N) 형식이며, 두번 째 N이 T에서 처음으로 등장하는 지점을 찾 특정 값을 찾지 못하면 std::exception을 던지거나 에러를 출력한다. Associative Container에 대해서는 다루지 않아도 된다.

std::find 함수를 이용하여 Container의 멤버 함수 begin()과 end()로 범위를 설정해주고 찾아야하는 값을 인자로 넘겨주면 된다. 반환되는 값을 typename T::iterator iter에 넣어주고 만약 iter가 end() 값을 가르키고 있다면 범위 내에 찾는 값이 없다는 뜻이므로 예외를 던진다. Container의 end()는 요소의 마지막 값 다음을 가르킨다.

T::iterator 앞에 typename이 존재하는 이유는 템플릿 매개변수는 타입 또는 값을 받도록 정의할 수 있고, T가 값이든 타입이든 :: 연산자를 통해 내부 요소에 접근하게 되면 내부 요소가 타입인지 값인지 판별하지 못하기 때문에 타입인 경우에는 typename을 명시적으로 기재해야 한다.

3. ex01 (Span)

Span이라는 클래스를 구현해야 하는데 이 클래스는 생성 시 인자로 받은 N만큼의 int형 데이터를 저장할 수 있다. addNumber이라는 멤버 함수를 통해 요소를 추가하는데 이미 요소가 N개만큼 다 찼다면 예외를 발생시킨다.

shortestSpan과 longestSpan이라는 멤버 함수도 구현해야하는데 shortestSpan은 내부 요소의 최소 값과 그 다음 최소 값과의 차이를 의미하고, longestSpan은 내부 요소의 최소 값과 최대 값의 차이를 의미한다. 이를 찾아내기 위해선 <algorithm>의 함수(min_element, max_element, sort 등)를 이용해야 한다. 요소가 하나도 없거나 하나만 있으면 비교할 수 있는 범위가 없으므로 예외를 발생시킨다.

각각의 요소는 std::vector<int>를 이용해 저장하면 된다. 생성 시 크기를 정해야할 때는 reserve 함수의 인자에 크기 N을 전달하면 된다. addNumber 함수는 int 값 하나만 인자로 받아 요소를 추가할 수도 있지만 iterator의 범위를 인자로 받아 한번에 요소를 추가할 수도 있다. 가능케하기 위해선 addNumber 함수를 오버로딩 해야한다.

4. ex02 (Mutated abomination)

Adapter Container인 std::stack은 아쉽지만 iterator를 제공하지 않는다. ex02의 목표는 MutuantStack 클래스 작성을 통해 std::stack에 iterator를 구현하는 것이다.

Container에 정의된 iterator의 종류에는 iterator, const_iterator, reverse_iterator, const_reverse_iterator가 있다.

iterator를 이용하는 함수가 begin과 end, const_iterator를 이용하는 함수가 cbegin과 cend, reverse_iterator를 이용하는 함수가 rbegin과 rend, const_reverse_iterator를 이용하는 함수가 crbegin, crend가 된다.

각각 매치되는 함수를 사용해 4가지 iterator를 구현해주면 된다. 다만 단순히 iterator, const_iterator, reverse_iterator, const_reverse_iterator를 이용하려고 하면, MutantStack<T>에서는 해당 타입들이 무엇인지 모르기 때문에 typedef typename std::stack<T>::container_type::iterator iterator;과 같이 typedef을 통해 별도의 별칭을 정의하여 사용한다.