CPP Module 08

20 Dec 2023 in 42Cursus on CPP Module

“CPP Module 08에 대하여”

• ex00: Easy find
  • 반복자 선언, 반복자 반환
  • 주의 사항
  • 연관 컨테이너
• ex01: Span
• ex02: mutated abomination
  • 주의 사항

Templated containers, iterators, algorithms

그냥 하나같이 입맛이 도는 키워드 뿐이네

• 본 모듈부터 템플릿 컨테이너, 반복자, 알고리즘에 접근할 수 있다. 과연 C++의 꽃이라 말할 수 있는 요소들이라 할 수 있겠다. 물론 과제를 원활하게 진행하기 위해서는 저 세 키워드에 대해서 잘 아는 것이 좋겠다. 자세한 공부를 위해서 링크 참조.

(1) 모두의 코드, 씹어먹는 C++ - <10 - 1. C++ STL - 벡터(std::vector), 리스트(list), 데크(deque)>

(2) 반복자, [C++] 반복자 (Iterator)

• 열심히 공부해보자…

ex00: Easy find

• type T를 매개 변수로 받는 함수 템플릿 easyfind를 만든다. 두 개의 매개 변수를 받는데, 첫 번째는 type T, 두 번째는 정수다.

• type T는 정수들로 구성된 컨테이너로 간주하며, 이 함수는 첫 번째 매개 변수에서 두 번째로 주어진 정수 매개 변수가 첫 번째로 등장하는 지점을 반환한다(반복자 반환).

• 만약 등장하지 않는다면 에러를 반환하거나, exception을 던진다. 기존 컨테이너의 행동 양식을 참조해도 좋다. 물론 각자의 main문을 만들어 테스트해보아야 한다.

• 연관 컨테이너를 고려할 필요가 없다.

반복자 선언, 반복자 반환

• 반복자는 c++ 라이브러리 내에서 마치 포인터처럼 동작한다. 사용법도 포인터와 동일하다. 반복자를 선언하고 반환하는 것에 익숙해지면 문제를 수월하게 해결할 수 있다. 간단한 예시를 보자.

#include <iostream>
#include <vector>

int main() 
{
    std::vector<int> v; // 정수 벡터 선언

    for (int i = 1; i <= 5; i++) // v = {1, 2, 3, 4, 5}
        v.push_back(i);

    std::vector<int>::iterator it = v.begin();
    // 정수 벡터의 반복자 선언 후 벡터 v의 begin으로 초기화

    while (it != v.end()) // while 문으로 순회 가능 
    {
        std::cout << *it << " "; // 역참조하는 것처럼 value 출력 가능
        ++it;
    }

	std::cout << '\n';
    
    for (std::vector<int>::iterator it = v.begin(); it != v.end(); it++)
    // for 문으로도 순회 가능
        std::cout << *it << " "; // 마찬가지로 역참조하는 것처럼 value 출력 가능

    return 0;
}

❯ ./a.out
1 2 3 4 5
1 2 3 4 5 %

• 벡터를 만들어 그 반복자를 선언하고, while 문이나 for 문으로 순회하는 간단한 코드다. 이 정도만 알아도 어렵지 않게 easyfind를 만들 수 있지 않을까 생각한다.

주의 사항

You will notice that, in this module, the exercises can be solved WITHOUT the standard
Containers and WITHOUT the standard Algorithms. However, using them is precisely the goal
of this Module. You are allowed to use the STL. 
Yes, you can use the Containers (vector/list/map/and so forth) and the Algorithms 
(defined in header <algorithm>). Moreover, you should use them as much as you can. 
Thus, do your best to apply them wherever it’s appropriate. You will get a very 
bad grade if you don’t, even if your code works as expected. Please don’t be lazy.

