ex02

stack에 대한 공부를 하고 가자

https://wo-dbs.tistory.com/181

stack

 

• 이 문제는 stack을 상속받아서 stack을 직접 구현해보는 문제임.
• 기본 stack의 요소들은 stack을 상속 받아서 잘 사용할 수 있기는 함. 그런데 문제에서 요구하는 건 stack 컨테이너에 없는 반복자의 기능을 넣어서 보여달라고 하는 거임
• 원래는 stack에 반복자 기능이 없음. 반복자 기능을 넣으려는 게 중요 포인트이다. 이걸 구현할 방법을 찾아보자.
• 먼저 stack 컨테이너를 구현한 코드를 들고와보자

stack

#include <__config>
#include <deque>

#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
#pragma GCC system_header
#endif

_LIBCPP_BEGIN_NAMESPACE_STD

template <class _Tp, class _Container = deque<_Tp> > class _LIBCPP_TEMPLATE_VIS stack;

template <class _Tp, class _Container>
_LIBCPP_INLINE_VISIBILITY
bool
operator==(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y);

template <class _Tp, class _Container>
_LIBCPP_INLINE_VISIBILITY
bool
operator< (const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y);

template <class _Tp, class _Container /*= deque<_Tp>*/>
class _LIBCPP_TEMPLATE_VIS stack
{
public:
    typedef _Container                               container_type;
    typedef typename container_type::value_type      value_type;
    typedef typename container_type::reference       reference;
    typedef typename container_type::const_reference const_reference;
    typedef typename container_type::size_type       size_type;
    static_assert((is_same<_Tp, value_type>::value), "" );

protected:
    container_type c;

public:
    _LIBCPP_INLINE_VISIBILITY
    stack()
        _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value)
        : c() {}

    _LIBCPP_INLINE_VISIBILITY
    stack(const stack& __q) : c(__q.c) {}

    _LIBCPP_INLINE_VISIBILITY
    stack& operator=(const stack& __q) {c = __q.c; return *this;}

• 이 stack 코드에서 _Container을 보면 deque<_Tp> 이렇게 있을 것이다. 이게 뭘 의미하냐 stack 컨테이너는 deque으로 이루어져있다는 것을 알 수가 있음.
• 우리 stack에 코드를 잘 찾아보면 반복자에 대한 내용은 없음. 하지만 deque의 코드를 살펴보면

deque

template <class _Tp, class _Allocator /*= allocator<_Tp>*/>
class _LIBCPP_TEMPLATE_VIS deque
    : private __deque_base<_Tp, _Allocator>
{
public:
    // types:

    typedef _Tp value_type;
    typedef _Allocator allocator_type;

    static_assert((is_same<typename allocator_type::value_type, value_type>::value),
                  "Allocator::value_type must be same type as value_type");

    typedef __deque_base<value_type, allocator_type> __base;

    typedef typename __base::__alloc_traits        __alloc_traits;
    typedef typename __base::reference             reference;
    typedef typename __base::const_reference       const_reference;
    typedef typename __base::iterator              iterator;
    typedef typename __base::const_iterator        const_iterator;
    typedef typename __base::size_type             size_type;
    typedef typename __base::difference_type       difference_type;

    typedef typename __base::pointer               pointer;
    typedef typename __base::const_pointer         const_pointer;
    typedef _VSTD::reverse_iterator<iterator>       reverse_iterator;
    typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;

    using typename __base::__deque_range;
    using typename __base::__deque_block_range;
    using typename __base::_ConstructTransaction;

    // construct/copy/destroy:
    _LIBCPP_INLINE_VISIBILITY
    deque()
        _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
        {}
    _LIBCPP_INLINE_VISIBILITY explicit deque(const allocator_type& __a) : __base(__a) {}
    explicit deque(size_type __n);
#if _LIBCPP_STD_VER > 11
    explicit deque(size_type __n, const _Allocator& __a);
#endif
    deque(size_type __n, const value_type& __v);
    deque(size_type __n, const value_type& __v, const allocator_type& __a);
    template <class _InputIter>
        deque(_InputIter __f, _InputIter __l,
              typename enable_if<__is_cpp17_input_iterator<_InputIter>::value>::type* = 0);
    template <class _InputIter>
        deque(_InputIter __f, _InputIter __l, const allocator_type& __a,
              typename enable_if<__is_cpp17_input_iterator<_InputIter>::value>::type* = 0);
    deque(const deque& __c);
    deque(const deque& __c, const allocator_type& __a);

    deque& operator=(const deque& __c);

#ifndef _LIBCPP_CXX03_LANG
    deque(initializer_list<value_type> __il);
    deque(initializer_list<value_type> __il, const allocator_type& __a);

    _LIBCPP_INLINE_VISIBILITY
    deque& operator=(initializer_list<value_type> __il) {assign(__il); return *this;}

    _LIBCPP_INLINE_VISIBILITY
    deque(deque&& __c) _NOEXCEPT_(is_nothrow_move_constructible<__base>::value);
    _LIBCPP_INLINE_VISIBILITY
    deque(deque&& __c, const allocator_type& __a);
    _LIBCPP_INLINE_VISIBILITY
    deque& operator=(deque&& __c)
        _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&
                   is_nothrow_move_assignable<allocator_type>::value);

    _LIBCPP_INLINE_VISIBILITY
    void assign(initializer_list<value_type> __il) {assign(__il.begin(), __il.end());}
