[42서울] containers 일기_week3

tamagoyakii·2023년 2월 20일
42Seoulcppft_containersstl
0

42seoul

목록 보기
15/19
post-thumbnail

스택과 type_traits 헤더의 함수들을 만든 후에 목표한 부분은 백터였다. 하지만 백터의 멤버 함수들을 구현하기 위해서는 반복자를 완성해야만 한다는 것을 깨달았고, 1주 차 때 잠깐 살펴보다가 넘어간 반복자로 다시 돌아왔다.

✨ iterator

iterators

  1. input_iterator
    컨테이너에서 값을 읽어오는 반복자를 뜻한다. single pass algorithm을 사용하기 때문에 한 번 읽은 메모리로 다시 돌아갈 수 없다.

  2. output_iterator
    컨테이너에 값을 담는 반복자를 뜻한다. input 반복자와 마찬가지로 single pass algorithm을 사용하기 때문에 지나온 메모리도 돌아갈 수 없다.

  3. forward_iterator
    반복자를 ++하여 컨테이너의 값을 차례대로 읽어나갈 수 있다. input 반복자와 다른 점은 forward 반복자는 multi pass algorithm이기 때문에 컨테이너의 begin을 알고 있다면 처음부터 다시 읽을 수 있다는 것이다.

  4. bidirectional_iterator
    forward 반복자와 같은 역할을 한다. 하지만 말 그대로 bidirectional이기 때문에 ++, -- 모두 가능하다.

  5. random_access_iterator
    지금까지 살펴본 반복자들은 컨테이너에 읽거나 쓰는 입구가 하나였다. 하지만 random access 반복자는 입구가 여러 개라서 임의의 입구를 사용해 컨테이너의 값에 접근할 수 있다.

iterator_tag

iterator 클래스의 iterator_category 반환 형식을 제공하는 클래스다. 가장 적합한 반복자를 찾기 위한 태그라고 생각하면 될 것 같다. 다음과 같이 선언되어 있다.

struct input_iterator_tag { };
struct output_iterator_tag { };
struct forward_iterator_tag : public input_iterator_tag { };
struct bidirectional_iterator_tag : public forward_iterator_tag { };
struct random_access_iterator_tag : public bidirectional_iterator_tag { };

named requirements

각 태그의 반복자가 반드시 만족해야만 하는 조건들이다. 단계별로 구현해야 하는 기능들이 추가된다.

  1. LegacyIterator
    • CopyConstructible
    • CopyAssignable
    • Destructible
    • Swappable
    • Dereferenceable :
      *r
    • Incrementable :
      ++r
  1. LegacyInputIterator
    • EqualityComparable :
      i == j
    • Can be compared using the inequality operators :
      i != j
    • Can be dereferenced as an rvalue :
      *i
      i->m
    • Can be incremented :
      ++r
      (void)r++
      *r++
  1. LegacyOutputIterator
    • Can be dereferenced as an lvalue :
      *r = o
    • Can be incremented :
      ++r
      r++
      *r++ = o
  1. LegacyForwardIterator
    • DefaultConstructible :
      T u
      T u{}
      T()
      T{}
    • Can be incremented :
      i++
      *i++
  1. LegacyBidirectionalIterator
    • Can be decremented :
      --i
      i--
      *i--
  1. LegacyRandomAccessIterator
    • Supports arithmetic operators :
      a + n
      n + a
      a - n
      a - b
    • Supports inequality comparisons between iterators :
      a < b
      a > b
      a <= b
      a >= b
    • Supports compound assignment operations :
      a += n
      a -= n
    • Supports offset dereference operator :
      a[n]

서브젝트에서 반드시 구현하도록 요구하는 것은 reverse_iterator이고, 이외의 반복자는 필요시 알아서 구현하여 사용하라고 적혀있다. 때문에 reverse_iterator 이외의 반복자에 대해서는 어떤 프로토타입도 정해져있지 않다.

