CPP Module 08

CPP Module 08

과제를 통해 배울 수 있는 것

CPP Module 07에서 템플릿에 대한 기초를 배웠다면 이번 과제에서는 템플릿의 응용을 배운다.

컨테이너

참고: (C++14 STL 철저 입문)[https://42library.kr/info/899]

컨테이너는 객체를 일정한 방식으로 저장하고 조직화하는 객체를 말한다. 컨테이너를 사용한다는 건 데이터에 접근하기 위해 반드시 반복자를 사용한다는 것이므로 반복자도 이해해야 한다.

STL에서 제공하는 컨테이너는 다음과 같다.

순차 컨테이너

• 선형으로 저장
• 반드시 연속 메모리로 저장될 필요는 없음
• 멤버 함수를 호출하거나 반복자를 사용해서 객체들을 차례로 접근할 수 있음
• 첨자 연산자와 인덱스를 사용해 접근 가능
• 예: array<T,N>, vector<T>, deque<T>, list<T>, forward_list<T>

연관 컨테이너

• 객체들을 연관된 키와 함께 저장
• 키를 이용해서 연관 컨테이너에서 객체를 가져옴
• 반복자를 이용해서 연관 컨테이너에서 객체를 가져올 수도 있음
• 예: map<K,T>, set<T>, multimap<T>, unordered_set<T>, unordered_multimap<T>

컨테이너 어댑터

• 순차 컨테이너나 연관 컨테이너에 저장된 데이터에 접근하는 따른 방법을 제공하는 어댑터 클래스 템플릿
• 예: stack<T>, queue<T>, priority_queue<T>

반복자

참고: (C++14 STL 철저 입문)[https://42library.kr/info/899]

반복자는 포인터와 비슷하게 동작하는 클래스 템플릿 타입의 객체를 말한다. 반복자 iter가 유효 객체를 가리킨다면 *iter라고 쓰기만 해도 반복자 iter를 역참조해서 객체에 대한 참조를 얻을 수 있다.
iter가 클래스 객체를 가리킨다면 객체의 멤버 member는 iter->member로 접근할 수 있다.

따라서 반복자는 포인터처럼 쓰면 된다.

반복자를 사용하면 컨테이너에 있는 원소들에 접근하면서 일정한 방식으로 원소들을 처리할 수 있다. 즉, 반복자는 컨테이너의 종류와 상관없이 컨테이너에 있는 원소들과 알고리즘을 이어준다.

반복자는 원소들의 범위를 정의하므로, 범위의 첫 번째 원소를 가리키는 begin 반복자와 마지막 원소를 가리키는 end 반복자로 지정한 원소들의 순차열로 범위를 표현한다.

Exercise 00: Easy find

템플릿 함수 easyfind는 첫 번째 인자로 주어진 매개 변수에서 두 번째 인자로 주어진 매개 변수를 찾아야 한다.
첫 번째 인자는 타입 T이며, 이 T는 정수형 컨테이너로 간주한다.
만약 찾지 못한다면 예외를 발생시키거나 에러를 출력한다.

template<typename T>
int easyfind(T &container, int n) {
  typename T::iterator it = std::find(container.begin(), container.end(), n);
  if (it == container.end())
    throw std::exception();
  return *it;
}

여기서 typename T::iterator it = std::find(container.begin(), container.end(), n); 부분을 보면 it라는 이름의 반복자를 선언하고 초기화 했다.

std::find() 함수는 value 부분인 n과 비교하여 컨테이너의 시작부터 끝까지 같은 값이 있는지를 탐색하고, 만약 같은 값이 없다면 마지막 반복자를 반환한다.
그래서 탐색 후에 같은 값이 없다면 it에는 컨테이너의 마지막 원소 container.end()가 들어있을 것이기 때문에, 이럴 경우에는 예외를 발생시키도록 한 것이다.

Exercise 01: Span

Span 클래스를 만드는 문제로, 최대 N(unsigned int)개의 정수를 저장할 수 있다. addNumber() 멤버 함수를 호출하여 Span에 한 개의 숫자를 추가할 수 있고 순서대로 채워져야 하며, 중복 삽입이라면 예외를 발생시킨다.

shortestSpan()과 longestSpan()은 각각 제일 짧은 거리(span)와 제일 긴 거리를 구해서 반환해야 하며, 만약 저장된 숫자의 개수가 1개 이하라면 어떠한 거리도 구할 수 없다. 따라서 예외를 발생시킨다.

매우매우 간단한 문제다. 나는 이번 문제에서 벡터를 사용했는데, 순서가 있다는 점이 선형적인 것 같아서 그 중에 가장 끌리는 자료형인 std::vector를 사용하였다.

우선 숫자를 추가하는 함수부터 살펴보도록 하겠다.

void Span::addNumber(unsigned int value) {
  try {
    if (_v.size() == _n)
      throw std::length_error("Error: the container is full.");
    if (std::find(_v.begin(), _v.end(), value) != _v.end())
      throw std::runtime_error("Error: the value is already stored.");
    _v.push_back(value);
  } catch (std::exception &e) {
    std::cout << F_RED
              << e.what()
              << FB_DEFAULT << std::endl;
  }
}

나는 Span 클래스에 _n이라는 멤버 변수를 이용하여 생성자에서 std::vector의 크기를 저장해두고 사용했다. 그래서 벡터 멤버 변수인 _v에 _n을 비교하여 사이즈가 같다면 이미 벡터의 크기가 _n이라는 의미기 때문에 이때 예외를 발생시켰다.

그리고 중복을 검사하기 위해 std::find라는 함수를 사용하였고 만약 _v에서 추가하려는 값을 찾았다면(= std::find의 반환값이 _v.end()가 아니라면) 이때도 예외를 발생시키도록 했다.

그 외의 상황에서는 push_back() 함수를 사용하여 순서대로 벡터에 값을 저장하였다.

이번엔 거리(span)을 구하는 함수를 보도록 하겠다.

int Span::shortestSpan() {
  try {
    if (_v.size() <= 1)
      throw std::runtime_error("Error: there is no span to find.");
    std::vector<int> tmp(_v);
    std::sort(tmp.begin(), tmp.end());
    int min = std::abs(tmp[0] - tmp[1]);
    for (unsigned int i = 0; i < tmp.size() - 1; i++) {
      for (unsigned int j = i + 1; j < tmp.size(); j++) {
        if (std::abs(tmp[i] - tmp[j]) < min)
          min = std::abs(tmp[i] - tmp[j]);
      }
    }
    return min;
  } catch (std::exception &e) {
    std::cout << F_RED
              << e.what()
              << FB_DEFAULT << std::endl;
  }
  return -1;
}

문제에 있던 대로 만약 벡터의 크기가 1보다 작거나 같다면 거리를 구할 수 없기 때문에 예외를 발생시켰다.

만약 정상적인 상황이라면, _v의 데이터 오염을 막기 위해 임시로 tmp 변수를 만들어 이 tmp를 정렬시켰다. 그래서 각 원소를 순회하며 앞과 뒤의 차를 구한 후에 절대값으로 구한 값이 기존의 최소값보다 작은지를 판단하여 최소 거리를 구했다.
최대 거리를 구하는 방법은 여기서 크냐 작냐만 바꾸면 된다.

Exercise 02: Mutated abomination

std::stack 컨테이너는 매우 훌륭하지만, 안타깝게도 반복자를 쓸 수 없다. 그러나! 42는! 스택에 없는 기능을 구현하여 자유를 주고자 한다!
정의를 실현하기 위해(?) std::stack 컨테이너에서도 반복자를 사용할 수 있게 해주자!

MutantStack 클래스를 정의하자. std::stack의 멤버 함수와 전부 같은 기능을 구현해야 하며, 여기에 반복자를 추가해야 한다.

참고로 std::stack의 멤버 함수는 (std::stack cppreference.com)[https://en.cppreference.com/w/cpp/container/stack]에서 확인할 수 있다.

template<typename T>
class MutantStack : public std::stack<T> {
 public:
  MutantStack() {};
  MutantStack(const MutantStack<T> &other) { if (this != &other) *this = other; }
  MutantStack<T> &operator=(const MutantStack<T> &mutantStack) {
    if (this != &mutantStack) {
      this->c = mutantStack.c;
    }
    return *this;
  }
  ~MutantStack() {};

  typedef typename MutantStack<T>::stack::container_type::iterator iterator;
  iterator begin() { return this->c.begin(); };
  iterator end() { return this->c.end(); }

  typedef typename MutantStack<T>::stack::container_type::const_iterator const_iterator;
  const_iterator begin() const { return this->c.begin(); }
  const_iterator end() const { return this->c.end(); }

  typedef typename MutantStack<T>::stack::container_type::reverse_iterator reverse_iterator;
  reverse_iterator rbegin() { return this->c.rbegin(); }
  reverse_iterator rend() { return this->c.rend(); }

  typedef typename MutantStack<T>::stack::container_type::const_reverse_iterator const_reverse_iterator;
  const_reverse_iterator rbegin() const { return this->c.rbegin(); }
  const_reverse_iterator rend() const { return this->c.rend(); }
};

저 위의 레퍼런스를 읽어봤다면 “어? 왜 push나 pop 같은 거 구현 안 함?” 할 수 있는데, 우리에겐 상속이라는 훌륭한 객체 지향 개념이 있다.

그래서 우리가 구현해야 할 것은 바로 컨테이너에 들어있는 반복자 뿐이다. 그런데 이 반복자도 종류가 여러 가지라(읽기, 출력, 순방향, 양방향, 랜덤 액세스) 다 구현해야 하나 싶었다.
그러던 와중에 (container: cppreference.com)[https://en.cppreference.com/w/cpp/container]에서 Member function table 보니까 Iterators 항목에 begin, cbegin, end, cend, rbegin, crbegin, rend, crend만 있길래 얘네만 구현해줬다.