ft_containers 개념정리

개발새발·2022년 8월 5일

42cursus iterator

42Cursus

목록 보기

24/29

ft_containers

본 프로젝트의 개요와 프로젝트를 진행하기 위한 개념 확립

1. TMP (Template Meta Programming)

템플릿을 사용하면 객체를 생성하지 않더라도 타입에 대한 어떠한 값을 부여할 수 있고, 또 그 타입들을 가지고 연산을 할 수가 있다. 또한 타입은 반드시 컴파일 타임에 확정되어야 하므로, 컴파일 타임에 모든 연산이 끝나게 된다. 이렇게 타입만 가지고 컴파일 타임에 생성되는 코드로 프로그래밍하는 것을 메타 프로그래밍이라고 하고, C++의 경우에는 템플릿을 가지고 이러한 작업을 하기 때문에 템플릿 메타 프로그래밍이라고 부른다.

2. STL (Standard Template Library)

C++을 위한 라이브러리로서 C++ 표준 라이브러리의 많은 부분에 영향을 미쳤다.
Algorithm, Container, Functor, Iterator 라고 불리는 네 가지의 구성 요소를 제공한다.
STL은 결과를 템플릿의 사용을 통해 달성한다. 이 접근법은 전통적인 런타임 다형성에 비해 훨씬 효과적인 컴파일 타임 다형성을 제공한다.

3. Container

3-1. Sequence Container (순차 컨테이너)

vector (Mandatory Part)
- C 배열과 같은 동적 배열로서 객체를 삽입하거나 제거할 때 자동으로 자신의 크기를 조정
deque
list

3-2. Conatainer Adapter (컨테이너 어댑터)

stack (Mandatory Part)
- LIFO 구조로 제일 마지막에 넣은 데이터가 제일 처음으로 나옴
queue
priority_queue

3-3. Associative Container (연관 컨테이너)

map (Mandatory Part)
- 각 노드가 key와 value 쌍으로 이루어진 트리 (RB tree)
- key 값의 중복을 허용하지 않음
multimap
set (Bonus Part)
- 노드 기반 컨테이너
- 균형 이진 탐색 트리로 구성 (RB tree)
- key라고 불리는 원소들의 집합
- key 값의 중복을 허용하지 않음
multiset
bitset

pair : 간단한 연관 컨테이너로서 데이터 요소의 2-tuple 또는 객체들로 이루어짐 (클래스 템플릿)
make_pair : 두 개의 인자를 받아 pair 객체를 생성 (함수 템플릿)

4. Iterator

4-1. Iterator definitions

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

4-2. Iterator categories

input iterator
- 단지 값들의 시퀀스를 읽는데 사용
- 전진만 가능
- 하나만 읽기 가능
output iterator
- 단지 값들의 시퀀스를 쓰는데 사용
- 전진만 가능
- 하나만 쓰기 가능
forward iterator
- 읽어지고 쓰여지며 앞으로 움직일 수 있음
- 전진만 가능
- 한 번에 여러 개 읽고 쓰기 가능
bidirectional iterator
- forward iterator와 같지만 뒤로도 움직일 수 있음
- 전후진 가능
- 한 번에 여러 개 읽고 쓰기 가능
random access iterator
- 한 연산에서 어떤 수만큼이라도 자유롭게 움직일 수 있음
- 임의의 위치만큼 전후진 가능

즉, iter += dist는 random access iterator 아니면 적용이 불가능하다. 또한 후진이 불가능한 iterator에 대해 음수의 dist가 넘어올 때 적절한 예외처리가 필요하다.

4-3. Iterator traits

Traits class란 컴파일 도중에 어떤 주어진 타입의 정보를 얻을 수 있게 하는 객체이다. 템플릿 클래스나 함수에서 여러 타입에 대해 각기 다르게 처리를 해줘야 하는 상황에서 컴파일 타임에 타입들을 구분하기 위해 사용하는 것이다.

Iterator traits 클래스는 타입을 구분할 수 있는 tag 구조체를 활용한다. 이를 반복자 범주를 두 부분으로 나누어 구현한다.