때문에 백터의 반복자는 gcc의 normal_iterator를 참고하여 만들었다. normal_iterator 클래스는 pointer를 iterator로 wrapping하는 역할을 한다. 때문에 vector나 string 같이 연속적인 데이터를 활용하는 컨테이너에 사용된다.

✨ reverse_iterator

template< class Iter >
class reverse_iterator;

역반복자는 컨테이너의 뒤에서부터 앞으로 순회하는 반복자다. 이 반복자는 최소한 LegacyBidirectionalIterator의 요건을 지키고 있어야 한다.

이 사진이 아마 역반복자를 구현하면서 가장 많이 보게 되는 사진일 것이다. 이전에 아무것도 모를 때 컨테이너 평가를 간 적이 있는데, 그때 피평가자분께서 위 사진을 참고하여 설명해 주신 내용이 머리에 쏙쏙 들어왔던 기억이 있다.

역반복자는 iterator base 클래스를 상속받는데, 역반복자에 정의되는 멤버 타입들은 모두 여기서 상속받게 된다.

std::iterator<std::iterator_traits<Iter>::iterator_category
			, std::iterator_traits<Iter>::value_type
			, std::iterator_traits<Iter>::difference_type
			, std::iterator_traits<Iter>::pointer
			, std::iterator_traits<Iter>::reference>

사실 저렇게 상속받는 iterator는 멤버 타입으로 사용하기 위해서 다시 선언해야 한다. 보통 이렇게들 사용하더라.

template <typename Iter>
class reverse_iterator
	: public ft::iterator<typename ft::iterator_traits<Iterator>::iterator_category,
						typename ft::iterator_traits<Iterator>::value_type,
						typename ft::iterator_traits<Iterator>::difference_type,
						typename ft::iterator_traits<Iterator>::pointer,
						typename ft::iterator_traits<Iterator>::reference > {
 public:
  typedef Iter iterator_type;
  typedef typename ft::iterator_traits<Iter>::iterator_category iterator_category;
  typedef typename ft::iterator_traits<Iter>::value_type value_type;
  typedef typename ft::iterator_traits<Iter>::difference_type difference_type;
  typedef typename ft::iterator_traits<Iter>::pointer pointer;
  typedef typename ft::iterator_traits<Iter>::reference reference;
}

근데 사실 이렇게 사용하면 아래에 퍼블릭 멤버 타입으로 선언된 친구들은 상속받은 친구들이 아니라 iterator_traits로 다시 불러온 친구다. 이게 무슨 구조인지는 잘 이해가 안 가는데 이럴 거면 굳이 상속받아야 하는가라는 의문이 들었다. 이것에 대한 고민은 조금 더 해봐야 할 것 같다.

역반복자에 필요한 모든 멤버 함수들은 cppreference에 예쁘게 잘 정리되어 있기 때문에 그대로 구현만 하면 끝이다.

✨ vector

Vector_base

백터를 구현할 때 Vector_base를 구현할 것인가에 대한 고민을 굉장히 많이 했다. Vector_base는 gcc에서 RAII 패턴을 지키기 위해 컨테이너 할당 및 초기화와 관련된 부분을 따로 선언해둔 백터의 부모 클래스다.

💡 RAII(Resource Acquisition Is Initialization)란?
C++은 동적 할당한 메모리를 프로그래머가 직접 해제해야만 한다. 때문에 항상 메모리 누수의 위협에 시달리게 되는데, 이를 방지하기 위해 나온 것이 RAII 패턴이다.

RAII 스택에 할당되는 메모리가 자동으로 해제되는 원리를 이용한 디자인 패턴이다. 주로 C++에서만 사용되며, std::shared_ptr, std::unique_ptr이 RAII를 사용하는 대표적인 친구들이다.

