포괄적 프로그래밍과 표준 C++ 라이브러리

소개와 활용 III (학술주석판)

1999-03-01·김재우11 min read

여태까지 진행된 논의를 기반으로 실제의 표준 라이브러리에 준하는 iterator 인터페이스와 그 기능적 특성을 좀더 깊이 살펴보도록 하자.

Iterator와 재사용성 #

이전 기사를 통해 여러 번 언급한 바와 같이 C++ 표준 라이브러리는 Algorithm-Iterator-Container로 구성된다. 여기서 Iterator는 Container와 algorithm의 지나친 의존관계를 제거하는 인터페이스 역할을 한다. ⊕ Algorithm-Iterator-Container (AIC) 아키텍처: 이는 STL의 정신적 핵심입니다. 25년 후 현대 언어도 같은 원칙을 따릅니다. Kotlin sequences, Rust iterators, JavaScript generators 모두 이 구조를 반영합니다. 쉽게 말하자면 algorithm에서 필요한 것은 일련의 원소이고 Container는 원소의 모임이다. 결국 algorithm이 필요로 하는 것은 컨테이너 그 자체가 아니라 컨테이너의 원소를 하나 씩 가져 와서 사용할 수 있는 제어 기능이다.

재사용성은 일반적으로 효율성의 손실로 이어진다. 그러나 이번C++라이브러리의 주요 부품군인 STL은 다르다. ⊕ 효율성 vs 일반성의 해결: 이것이 STL의 최대 성과입니다. Dynamic polymorphism (virtual functions)은 비용이 있지만, template-based generic programming은 컴파일 타임에 특화되어 0 overhead abstraction을 제공합니다. 잘 아시다시피 STL은 Alexander Stepanov와 Meng Lee의 연구 성과다. 그 들은 C++ 언어 자체를 변화 시켜서라도 효율성과 일반성이라는 두 마리 토끼를 모두 잡으려고 무던한 노력을 하였다.

STL의 설계자들이 주목한 C++언어의 기능은 바로 template이었다. 그들은 재사용 라이브러리의 주된 설계 및 구현 모델인 객체지향적 언어기능에 거의 의존하지 않았다. 객체지향적 재 사용성은 한 마디로 subtyping polymorphism에 의존하는 것이고 subtyping polymorphism의 일반적인 구현전략은 method overriding을 위한 dynamic binding이다. ⊕ Dynamic Binding의 비용: Virtual function calls은 함수 포인터 indirection이므로 최적화(inlining)를 방해합니다. C++11의 virtual 키워드 최적화와 C++20의 devirtualization techniques도 이 문제를 해결하려는 시도들입니다. Dynamic binding이란 결국 indirection이며 성능의 감소는 필연적이다. 이에 반해 template에 기반한 C++의 generic 또는 parametric polymorphism은 컴파일러가 안정적으로 지원하기만 한다면 효율성의 감소가 거의 없다.

배열의 포인터와 Iterator #

표준 C++ 라이브러리의 Iterator가 cursor라 불리는 모델에 따라 설계되었다는 점은 지난 호에 이미 설명하였다. ⊕ Cursor 모델의 정의: Iterator는 “현재 위치(where)“를 나타내는 추상화입니다. SQL의 CURSOR, 데이터베이스의 seek pointer와 동일한 개념입니다. 이는 Range-based (begin/end)이 아닌 State-based (position) 모델입니다. Cursor 방식만을 두고 얘기한다면 Iterator란 “포인터의 추상화"에 불과하다.

포인터는 특정객체의 위치를 가리키는 객체다. 그러므로, 포인터 변수 p가 가리키는 원소를 얻어내려면:

*p

라고 operator*(dereference operator)(read/write)를 사용하면 된다. 다음으로, 만일 p가 배열의 특정원소를 가리키는 포인터 변수라면:

p++
++p

와 같이 위치이동을 하는 연산이 가능하다. ⊕ Increment 연산의 두 가지 형태: p++ (post-increment)와 ++p (pre-increment)는 의미상 다릅니다. 포인터에서는 차이가 없지만, Iterator에서는 post-increment가 임시 객체를 생성하므로 비용이 더 클 수 있습니다.

또한 p는 배열의 포인터기 때문에 subscript (index) 연산자를 사용해서 random으로 다음과 같이 원소를 참조할 수 있다.

p[i] (== p + i)

부가적으로 C/C++의 배열에는 아주 심각한 문제가 있다는 점을 지적하고 넘어가야 하겠다. ⊕ 배열의 근본적 문제: C 배열은 크기 정보를 잃어버립니다. int a[10]에서 int* p = a로 decay하면 크기 정보가 소실됩니다. 이는 C++11의 std::array<T, N>과 C++20의 std::span<T>로 해결되었습니다. 포인터변수를 사용해서 배열을 조작하는 경우 배열의 크기를 알 수가 없기 때문에 프로그래머는 포인터 연산을 하거나 indexing을 하는 경우 본래 배열의 범위를 넘지않는지 항시 검사할 필요가 있다.