사용자 정의 타입으로 하여금 iterator_category라는 이름의 타입을 내부에 가질 것을 요구한다.
예를 들어, list의 경우 bidirectional_iterator_tag를 iterator_category로 typedef한다.
사용자가 정의한 타입을 똑같이 가진 iterator_traits 구조체를 정의한다. 또한 struct iterator_traits 기본 제공 타입에 대해서도 특성 정보를 사용할 수 있도록 부분 특수화 버전을 만들어준다.
각 iterator를 사용하는 곳에서 iterator_category를 typedef하고 있다. 또한 iterator_traits 구조체는 넘어온 iterator::iterator_category 타입을 자신의 iterator_category로 typedef하고 있다.

5. Algorithm

STL에서 제공되는, 검색이나 정렬 같은 작업을 수행하는 알고리즘 대부분은 각각 반복자(iterator)의 특정한 수준을 요구한다.
이 반복자들을 가지고 일련의 작업을 수행한다.
정렬, 삭제, 검색, 연산 등을 해결하는 일봔화된 방법을 제공하는 함수 템플릿이다.

equal : 두 원소의 나열들이 일치하는지 확인
lexicographical_compare : 사전적 크기 비교 수행

6. SFINAE

C++11 표준의 14.8.2 조항에 따르면 템플릿 인자 치환에 실패할 경우 컴파일러는 이 오류를 무시하고 그냥 오버로딩 후보에서 제외하면 할 수 있다. C++에서는 이를 SFINAE - Substitution Failure Is Not An Error(치환 실패는 오류가 아니다)라고 한다.

SFINAE를 잘 활용하는 툴 중 가장 널리 쓰이는 것이 바로 enable_if이다. enable_if는 템플릿들을 위한 컴파일 타임 스위치이며 이게 없으면 오버로딩 함수들이 무분별하게 오버로딩 될 수 있다.

예제

template <typename T>
class vector
{
	vector(size_type n, const T val);
    
    template <class InputIterator>
    vector(InputIterator first, InputIterator last);
};

위와 같이 두 가지 형태의 두 개의 인자를 받는 생성자가 있고 std::vector<int> v(2, 4);로 vector를 생성했을 때, 프로그래머는 첫 번째 생성자를 의도한 것이겠지만 실제로는 두 번째 생성자가 호출된다. 왜냐하면 size_type이 대개 unsigned로 있지만, 2의 경우 그냥 sign이므로 더 잘 맞는 후보군은 두 번째 것이 되기 때문이다. 따라서 enable_if를 이용해서 InputIterator가 정말로 반복자일 때만 오버로딩 될 수 있도록 제한해야 한다.

7. Allocator와 Rebind

STL allocator를 제작할 때, 표준 컨테이너에서 필요로 하는 rebind라는 중첩 구조체 템플릿을 반드시 제공해야 한다. 예를 들어, set은 단순히 <T>를 저장하는 컨테이너가 아니라 <T> 타입 데이터를 포함한 노드 구조체를 저장하는 컨테이너이다.

하지만 allocator에 넘긴 템플릿 매개변수는 <T>인데 이것만으로 allocator 함수를 호출한다면 딸랑 <T>의 크기만큼의 바이트만 할당이 될 것이다.

이렇듯 해당 템플릿 매개변수 <T> 타입의 컨테이너 allocator는 <T> 타입이 아닌 해당 컨테이너에서 요구되는 진정한 할당 타입의 allocator가 필요하다.

이와 같은 요구사항을 충족하기 위해 STL allocator는 반드시 rebind 중첩 구조체 템플릿을 가져야 한다.

References
https://www.cplusplus.com/reference/
https://modoocode.com/255
https://modoocode.com/174
https://modoocode.com/221
http://egloos.zum.com/sweeper/v/3007176
http://egloos.zum.com/sweeper/v/2966785
https://ko.wikipedia.org/wiki/%ED%91%9C%EC%A4%80_%ED%85%9C%ED%94%8C%EB%A6%BF_%EB%9D%BC%EC%9D%B4%EB%B8%8C%EB%9F%AC%EB%A6%AC