RAII를 그대로 해석하자면 "자원의 획득은 초기화다."인데, 획득한 자원은 초기화되어 접근 가능 시점에 초기화가 보장되어 있어야 함을 뜻한다. 초기화에 실패한다면 throw() 하기 때문에 자동으로 소멸자가 호출된다. 여기서 알 수 있는 건, RAII에서 중요한 건 소멸자라는 것이다. 유효한 객체가 아닐 때 소멸자가 호출됨으로 자연스럽게 자원이 해제된다. 때문에 예외가 발생하더라도 메모리 누수가 일어나지 않는 것이다.

근데~ gcc의 vector는 Vector_base를 상속받는데~ 이 Vector_base는 사실 Vector_alloc_base라는 녀석을 상속받는다. 이놈들을 보고 있자니 RAII를 지키기 위해서 이렇게 구구절절한 코드를 짜야 하는가?라는 고민을 하게 되는데...

그래서 일단은 Vector_base 없이 백터를 만들었다. 백터의 생성자에는 4가지 종류가 있다.

// default (1)	
explicit vector (const allocator_type& alloc = allocator_type());
// fill (2)	
explicit vector (size_type n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type());
// range (3)	
template <class InputIterator>
vector (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());
// copy (4)	
vector (const vector& x);

Vector_base 없이 이 친구들을 만들다 보면, allocate() 또는 construct() 실패 시 소멸자를 호출하기 위해 온갖 try()... catch()문을 사용하게 된다. 여기까지는 뭐 조금만 신경 쓰면 되니 괜찮다고 생각을 했다.

하지만 allocator를 사용한 할당 과정이 비슷하다 보니 네 개의 생성자에 같은 코드가 줄줄이 들어서게 되는데... 이때 딱 Vector_base를 만들어야겠다는 결심을 했다.

Vector_base 클래스는 메모리 할당과 해제의 역할을 한다. 때문에 다음과 같은 멤버 변수를 선언했다.

template <class T, class Alloc>
class Vector_base {
 public:
  typedef Alloc allocator_type;
  typedef typename allocator_type::pointer pointer;
  typedef typename allocator_type::reference reference;

 protected:
  allocator_type _alloc;
  pointer _begin;
  pointer _end_of_content;
  pointer _end_of_storage;
}

_alloc은 컨테이너에 담기는 요소의 타입을 템플릿 인자로한 std::alloctor 객체다. _begin은 할당된 메모리의 시작을 가리키는 포인터, _end_of_content은 컨테이너의 마지막 요소의 다음을 가리키는 포인터, 마지막으로 _end_of_storage는 할당된 메모리의 마지막을 가리키는 포인터다.

위의 그림처럼 백터에는 size()라는 놈과 capacity()라는 놈이 있다. 때문에 각각의 마지막을 가리키는 포인터를 만들었다.

그리고 allocator 함수들을 사용하는 멤버 함수를 따로 구현했다. allocate(), construct(), deallocate(), destroy() 함수들을 만들어서 백터 클래스에서 메모리 관련 함수들을 Vector_base를 통해 처리할 수 있도록 했다.

부모와 자식 클래스가 모두 템플릿 클래스인 경우 자식이 상속받은 부모의 멤버를 사용하기 위해서는 반드시 this 포인터를 써야 한다. 하지만 using 키워드를 사용하여 선언하면, 다른 곳에 정의된 이름을 해당 키워드를 사용하는 지역에서도 쓸 수 있기 때문에 상속받은 부모의 멤버를 this 포인터 없이 사용할 수 있다.

template <class T, class Alloc = std::allocator<T> >
class vector : protected Vector_base<T, Alloc> {
 private:
  using _Base::_alloc;
  using _Base::_begin;
  using _Base::_end_of_content;
  using _Base::_end_of_storage;
  ...
}

참고

https://en.cppreference.com/w/cpp/iterator/reverse_iterator
https://80000coding.oopy.io/ad7da304-36e9-4db0-aba7-db439cc8bac2
https://occamsrazr.net/tt/297
https://en.cppreference.com/w/cpp/language/using_declaration

profile
tamagoyakii
이전 포스트

[42서울] containers 일기_week2

다음 포스트

[42서울] 소켓 통신과 IRC

0개의 댓글