subject
subject.pdf
과제 목표
STL에 있는 컨테이너 만들기
로드맵
{ 1phase / container 의 필수 요소 감잡기 but 이단계에선 내가 뭘 만드는지 모르는게 당연 } // 권장 학습 기간 2~3일
0. 사전 지식 공부 - SFINAE와 enable_if, allocator, is_integral, iterator traits 등
1. // type traits - enable_if, is_integral 들 구현
2. iterator traits
3. algorithm - equal, lexicographical_compare
4. pair
{ 2phase / 위에서 만든걸 써먹으면서 이해도 높이기 } // 권장 학습 기간 2일
5. random access iterator
6. reverse iterator
{ 3phase / 위에서 만든걸 사용하면서 컨테이너를 직접 구현 } // 권장 학습 기간 3일
7. vector 구현
8. vector 구현 이후 adaptor container 로 stack 구현
{ 4phase / map에 대해 공부하고 tree를 구현할 준비 } // 권장 학습 기간 2일
9. tree node
10. tree iterator
{ 5phase / map 구현 } // 권장 학습 기간 3일
11. map -> set (인터페이스만 구현)
12. red black tree 이나 avl tree 로직을 사용하여 트리 구현 (내부로직 구현)
/* 참고사항
- 대부분 구현해야할 것들은 cppreference.com 이나 cplusplus.com 에서 확인 가능
*/
Plain Text
복사
C++은 제너릭한 프로그래밍을 위해 template을 지원한다. template이란 함수나 클래스를 다양한 자료형으로 사용할 수 있도록 만든 틀이다. 또한 이런 template을 이용한 라이브러리를 Standard Template Library라고 한다.
•
임의 타입의 객체를 보관할 수 있는 컨테이너 (container)
•
컨테이너에 보관된 원소에 접근할 수 있는 반복자 (iterator)
•
반복자들을 가지고 일련의 작업을 수행하는 알고리즘 (algorithm)
STL은 보통 이 세 개의 라이브러리를 의미한다.
이 STL의 container를 구현하는 것이 이 과제의 주제이고, 이를 위해 필요한 iterator와 algorithm등을 구현해야 한다.
사전 지식인 enable_if, SFINAE를 공부하려고 검색했을 때 나오는 코드는 아래와 같은 형태이다.
struct T {
enum { int_t, float_t } type;
template <typename Integer,
std::enable_if_t<std::is_integral<Integer>::value, bool> = true
>
T(Integer) : type(int_t) {}
template <typename Floating,
std::enable_if_t<std::is_floating_point<Floating>::value, bool> = true
>
T(Floating) : type(float_t) {} // OK
};
C++
복사
멘탈 바사삭… 도대체 뭔소린지 하나도 모르겠다.
우선 enable_if 와 is_integral은 c++ 11 버전의 기능이지만, 과제에서는 구현하라고 되어 있기 때문에 우선 찾아보자.
우선 SFINAE는 링크 로 대충 개념만 감을 잡았다. 예를 들어, value_type이라는 멤버타입을 가지고 있는 클래스가 입력되어야 하는 템플릿에서, int 등의 자료형이 들어왔을 때 오류를 뱉어내는 것이 아니라 그냥 오버로딩 후보에서 제외시키는 것이다.
물론 int를 받을 수 있는 함수가 아예 없으면 당연히 no matching error가 나지만, 여기서 오류가 아니라는 뜻은 ‘컴파일러가 컴파일 과정에서 template 함수를 확인하는 과정에서 오류가 나지 않는다' 는 것이다.
#include <iostream>
int negate(int i) {
std::cout << "int" << std::endl;
return -i; }
template <typename T>
typename T::value_type negate(const T& t) {
std::cout << "SFINAE" << std::endl;
return -T(t);
}
int main()
{
negate('c');
}
C++
복사
위의 코드를 실행하면, 출력은 int 가 나오게 된다. char 자료형인 c 가 함수에 적용되어야 하는데, value_type이 없기 때문에 typename T::value_type negate(const T& t) 템플릿에는 적용되지 않는다. 하지만 SFINAE로 인해 오류가 나지 않고 오버로딩 후보에서 제외되어 char 자료형이 int 자료형으로 변환되어 int negate(int i) 함수가 실행된다.
하지만 위의 template 함수를 아래 코드로 변경하여 실행하면 컴파일 오류가 발생한다.
#include <iostream>
int negate(int i) {
std::cout << "int " << std::endl;
return -i; }
template <typename T>
void negate(const T& t) {
typename T::value_type n = -t();
}
int main()
{
negate('c');
}
C++
복사
이 코드는 컴파일 단계에서 error: type 'char' cannot be used prior to '::' because it has no members 에러를 뱉는다. char 자료형에는 멤버가 없기 때문에 :: 을 통한 접근이 불가능하다는 이야기이다. 즉, 컴파일단계에서 template 함수에 char 를 넣어보는 과정에서 오류가 발생한 것이다. 이 경우는 SFINAE가 적용되지 않은 것이다.
왜냐하면 T::value_type는 함수 타입과 템플릿 타입 인자의 즉각적인 맥락(immediate context) 바깥에 있기 때문입니다. 따라서 표준 규정에 따라 이는 SFINAE 의 적용 범위를 넘어섭니다. -모두의 코드
따라서 우리가 쓸데 없는 컴파일 오류를 뱉지 않게 하려면, 함수 내부가 아닌 함수의 선언부에 타입을 넣어야 ‘치환실패로 인한 컴파일 후보 제외' 만 일어나고 ‘컴파일 오류' 는 일어나지 않게 된다. 이런 SFINAE를 잘 사용하는 툴 중 하나가 바로 enable_if 이다.
template <bool, typename T = void>
struct enable_if {};
template <typename T>
struct enable_if<true, T> {
typedef T type;
};
C++
복사
enable_if 는 다음과 같이 정의할 수 있다. 여기부터 또 헷갈린다.
우선, C++에서 struct와 class 는 같다고 볼 수 있다. 그래서 struct를 클래스라고 칭하는 블로그나 레퍼런스도 있음!
template <bool, typename T = void> struct enable_if {};
에서 typename T = void 는 자료형이 안들어오면 void라고 한다는 뜻!
enable_if 에 자료형으로 true, T 가 들어오면 T 형식의 type이 생긴다. 따라서,
template <class T>
typename std::enable_if<std::is_integral<T>::value, bool>::type
is_odd (T i) {return bool(i%2);}
C++
복사
is_integral<T>::value 가 true 이면 enable_if에 type이라는 bool자료형의 타입이 생기기 때문에 위의 코드가 컴파일이 가능하다. 하지만 만약 is_integral 에 들어간 자료형 T가 false, 즉 정수형이 아닌 자료형이라면 enable_if에서 type이라는 멤버타입이 생기지 않기 때문에 컴파일 에러가 뜬다.
그리고 우리는 is_integral 역시 구현해야 한다.
template <class T> struct is_integral;
C++
복사
is_integral은 자료형 T가 정수 유형인지 식별하는 클래스이다.
T 가 정수 유형인지에 따라 integral_constant 를 true_type 혹은 false_type으로 상속받는다.
template <class T, T v> struct integral_constant {
static constexpr T value = v;
typedef T value_type;
typedef integral_constant<T,v> type;
constexpr operator T() { return v; }
};
C++
복사
우선, 처음보는 저 constexpr 에 대해 알아보자.
11버전부터 쓰는 표현인가보다.
근데 어차피 우리가 쓰려는 기능 내에서는 저 constexpr 이 붙은 멤버를 다 빼도 큰 문제가 없다고 한다… (jseo님은 constexpr을 const 로 했다고 한다.)
근데 다시 보니 위의 enable_if 예시에서 template <class T> typename std::enable_if<std::is_integral<T>::value, bool>::type is_odd (T i) {return bool(i%2);} 으로 is_integral의 type을 사용한다. 그러면 멤버타입 value 는 static const 로 넣어야 할 것 같다.
그럼 이제 integral_constant 가 다음과 같은 형식이 된다.
template <class T, T v> struct integral_constant {
static const T value = v;
typedef T value_type;
typedef integral_constant<T,v> type;
};
C++
복사
v 로 초기화된 static const T 형식의 value, T 형식의 value_type과 integral_constant 형식의 type을 가진다.
typedef integral_constant<bool, true> true_type;
typedef integral_constant<bool, false> false_type;
C++
복사
integral_constant 에 bool, true 가 들어간 클래스를 true_type으로, false가 들어간 클래스를 false_type 으로 typedef 시켜둔다.
이후 is_integral 에 들어온 자료형이 정수형이면 true_type을 상속받고, 아니면 false_type을 상속받는다.
그렇게 아래처럼 써봤는데
template <>
struct is_integral<bool> : public true_type{};
template <>
struct is_integral<char> : public true_type {};
template <>
struct is_integral<unsigned char> : public true_type {};
.
.
.
C++
복사
그런데 여기서 is_integral 의 레퍼런스를 읽어보다가, 이런 부분이 있다는 걸 발견했다.
All fundamental integral types, along with all their aliases (like those in cstdint), are considered integral types by this class, including their const
and volatile qualified variants.
const 와 volatile 역시 포함한다고 써있다! volatile 이 뭔지는 잘 모르지만, 일단 const만 하더라도 모든 자료형에 const를 붙인 함수를 또 써야 한다… 심지어 const volatile 도 있다고 하니, int 하나의 자료형에 int, const int, volatile int, const volatile int 총 네 개의 템플릿 클래스를 만들어야 한다.
template <class T> struct remove_cv { typedef T type; };
template <class T> struct remove_cv<const T> { typedef T type; };
template <class T> struct remove_cv<volatile T> { typedef T type; };
template <class T> struct remove_cv<const volatile T> { typedef T type; };
C++
복사
이렇게 만든 후 remove_cv::type 을 호출하면 const 와 volatile이 모두 삭제된 type 만 호출되게 된다.
다시 위의 enable_if 코드를 보고 정리해보면
template <class T>
typename std::enable_if<std::is_integral<T>::value, bool>::type
is_odd (T i) {return bool(i%2);}
C++
복사
is_integral 에 들어온 자료형 T 가 정수라면, SFINAE가 적용된 enable_if의 type 을 호출할 수 있기 때문에 오류가 나지 않는다. T가 정수형이 아니라면, is_integral<T>::value 가 false가 되고, enable_if의 첫번째 타입이 false 이면 멤버타입이 없는 enable_if 가 생성되기 때문에 컴파일 에러가 나게 된다!
(쓰면서도 엄청 헷갈린다.)
여기까지 잘 이해해서 정리하면 enable_if 와 is_integral 등 <type_traits> 헤더는 구현끝!
다음은 iterator 이다.
allocator
<memory> 헤더에 있는 클래스이다.
서브젝트에 보면 std::allocator 를 반드시 사용하라는 문구가 있다. 이 allocator가 뭔지 알아보자.
vector에는 공간을 할당해주는 멤버 함수들이 있다. resize 등!
c++에서는 공간 할당을 할때 new 연산자를 사용하는데, new 연산자는
1.
기본 생성자 필요
2.
메모리 할당
3.
요소 초기화
3가지 조건이 필요하다.
하지만 이 세가지 조건이 세트로 따라다니게 되어서 컴퓨터 자원의 사용량이 상당히 증가한다. 그래서 allocator를 이용하여 위 단계들을 각각 원할때 사용할 수 있게 한다.
특정 컨테이너에 최적화된 유연한 메모리 사용과 관리를 위해 대부분의 컨테이너들은 allocator를 사용한다.
그러니까, new를 쓰면 생성자가 호출되며 메모리를 할당해주고, 해당 자료형에 맞게 초기화까지 해준다. 예를들어 vector<int>를 new로 할당하면 공간 할당을 한 후 초기화가 되고, 이후 사용자가 사용할 때 한번 더 초기화 된다. 초기화가 하나의 요소마다 두번씩 진행되기 때문에 자원 낭비가 심하다는 것이다.
하지만 allocator 클래스를 사용하면 메모리 할당만 하고 초기화를 하지 않을 수 있다. 또한 객체가 들어있는 메모리 공간을 해제(deallocate) 하지 않고 (재할당 하지 않고) 초기 상태로 돌릴 수 있다. (객체만 소멸 시킬 수 있다.destroy)
얘네는 구현된 std 쓰는거라 구현까지는 안해도 된다! 근데 이해는 확실히 해야한다. 무슨 함수가 어떻게 동작하는지 알아야 나중에 벡터의 capacity, resize, size 등을 구현할 때 잘 쓸 수 있다.
capacity ⇒ allocate
size ⇒ allocate + 초기화
(맞나?)
pair
std::pair 과 std::make_pair 를 구현하라고 되어있다.
다른애들은 서브젝트에 std:: 가 안붙어있는데 얘는 왜 붙어있을까?
std::pair::pair 이 있던데 얘때문인가
equal
template <class InputIterator1, class InputIterator2>
bool equal (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2);
C++
복사
first1~last1 범위와 first2~ 앞 범위의 개수만큼의 범위 요소가 모두 같으면 true 리턴!
lexicographical_compare
template <class InputIterator1, class InputIterator2>
bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2);
C++
복사
first1~last1 범위의 요소가 first2~last2 범위의 요소보다 작으면 true!
// lexicographical_compare example#include <iostream>// std::cout, std::boolalpha#include <algorithm>// std::lexicographical_compare#include <cctype>// std::tolower// a case-insensitive comparison function:
bool mycomp (char c1,char c2)
{return std::tolower(c1)<std::tolower(c2); }
int main () {
char foo[]="Apple";
char bar[]="apartment";
std::cout << std::boolalpha;
std::cout <<"Comparing foo and bar lexicographically (foo<bar):\n";
std::cout <<"Using default comparison (operator<): ";
std::cout << std::lexicographical_compare(foo,foo+5,bar,bar+9);
std::cout <<'\n';
std::cout <<"Using mycomp as comparison object: ";
std::cout << std::lexicographical_compare(foo,foo+5,bar,bar+9,mycomp);
std::cout <<'\n';
return 0;
}
C++
복사
vector 구현
레퍼런스에 나와있는 것을 토대로 C++11 버전 이전의 (98버전의) 멤버들과 함수들을 작성하면 된다.
멤버 변수로는
pointer _begin;
pointer _end;
pointer _end_cap;
allocator_type _alloc;
C++
복사
_end는 이터레이터의 end를 가리키는 포인터
_end_cap 은 capacity의 end를 가리킨다. 즉, capacity 용량의 end 포인터 인듯!