• 서브젝트를 유심히 보지 않는다면 지나치기 쉬운 부분인데, 표준 템플릿 라이브러리(컨테이너, 반복자, 알고리즘)를 사용하지 않으면 점수를 받지 못한다. 그러니까 STL를 쓰지 않아도 문제를 풀 수 있다는 사실을 알았어도, STL를 사용한 코드를 제출해야만 한다. easyfind의 경우, 많은 사람들이 알고리즘의 매서드인 std::find()를 사용하는데 이것도 find를 사용하지 않고 풀 수가 있다. 그런 코드를 제출했다가는 점수를 얻지 못하게 될 것이다.

• std::find(container.begin(), container.end(), const T& value)는 container의 begin부터 end까지를 순회하여 매개 변수로 들어온 value가 컨테이너 내에 존재한다면 그 value를 가리키는 반복자를 반환하고, 그렇지 않다면 end의 반복자를 반환한다. 모두의 코드 링크를 첨부한다.

• 모두의 코드, C++ 레퍼런스 - find 함수 (algorithm)

• 아래 코드는 본인이 find를 쓰지 않고 만들었던 코드다. 처음에는 위 사실을 인지하지 못했었다. 이대로 제출했으면 통과하지 못했을 것이다.

template <typename T>
typename T::iterator easyfind(T& container, int value)
{
    typename T::iterator it;

    for (it = container.begin(); it != container.end(); it++)
        if (*it == value)
            return it;

    if (it == container.end())
        throw std::runtime_error("Cannot find value in Container");

    return container.end();
}

• find를 쓰면, typename T::iterator it를 선언하면서 동시에 find로 초기화시켜서, value를 가리키는 반복자가 반환된다면 그대로 반환하고 아니라면 에러로 처리할 테니 줄 길이가 더 줄어들기는 하겠다.

연관 컨테이너

• 연관 컨테이너에 대해 공부하려면

(1) TCP School의 연관 컨테이너

• 연관 컨테이너는 key와 value로 데이터를 쌍으로 저장하는 컨테이너를 말한다. STL에서는 set, multiset, map, multimap 등이 연관 컨테이너다. c++11부터는 unordered_set, unordered_multiset, unordered_map, unordered_multimap을 지원한다. 이들은 본래 정렬을 하면서 데이터를 추가하는 기존의 연관 컨테이너와 달리 정렬하지 않는다.

• 과제를 풀 때 연관 컨테이너에 대해서는 전혀 신경쓰지 않아도 되지만, 연관 컨테이너가 뭔지 알아는 둬야겠다.

ex01: Span

• 최대 N개의 정수를 수용할 수 있는 Span 클래스를 만든다. N은 생성자를 통해서만 전달된다.

• addNumber()를 통해 Span에 새로운 정수를 추가할 수 있다. 물론 Span에 이미 N개의 정수가 들어있다면 예외를 던져야 한다.

• 이후, shortestSpan()과 longestSpan() 멤버 함수를 구현해야 한다. 이는 각각 shortest Span과 longest Span을 찾아 반환해야 한다. 정수가 하나 들어있거나, 없어서 구간이 존재하지 않는다면 예외를 던져야 한다. 정수 간의 가장 짧은 간격이 shortest span, 정수간의 가장 긴 간격이 longest span이라고 볼 수 있다.

• 물론 자신만의 main문을 만들어서 테스트해봐야 한다. 최소한 10000개의 정수를 넣어서 테스트해보는게 좋겠다. 서브젝트에서는 아래의 예시를 제시한다.

int main()
{
    Span sp = Span(5);
    sp.addNumber(6);
    sp.addNumber(3);
    sp.addNumber(17);
    sp.addNumber(9);
    sp.addNumber(11);
    std::cout << sp.shortestSpan() << std::endl;
    std::cout << sp.longestSpan() << std::endl;
    return 0;
}

$> ./ex01
2
14
$>

• 9와 11의 간격이 2로 제일 좁아서 shortestSpan이고, 3과 17의 간격이 제일 넓어서 longestSpan이다.

