🍩 stack

contianers에서 구현해야 하는 헤더 파일은 크게 세 개다. (보너스까지 하면 사실 네 개다.)

1. vector
2. map
3. stack
4. set

스택은 본래 큐(queue)의 컨테이너 어댑터다. 하지만 서브젝트에서는 내가 만든 백터(vector) 클레스를 사용하라고 요구한다. 이러나저러나 스택은 백터의 기능을 제한하기만 하면 되기 때문에 가장 쉽게 구현할 수 있을 것 같아 이놈 먼저 처리하기로 했다. (구현은 std::vector로 먼저 했다.)

스택의 메모리 구조는 선형 메모리 공간에 데이터를 저장하면서 후입선출, 즉 LIFO(Last In First Out)의 시멘틱을 따른다. 스택 컨테이너는 요소에 대한 임의의 접근을 허용하지 않으며, 스택을 순회하는 반복자도 허용하지 않는다!

template <class T, class Container = deque<T> >
class stack;

member functions

멤버 함수와 비멤버 함수들은 cppreference 또는 cplusplus에 굉장히 자세히 나와있다. 하지만 그럼에도 불구하고 여기에 적어놓는 이유는 내가 보기 편하려고..!이다.

• empty() =vector.empty()
  : 스택이 비어 있으면 true를, 비어 있지 않으면 false를 반환
• pop() =vector.pop_back()
  : 스택의 제일 상단에 있는 요소를 삭제
• push() =vector.push_back()
  : 스택의 제일 상단에 요소를 삽입
• size() =vector.size()
  : 스택 요소의 총 개수를 반환
• swap()
  : non-member overload 함수인 swap()을 호출
• top() =vector.back()
  : 스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소에 대한 참조를 반환

non-member overloads

• relational operators

template <class T, class Container>
bool operator== (const stack<T,Container>& lhs, const stack<T,Container>& rhs);

template <class T, class Container>  
bool operator!= (const stack<T,Container>& lhs, const stack<T,Container>& rhs);

template <class T, class Container>  
bool operator< (const stack<T,Container>& lhs, const stack<T,Container>& rhs);

template <class T, class Container>  
bool operator<= (const stack<T,Container>& lhs, const stack<T,Container>& rhs);

template <class T, class Container>  
bool operator>  (const stack<T,Container>& lhs, const stack<T,Container>& rhs);

template <class T, class Container>  
bool operator>= (const stack<T,Container>& lhs, const stack<T,Container>& rhs);

• swap()

template <class T, class Container>
void swap (stack<T,Container>& x, stack<T,Container>& y) noexcept(noexcept(x.swap(y)));

사실 swap은 아직 잘 모르겠다. 백터의 swap을 먼저 구현하는게 좋을 듯 하다.

스택은 사실 크게 어려운 부분이 없다. 컨테이너 어댑터이기 때문에 기저 컨테이너의 함수들을 잘 사용할 수 있도록만 구현해 주면 끝이다.

스택을 다 만들었다면 백터로 넘어가게 될 텐데, 이때 구현의 첫 부분인 생성자를 만들기 위해 알아야 하는 개념들이 다음에 나온다.

🍩 type_traits

SFINAE

SFINAE(Substitution Failure Is Not An Error)는 말 그대로 치환 오류는 컴파일 에러가 아니라는 원칙이다. 때문에 템플릿 인자 치환 후에 만들어진 식이 문법적으로 맞지 않는다면 컴파일 오류를 내는 대신 단순히 함수의 오버로딩 후보군에서 제외만 시키게 되는 것이다.

이런 작업을 쉽게 할 수 있도록 제공되는 type_traits 헤더의 함수 중 하나가 아래의 enable_if이다. 우리가 직접 구현해야 하는 함수이기도 하다.

std::enable_if

enable_if 는 SFINAE를 통해서 조건에 맞지 않는 함수들을 오버로딩 후보군에서 쉽게 뺄 수 있게 도와주는 간단한 템플릿 메타 함수로, 다음과 같이 정의되어 있다.

template<bool B, class T = void>
struct enable_if {};
 
template<class T>
struct enable_if<true, T> { typedef T type; };

템플릿 인자인 B에는 우리가 확인할 조건을 넣어주면 되는데, 이때 B가 true로 판별되면 아래의 객체가, false로 판별되면 위의 객체가 사용된다.

즉, 조건이 참일 경우의 enable_if::type 은 T가 되고, 거짓일 경우 enable_if::type은 존재하지 않게 되는 것이다.

std::is_integral

여기서 정수타입인지 아닌지 확인해주는 함수가 추가된다. 이 또한 서브젝트에서 직접 구현하라고 요구하는 함수다. is_integral 함수가 정수라고 판단하는 타입들은 다음과 같다.

• bool
• char
• char16_t
• char32_t
• wchar_t
• signed char
• short int
• int
• long int
• long long int
• unsigned char
• unsigned short int
• unsigned int
• unsigned long int
• unsigned long long int