#endif  // _LIBCPP_CXX03_LANG

    template <class _InputIter>
        void assign(_InputIter __f, _InputIter __l,
                    typename enable_if<__is_cpp17_input_iterator<_InputIter>::value &&
                                      !__is_cpp17_random_access_iterator<_InputIter>::value>::type* = 0);
    template <class _RAIter>
        void assign(_RAIter __f, _RAIter __l,
                    typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type* = 0);
    void assign(size_type __n, const value_type& __v);

    _LIBCPP_INLINE_VISIBILITY
    allocator_type get_allocator() const _NOEXCEPT;

    // iterators:

    _LIBCPP_INLINE_VISIBILITY
    iterator       begin() _NOEXCEPT       {return __base::begin();}
    _LIBCPP_INLINE_VISIBILITY
    const_iterator begin() const _NOEXCEPT {return __base::begin();}
    _LIBCPP_INLINE_VISIBILITY
    iterator       end() _NOEXCEPT         {return __base::end();}
    _LIBCPP_INLINE_VISIBILITY
    const_iterator end()   const _NOEXCEPT {return __base::end();}

    _LIBCPP_INLINE_VISIBILITY
    reverse_iterator       rbegin() _NOEXCEPT
        {return       reverse_iterator(__base::end());}
    _LIBCPP_INLINE_VISIBILITY
    const_reverse_iterator rbegin() const _NOEXCEPT
        {return const_reverse_iterator(__base::end());}
    _LIBCPP_INLINE_VISIBILITY
    reverse_iterator       rend() _NOEXCEPT
        {return       reverse_iterator(__base::begin());}
    _LIBCPP_INLINE_VISIBILITY
    const_reverse_iterator rend()   const _NOEXCEPT
        {return const_reverse_iterator(__base::begin());}

    _LIBCPP_INLINE_VISIBILITY
    const_iterator         cbegin()  const _NOEXCEPT
        {return __base::begin();}
    _LIBCPP_INLINE_VISIBILITY
    const_iterator         cend()    const _NOEXCEPT
        {return __base::end();}
    _LIBCPP_INLINE_VISIBILITY
    const_reverse_iterator crbegin() const _NOEXCEPT
        {return const_reverse_iterator(__base::end());}
    _LIBCPP_INLINE_VISIBILITY
    const_reverse_iterator crend()   const _NOEXCEPT
        {return const_reverse_iterator(__base::begin());}

    // capacity:
    _LIBCPP_INLINE_VISIBILITY
    size_type size() const _NOEXCEPT {return __base::size();}
    _LIBCPP_INLINE_VISIBILITY
    size_type max_size() const _NOEXCEPT
        {return std::min<size_type>(
            __alloc_traits::max_size(__base::__alloc()),
            numeric_limits<difference_type>::max());}
    void resize(size_type __n);
    void resize(size_type __n, const value_type& __v);
    void shrink_to_fit() _NOEXCEPT;
    _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
    bool empty() const _NOEXCEPT {return __base::size() == 0;}

• iterators에 대한 내용이 있다. 즉, 반복자에 대한 내용이 있음 이 기능을 상속 받아서 사용하면 됨.
• 다시 생각해보면 우리는 우리가 만든 stack에서 stack 컨테이너를 상속 받았음. 즉 deque도 상속 받았다고 생각하면 됨. 그렇기에 바로 반복자 기능만 추가하면 된다는 사실임.

 

main.cpp

#include "MutantStack.hpp"

int main()
{
	MutantStack<int> mstack;

	mstack.push(5);
	mstack.push(17);
	
	std::cout << mstack.top() << std::endl;

	mstack.pop();

	std::cout << mstack.size() << std::endl;

	mstack.push(3);
	mstack.push(5);
	mstack.push(737);
	mstack.push(0);

	MutantStack<int>::iterator it = mstack.begin();
	MutantStack<int>::iterator ite = mstack.end();

	++it;
	--it;
	while (it != ite)
	{
		std::cout << *it << std::endl;
		++it;
	}
	std::stack<int> s(mstack);

	std::cout << "------------------------------\\n";

	{
		std::list<int> list;
		list.push_back(5);
		list.push_back(17);
		std::cout << list.back() << std::endl;
		list.pop_back();
		std::cout << list.size() << std::endl;
		list.push_back(3);
		list.push_back(5);
		list.push_back(737);
		list.push_back(0);
		std::list<int>::iterator it_list = list.begin();
		std::list<int>::iterator ite_list = list.end();
		++it_list;
		--it_list;
		while (it_list != ite_list)
		{
			std::cout << *it_list << std::endl;
			++it_list;
		}
	}

	return 0;
}