• 마지막으로 반복자의 범위를 이용하여 Span을 채우는 로직을 만들어야 한다. 예를 들어 0부터 19999까지의 정수를 Span에 넣을 때 addNumber를 20000번 호출하는 것이 아니라 0부터 19999가 들어있는 벡터 v를 미리 만들어둔 후, 그 반복자(v.begin(), v.end())를 이용하면 그 함수를 한번 호출하는 것 만으로 Span을 채울 수가 있다.

• longestSpan의 경우 Span 내에서 가장 큰 값과, 가장 작은 값을 구해서 빼면 되는 간단한 함수이고 이것을 지원하는 매서드도 따로 존재한다. 바로 std::minmax_element(container.begin(), container().end())이다.

(1) cpp 레퍼런스, std::minmax_element

std::pair<std::vector<int>::iterator, std::vector<int>::iterator> p = std::minmax_element(getBegin(), getEnd());

• 위와 같이 선언하여

int min = *(p.first);
int max = *(p.second);

• 이렇게 값을 따올 수가 있다. 아주 편리하다.

• shortestSpan의 경우, Span을 본뜬 벡터를 만들어 그 벡터를 오름차순으로 정렬하고, for 문을 돌면서 v[k + 1] - v[k]의 절댓값을 비교하여 제일 작은 값을 반환했다. 물론 이것 이외에도 다른 방법들이 존재할 것이라고 생각한다.

• 반복자의 범위를 이용하여 Span을 채우는 로직의 경우, 반복자의 처음과 반복자의 마지막을 받아서 while문을 돌면서 Span에 addNumber를 호출하는 함수를 따로 템플릿으로 구현했다. 이 함수를 구현하는 것도 여러 방법이 있을 거라 생각한다.

template <typename T>
void addRange(T first, T last) {
    while (first != last) {
        addNumber(*first);
        ++first;
    }
}

• 이런 느낌으로 hpp에 만들어서, main 문에서 컨테이너를 만들고 그 begin과 end를 가지고 addRange를 호출하면 그 컨테이너의 값들이 Span에 담기게 될 것이다.

ex02: mutated abomination

• ex02를 진행하기 위해서는 컨테이너 어댑터(Container Adapter)에 대해 알고 있어야 한다. 컨테이너 어댑터에 대해 공부하려면 아래 링크 참조.

(1) TCP School, 컨테이너 어댑터

The std::stack container is very nice. 
Unfortunately, it is one of the only STL Containers that is NOT iterable. 
That’s too bad.

아래는 표준 라이브러리 “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>*/>
// ...

• 컨테이너 어댑터에 대해 공부했다면, 서브젝트에 적혀있는 위와 같은 말을 이해할 수 있다. 표준 라이브러리 “stack”을 잘 살펴보면 stack은 deque의 기능을 제한하여 만들어진 것으로 보이는데, 여러가지 기능들이 제한되어있기 때문에 스택은 요소에 대해 임의로 접근(인덱스 기반 접근)할 수가 없고, 반복자도 호출할 수가 없다. 백준이나 프로그래머스에 스택을 만져봤다면 익숙하게 다가올 만한 요소다. ex02에서는 이렇게 반복자를 호출할 수 없는 stack을 보완한, 반복 가능한 MutantStack 클래스를 탄생시켜야 한다. std::stack를 상속하여 스택의 모든 기능을 사용할 수 있도록 한 후, 반복자 기능을 추가하면 된다. 물론 main 문을 작성하여 기능을 테스트해야 할 것이다. 서브젝트에서 아래 main문을 제공한다.

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);
    return 0;
}

• 테스트할 때 MutantStack 외에, 예를 들어 std::list와 같은 컨테이너를 사용하여 반환값이 동일한지 테스트해야 한다. 컨테이너마다 멤버 함수가 조금씩 다를 수 있는데(push()와 push_back() 등), 그 부분은 따로 조정해야 한다.