int a[4] = { 1, 2, 3, 4 };
int* p= a;
int* const end = a + 4;
while (p != end) { ...; p++; }

Iterator Category를 이해하자 #

C++ 표준 라이브러리가 제공하는 Iterator는 연산의 성질에 따라 다섯 가지로 분류된다. ⊕ Five Iterator Categories: 이 분류는 1998년 표준화 과정에서 확립되었습니다. 참고: cppreference: Iterator categories InputIterator, OutputIterator, ForwardIterator, BidirectionalIterator, RandomAccessIterator.

struct InputIterator {};
struct OutputIterator {};
struct ForwardIterator : public InputIterator, OutputIterator {}
struct BidirectionalIterator : public ForwardIterator {}
struct RandomAccessIterator : public BidirectionalIterator {}

위에서 제시한 분류방식을 이해하기 위해 iterator category마다 적용될 수 있는 연산을 살폅도록 하자.

Let p : OutputIterator
   v, *p : T
        *p =  v (write)
        ++p, p++  (iteration)

Let p, k : InputIterator
   v, *p : T
        v = *p (read)
        p->
        ++p, p++  (iteration)
        p == k, p != k (equality comparable)

ForwardIterator는 InputIterator이자 OutputIterator다. BidirectionalIterator는 ForwardIterator에 역방향 이동을 추가한 것이다. RandomAccessIterator는:

Let p, k : RandomAccessIterator, i : difference_type
        p[i]
        p += k, p -= k
        p < k, p > k, p >= k, p <= k (Ordered)

위와 같이 Iterator의 분류는 매우 직관적이고 배우기 쉽다. 문법이 일반적인 포인터의 조작과 크게 다를 바가 없기 때문이다. 사실 위와 같은 분류에 따르자면 포인터 변수는 RandomAccessIterator에 포함된다.

두 마리 토끼를 잡는 법: Tag Dispatch Pattern #

예를 들어 The C++ Programming Language 3rd에서의 제시하는 예를 살펴보자. distance는 주어진 두 iterator간의 range 값을 얻어내는 함수다.

template<class InputIterator>
inline typename Iterator::difference_type
distance(InputIterator first, InputIterator last)
{ // O(n) time complexity
    typename Iterator::difference_type dist = 0;
    while (first++ != last) dist++;
    return dist;
}

그러나 RandomAccessIterator라면 위와 같은 구현은 매우 비효율적이며 다음과 같이 간단한 연산으로 계산하는 편이 낫다.

template<class RandomAccessIterator>
inline typename RandomAccessIterator::difference_type
distance(RandomAccessIterator first, RandomAccessIterator last)
{ // O(1) time complexity
    return last - first;
}

문제는 위와 같이 동일한 이름의 동일한 parameter를 가진 template함수가 공존할 수 없다는 점이다. 그러므로 STL의 설계자들은 객체지향적 방법을 빌지않고 특정 category의 Iterator를 위해 특화된 구현을 제공할 수 있는 동시에 동일한 인터페이스를 제공할 수 있는 방법이 필요했다.

만일 Iterator를 n 만큼 이동하는 연산 advance()를 구현한다고 가정하자.

template<class UnknownIterator, class Distance>
inline void advance(UnknownIterator& i, Distance n) { ... }

문제는 각각의 Iterator마다 적합한 알고리즘이 다르다는 것이다. ForwardIterator라면 i를 n만큼 하나씩 선형적으로 이동하는 방법이외에는 없으며 i를 되감을 수는 없기 때문에 n은 항시 양의 정수여야 한다. ⊕ 알고리즘의 복잡도 차이: ForwardIterator는 O(n), BidirectionalIterator도 O(n), 하지만 RandomAccessIterator는 O(1)입니다. 이런 차이를 runtime이 아닌 compile-time에 해결하는 것이 tag dispatch의 핵심입니다.

RandomAccessIterator는 보다 효율적인 구현이 가능하다. 앞의 두 함수는 O(n)의 계산방식이 필요하지만 이 경우엔 n을 i에 가감하는 것만으로 충분하다O(1).

결국 효율성과 일반성을 모두 잡아낼 수 있는 프로그래밍 기법이 필요한 것이다. C++ overloading 기능의 특성을 잘 활용하면 원하는 목표를 쉽게 달성할 수 있다. 아이디어 그 자체는 매우 단순하다. 실제 사용되지는 않지만 C++ 의 type deduction기능을 보조해주는 부가적인 인자를 하나 더 추가하는 것이다.

template<class InputIterator, class Distance>
inline void advance_with_tag(InputIterator& iter, Distance n, std::input_iterator_tag)
{
     while (n--) ++iter;
}

이제 BidirectionalIterator, RandomAccessIterator를 위한 advance_with_tag를 작성하자.

