컨테이너 종류

Sequence containers

array : 배열
vector : 배열과 비슷하지만 삽입, 추가, 삭제 등 크기 조절이 가능
deque : 양쪽으로 자료를 추가, 삭제
list : 이중 연결 리스트

연관 컨테이너(Associative Containers)

set : 유일 키를 갖는 트리구조
map : 유일 키와 값을 갖는 트리구조
multiset : 중복 키를 갖는 트리구조
multimap : 중복 키와 값을 갖는 트리구조

해시 컨테이너(Unordered Associative Containers)

unordered_set : 유일 해시 키를 갖는 해시 구조
unordered_map : 유일 해시 키와 값을 갖는 해시 구조
unordered_multiset : 중복 해시 키를 갖는 해시 구조

컨테이너 어댑터(Container Adapters)

stack : dequeu에서 만들어진 후입선출 자료구조
queue : dequeu에서 만들어진 선입선출 자료구조

구현

iterator를 구현할 때는 동작에 대한 구현이라고 보고 접근하면 좋다. 실제 어디서부터 움직일것인가 하는 것은 자료구조 자체에서 결정되기 때문.

iterator template

iterator에는 5가지 종류가 있음.

Input iterator : 전진만 가능, 한번에 하나만 읽기
Output iterator : 전진만 가능, 한번에 하나만 쓰기
Foward iterator : 전진만 가능, 한번에 여러개 읽고 쓰기
Bidirectional iterator : 전/후진 가능, 한번에 여러개 읽고 쓰기
Random access iterator : 반복자를 임의의 위치만큼 전/후진 가능

하지만 함수 템플릿에 iterator를 대입하는 경우 이것이 어떤 iterator인지, 정수형은 아닌지에 대해 컴파일러가 구분을 할 수 있게 해줘야 한다.
예를 들어 std::accumulate(InputIt first, InputIt last, T init)에는 범위를 iterator로 주게 된다. 하지만 iterator가 어떤 자료형을 가리키고 어떤 특성을 가리키는 지는 함수에서 단순한 방법으로는 알 수 없다. 그래서 필요한 것이 iterator_traits다.

iterator_traits

iterator는 5가지 종류가 있다. iterator_traits는 STL의 iterator는 제각기 다르기 때문에 일관된 이름을 갖지만 각 iterator의 특성을 반영하는 템플릿이다.

template<typename Iterator>
struct iterator_traits {
	typedef typename Iterator::difference_type		difference_type;
	typedef typename Iterator::value_type			value_type;
	typedef typename Iterator::pointer				pointer;
	typedef typename Iterator::reference			reference;
	typedef typename Iterator::iterator_category	iterator_category;
};

이때 typedef는 nested dependent type name에 대해 컴파일러에게 구분을 제공하는 한정자이다.
아울러 iterator는 포인터를 흉내내도록 정의되지만, vector등과 같이 실제 포인터를 그대로 차용하는 경우가 있으므로 포인터 타입에 대한 template specialization을 해줘야 한다.

template<typename T>
struct iterator_traits<T*> {
	typedef std::ptrdiff_t						difference_type;
	typedef T									value_type;
	typedef T*									pointer;
	typedef T&									reference;
	typedef std::random_access_iterator_tag		iterator_category;
};

reverse_iterator

iterator_traits를 기반으로 reverse_iterator를 구현한다. 물리적인 순서와 논리적인 순서가 1칸씩 다르고, 이를 보정하는 개념이 base(), 즉 물리적인 순서이다.
아래 사이트에 잘 설명돼 있다.
https://en.cppreference.com/w/cpp/iterator/reverse_iterator

enable_if 와 is_integral

enable_if는 is_integral과 함께 iterator인지 아닌지에 대한 구분을 컴파일러에게 제공해준다.
is_integral은 <type_traits>에 정의된 것들중 하나다.

		...
        
    // Primary classification traits:
    template <class T> struct is_void;
    template <class T> struct is_null_pointer;  // C++14
    template <class T> struct is_integral;
    template <class T> struct is_floating_point;
    template <class T> struct is_array;
    template <class T> struct is_pointer;
    template <class T> struct is_lvalue_reference;
    template <class T> struct is_rvalue_reference;
    template <class T> struct is_member_object_pointer;
    template <class T> struct is_member_function_pointer;
    template <class T> struct is_enum;
    template <class T> struct is_union;
    template <class T> struct is_class;
    template <class T> struct is_function;
    
		...

rebind

std::allocator에서 사용되는 개념이다. 예를 들어 vector<int>는 단순히 int형 만큼의 메모리 할당 뿐 아니라 int형을 감싸고 있는 자료구조 자체에 대한 메모리도 할당 돼야 한다. 이를 해결해 주는 개념이 rebind다.

resize vs reserve

stl에서 size()란 실제 원소들이 얼만큼 들어있는가를 말하며, capacity()는 해당 stl을 위해 얼마만큼의 메모리가 할당되었는가를 나타낸다. 따라서 resize()는 실제 요소들의 수를 조정한다는 것이고, reserve()는 메모리 할당을 다시 한다는 것이다.

RB Tree

맵과 셋 구현에 필요한 자료구조. AVL트리로도 구현이 가능하다. 레드블랙 트리는 인터넷에 좋은 자료들이 많이 있으므로 생략
레드블랙 트리의 동작을 시각화한 사이트:
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

생성자에 explicit 키워드

만약 생성자에 explicit 키워드를 붙이지 않는다면 다음과 같은 의도치 않은 오류가 날 수 있다.

std::allocator<int> a;

ft::vector<int> v = a; // Implicit conversion from std::allocator<int> to vector<int>