is_integral은 템플릿 인자로 판별할 타입 T를 받으며, integral_constant 구조체를 상속받는다.

template< class T >
struct is_integral;

template< class T, T v >
struct integral_constant;

위의 템플릿 인자 T는 상수의 형식, v는 상수의 값이며, integral_constant는 T가 bool일 때 두 가지 별칭이 존재한다.

typedef std::integral_constant<bool, true> true_type;
typedef std::integral_constant<bool, false> false_type;

값이 true 일 때는 true_type, false 일 때는 false_type이라고 불리는 것이다. 이외의 멤버 타입 및 함수들은 다음과 같다.

template< class T, T v >
struct integral_constant {
	// member types
	typedef T value_type;
    typedef integral_constant<T, v> type;
    // member constants
    static const T value = v;
	// member functions
    constexpr operator value_type() const noexcept;
    constexpr value_type operator()() const noexcept;
}

다시 is_integral로 돌아가 보자면, is_integral은 템플릿 인자의 값이 정수냐 아니냐에 따라 상속 받는 integral_constant가 달라진다. 정수일 때는 true_type, 아닐 때는 false_type을 상속받는다.

이를 판별하기 위해 이전에 배운 템플릿 특수화가 사용된다.

template <class T>
struct is_integral : public false_type {};		// 기본적으로 false_type 상속

template <>
struct is_integral<bool> : public true_type {};	// bool일 경우 true_type 상속

template <>
struct is_integral<char> : public true_type {};	// char일 경우 true_type 상속

...

이렇게 구현한 enable_if와 is_integral은 이후 과제를 진행하면서 직접 사용하게 된다.

🍩 std::allocator

표준 라이브러리, 주로 STL 컨테이너에서 사용되는 메모리 모델을 정의해주는 클래스다. 백터 컨테이너를 할당하기 위해 필요하다.

constructor

allocator 객체를 만든다. 그 어떤 초기화도 하지 않지만, 세 가지 버전의 생성자 모두 다른 타입의 allocator 객체를 복사 생성할 수 있어야 한다.

• default

allocator() throw();

• copy

allocator (const allocator& alloc) throw();

template <class U>
allocator (const allocator<U>& alloc) throw();

member functions

• address()
  : x의 주소를 반환한다. 여기서 x는 객체의 참조자로, allocator 객체의 멤버 타입으로 선언되어있다.

pointer address(reference x) const;
const_pointer address(const_reference x) const;

• allocate()
  : value_type을 최소 n개 수용할 수 있는 공간의 할당을 시도하고, 첫 요소의 포인터를 반환한다. 이때 value_type타입의 객체를 위한 메모리가 할당될 뿐, 생성까지 되는 것은 아니다. 여기서 할당이 실패한다면 default allocator가 bad_alloc을 throw 한다.

pointer allocate(size_type n, allocator<void>::const_pointer hint=0);

• deallocate()
  : 위의 allocate()로 할당된 메모리 중 아직 해제되지 않는 것들을 해제시킨다. 인자로 들어오는 p는 위의 allocate()에서 할당하는 메모리의 주소이고, n은 allocate()을 호출할 때 전달했던 인자의 개수다.

void deallocate(pointer p, size_type n);

• max_size()
  : allocate() 멤버 함수로 할당할 수 있는 value_type 객체의 최대 개수를 반환한다. 그러나 max_size()의 반환값을 이용한 allocae()가 꼭 성공하는 것은 아니다.

size_type max_size() const throw();

• construct()
  : 포인터 p가 가리키는 메모리 공간에 요소 val을 저장한다. 요소를 위한 공간을 할당하는 것은 아니며, allocate() 함수로 이미 할당되어 있어야 한다. 이때 val은 멤버 타입인 value_type의 객체이며, 복사 생성자를 이용하여 초기화되므로 다음의 식이 실행되는 것과 같은 동작을 한다.
  new ((void*)p) value_type (val);

void construct(pointer p, const_reference val);

• destroy()
  : 포인터 p가 가리키는 공간에 있는 객체를 소멸시킨다. 그 공간 자체의 메모리는 deallocate() 함수로 해제해야 한다.

void destroy(pointer p);

allocator를 사용하여 공간을 관리할 경우 allocate(), construct() 등의 함수에서 실패 시 bad_alloc을 throw 한다. 이를 vector 생성자에서 직접 사용하게 되면 많은 try()...catch()문이 쓰이게 된다.

이를 방지하기 위해 사용되는 방법이 RAII 패턴이다. 이에 대한 내용은 이후 vector를 구현할 때 살펴보도록 하겠다.

🍩 참고

https://cplusplus.com/reference/stack/stack/
https://modoocode.com/295
https://cplusplus.com/reference/type_traits/is_integral/
https://en.cppreference.com/w/cpp/types/is_integral
https://en.cppreference.com/w/cpp/types/integral_constant
https://en.cppreference.com/w/cpp/memory/allocator
https://cplusplus.com/reference/memory/allocator/