template <class BidirectionalIterator, class Distance>
inline void advance_with_tag(BidirectionalIterator& bi, Distance n,
                      bidirectional_iterator_tag) {
    if (n > 0) while (n--) ++bi;
    else while (n++) --bi;
}

template <class BidirectionalIterator, class Distance>
inline void advance_with_tag(BidirectionalIterator& i, Distance n,
                      random_access_iterator_tag) {
  i += n;
}

이제 남은 것은 Iterator category에 따라 각기 다른 구현을 호출할 수 있는 인터페이스 함수를 구현하는 일이다.

template <class InputIterator, class Distance>
inline void advance(InputIterator& i, Distance n)
{
    return advance_with_tag(i, n, typename InputIterator::iterator_category());
}

사용자는 iterator의 category에 대한 정보를 명시적으로 제공해야 할 필요가 전혀 없기 때문에 advance를 사용하더라도 특정 iterator에 의존하지 않는 포괄적함수를 작성할 수 있다. 헤더 파일을 통해 제공되는 거의 모든 알고리즘은 이와 같은 방식으로 작성된다.

마지막으로 표준 라이브러리가 제공하는 iterator_traits class가 왜 필요한 가를 이해하면서 이 단락을 마무리 짓도록 하자. traits class가 필요한 이유는 Iterator class로 구현되지 않았다 하더라도 표준 iterator의 속성을 공유할 수 있게 하기 위해서다. ⊕ iterator_traits의 역할: int* (built-in pointer)는 iterator base class를 상속하지 않습니다. 하지만 iterator_traits<int*>를 특화하여 같은 인터페이스를 제공할 수 있습니다. 이는 C++의 template specialization을 활용한 polymorphism입니다.

만일 traits class가 없다면 class로 구현되지 않는 iterator는 위에서 distance나 advance같은 함수를 사용할 수가 없다. 정수배열의 int* 같은 경우엔 Iterator::iterator_category같은 type attribute가 있을 수 없기 때문이다.

먼저 가장 일반적인 iterator_traits class는 다음과 같이 구현되어있다.

template <class Iterator>
struct iterator_traits {
  typedef typename Iterator::iterator_category iterator_category;
  typedef typename Iterator::value_type        value_type;
  typedef typename Iterator::difference_type   difference_type;
  typedef typename Iterator::pointer           pointer;
  typedef typename Iterator::reference         reference;
};

그러나 위의 구현은 단지 class로 구현된 iterator를 위한 정의이고 T* (포인터) iterator를 위해서는 별도의 구현이 필요하다.

template <class T>
struct iterator_traits<T*> { // Built-in Iterator
  typedef random_access_iterator_tag iterator_category;
  typedef T                          value_type;
  typedef ptrdiff_t                  difference_type;
  typedef T*                         pointer;
  typedef T&                         reference;
};

template <class T>
struct iterator_traits<const T*> {
  typedef random_access_iterator_tag iterator_category;
  typedef T                          value_type;
  typedef ptrdiff_t                  difference_type;
  typedef const T*                   pointer;
  typedef const T&                   reference;
};

iterator_traits class를 사용하여 advance를 수정하면:

template <class InputIterator, class Distance>
inline void advance(InputIterator& i, Distance n)
{
    return advance_with_tag(i, n, typename iterator_traits<InputIterator>::iterator_category());
}

위와 같다. 그리고 단순 배열이라고 해도 advance/distance같은 함수를 사용할 수 있다는 점이 무엇보다도 중요하다.

참고 문헌 및 웹 자료 #

원본 자료 #

• SGI STL - Iterator Documentation - 원본 STL iterator 설명서
• Bjarne Stroustrup - The C++ Programming Language

C++ 표준 문서 #

• cppreference: Iterators - 완전한 iterator 레퍼런스
• cppreference: std::iterator - iterator base class
• cppreference: Iterator categories - 5가지 iterator 분류

Iterator 고급 개념 #

• cppreference: iterator_traits - Traits pattern
• cppreference: std::distance - distance 알고리즘
• cppreference: std::advance - advance 알고리즘

C++20 현대화 #

• cppreference: Ranges - C++20 ranges 라이브러리
• cppreference: Concepts - C++20 concepts
• cppreference: Iterator concepts - Iterator formal concepts

관련 디자인 패턴 #

• GoF Design Patterns - Iterator Pattern
• Tag Dispatch Pattern - Modern C++ Techniques

역사 및 배경 #

• History of C++ - Templates - C++ 표준화 역사
• Alexander Stepanov - Generic Programming
• SGI STL Technical Papers

현대 언어의 유사 개념 #

• Rust Iterator Documentation - Rust의 iterator 시스템
• Python Iterators and Generators - Python generator 프로토콜
• JavaScript Iterators and Iterables - JS Symbol.iterator

[이 주석판은 1998-1999년의 세 편 연재 기사를 완성합니다. 각 파일은 역사적 의미와 2024년 현대적 관점을 모두 담고 있습니다.]