• 그래서 MutantStack.hpp에 iterator 기능을 넣어줘야 하는데, 그걸 어떻게 하느냐…

• 이건 “stack”에 있는 내용인데, 이것만 보고 곧바로 .hpp에 iterator를 옮겨넣기가 쉽지 않을 것 같다. 정답지를 펼쳐놓고 말하자면

typedef	typename MutantStack<T>::stack::container_type::iterator    iterator;

iterator    begin()
{
    return  this->c.begin();
}

• 이런식으로 나머지 reverse_iterator, const_iterator, const_reverse_iterator도 구현하면 된다. 우선 저기 typedef typename MutantStack<T>::stack::container_type::iterator가 당황스러운데 typedef는 우리가 아는 타입 별칭이고, typename은 템플릿에서 써본 그 typename이다. 저기서 typename을 별도로 사용하는 이유는, typename을 사용하지 않으면 컴파일러가 기본적으로 iterator를 타입으로 간주하기 때문이라고 한다. iterator는 기본적으로 MutantStack<T>에 의존하는 의존 타입이기 때문에 컴파일러에게 iterator가 type이라는 것을 알리기 위해 typename 키워드를 붙여준다. 아까 이미지를 코드로 다시 봐보자.

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;
}

• 맨 윗줄에 친절하게 template <class _Tp, class _Container /*= deque<_Tp>*/>라고 적혀 있다. 기본적으로 stack을 만드는데 deque이 사용되며, public 바로 아래의 typedef _Container container_type; 라인을 통해 deque(_Container)이 container_type으로 치환된다는 것을 알 수가 있다. 그렇다면 다시 typedef typename MutantStack<T>::stack::container_type::iterator iterator를 살펴보자.

typedef	typename MutantStack<T>::stack::container_type::iterator    iterator;

(1) typedef는 우리가 typename MutantStack<T>::stack::container_type::iterator를
iterator로 별칭할 것을 나타낸다.

(2) typename은 iterator가 type이라는 것을 명시한다.

(3) MutantStack<T>::stack::container_type::iterator는 deque의 iterator를 찾아가는 과정이다.

MutantStack은 stack을 상속했으며(MutantStack<T>::stack), stack의 container_type은 deque이다.

(MutantStack<T>::stack::deque), deque에는 iterator가 구현되어 있다.

(MutantStack<T>::stack::deque::iterator), 아래의 이미지를 살펴보자.

아래의 이미지는 <deque>의 일부분이다. iterator가 구현되어 있음을 확인할 수 있다.

• 위의 순서를 거쳐서 MutantStack.hpp에서 deque의 iterator를 끄집어낼 수가 있다. 동일한 방법으로 나머지 반복자들 또한 꺼내올수가 있다.

주의 사항

• cbegin과 crbegin 그리고 cend와 crend를 구현할 때, c++11 함수를 가져다쓰는 실수를 하면 안된다. 제대로 확인하지 않았다가 예리한 사람한테 걸리면 그대로 fail을 받게 된다. 예를 들어 std::deque::begin의 reference를 살펴보자.

• deque의 begin과 end는 c++98 함수이다. 이것은 deque뿐만 아니라 vector, list와 같은 다른 컨테이너에도 해당하는 상황이다. 즉 MutantStack에서 iterator begin이나 end를 반환하기 위해 this->c.begin()과 같이 사용하는 것은 아무런 문제가 없다.

• 그러나 cbegin은 빼박 c++11 함수여서 const iterator, const reverse iterator의 cbegin, cend, crbegin, crend를 호출한답시고 this->c.cbegin() 이라도 외치는 순간 바로 c++11함수를 사용하게 된다. 상수 반복자를 구현할 때 cbegin, cend 함수를 바로 사용하는 것이 아니라 begin, end 등을 사용한 후 const로 반환받는 방식으로 c++11 함수 사용을 회피해야 한다. 이것으로 모듈 8을 마친다.