본문 바로가기
프로그래밍/C & C++

[C++] 템플릿과 상속 (EBCO, CRTP)

by 별준 2023. 12. 29.

References

  • Ch 21, C++ Templates The Complete Guide

Contents

  • The Empty Base Class Optimization (EBCO)
  • The Curiously Recurring Template Pattern (CRTP)

The Empty Base Class Optimization (EBCO)

비어있는(empty) C++ 클래스는 런타임에서 메모리를 요구하는 내부 표현이 없다는 것을 의미한다. 일반적으로 타입 멤버, nonvirtual 함수 멤버, 그리고 static 데이터 멤버만을 갖는 클래스를 empty class 라고 한다. 반면, nonstatic 데이터 멤버, virtual 함수, 그리고 virtual base 클래스는 런타임에 메모리를 필요로 한다.

 

하지만, empty class라고 하더라도 크기가 0인 것은 아니다.

#include <iostream>

class EmptyClass {};

int main()
{
    std::cout << "sizeof(EmptyClass): " << sizeof(EmptyClass) << std::endl;
}

대다수의 플랫폼에서 위 코드를 실행하면 "sizeof(EmptyClass): 1" 이라는 출력을 확인할 수 있다. 일부 시스템에서는 클래스 타입에 대해서 조금 더 엄격하게 정렬하기 때문에 1이 아닌 값을 출력할 수 있다.

 

Layout Principles

Empty 클래스의 크기가 0이 아닌 이유에는 여러 가지가 있다. 예를 들어, 이 클래스로 배열을 만들면 해당 배열 역시 크기가 0이 될 것이다. 따라서, 일반적인 포인터 연산의 속성이 더 이상 적용되지 않을 것이다. 예를 들어, ZeroSizedT의 크기가 0인 타입이라고 가정해보자.

ZeroSizedT z[10];
...
&z[i] - &z[j]; // compute distance between pointers/addresses

위의 3 line 코드는 일반적으로 두 주소 사이의 바이트 수를 포인터가 가리키고 있는 타입의 크기로 나눈 값을 반환하지만, 이 예시에서 ZeroSizedT의 크기가 0이므로 이 방식으로는 계산할 수 없다.

 

그러나, C++에서 크기가 0인 타입은 없지만 C++ 표준에서는 empty class가 base class로 사용되는 경우에는 같은 타입의 다른 객체나 하위 객체와 동일한 주소에 할당되지 않는 한 empty class에 공간을 할당할 필요가 없닥도 명시하고 있다. Empty Base Class Optimization (EBCO)라고 불리는 이 최적화가 실제로는 무엇을 의미하는지 아래 예시를 통해서 살펴보자.

#include <iostream>

class Empty {
    using Int = int; // type alias members don't make a class nonempty
};
class EmptyToo : public Empty {};
class EmptyThree : public EmptyToo {};


int main()
{
    std::cout << "sizeof(Empty):       " << sizeof(Empty) << std::endl;
    std::cout << "sizeof(EmptyToo):    " << sizeof(EmptyToo) << std::endl;
    std::cout << "sizeof(EmptyThree):  " << sizeof(EmptyThree) << std::endl;
}

컴파일러가 EBCO를 구현한다면, 모든 클래스는 같은 크기(일반적으로 1)를 출력하지만 이들 클래스 중에 크기가 0인 클래스는 없다.

이를 위 그림과 같이 표현할 수 있다. EmptyToo 클래스 내에서 Empty 클래스는 어떠한 공간도 차지 않는다는 의미이다. 또한, 최적화된 empty bases(and no other bases)를 갖는 empty class도 역시 empty가 된다. 따라서, EmptyThree 클래스의 크기가 Empty 클래스와 같다. 만약 컴파일러가 EBCO를 구현하지 않았다면 아래 그림과 같이 각각 다른 크기를 출력하게 된다.

EBCO의 제약을 받는 아래 예시를 살펴보자.

#include <iostream>

class Empty {
    using Int = int; // type alias members don't make a class nonempty
};
class EmptyToo : public Empty {};
class NonEmpty : public Empty, public EmptyToo {};

int main()
{
    std::cout << "sizeof(Empty):      " << sizeof(Empty) << std::endl;
    std::cout << "sizeof(EmptyToo):   " << sizeof(EmptyToo) << std::endl;
    std::cout << "sizeof(NonEmpty):   " << sizeof(NonEmpty) << std::endl;
}

위 코드에서 NonEmpty는 empty 클래스가 아니라는 것을 보여준다. 이 클래스는 base 클래스 이외에 다른 멤버를 갖지 않지만, base 클래스인 Empty와 EmptyToo에 같은 주소를 할당할 수 없다. 같은 주소를 할당한다면 EmptyToo의 base 클래스(Empty)와 NonEmpty의 base 클래스(Empty)가 결과적으로 같은 주소를 갖게 되기 때문이다. 즉, 동일한 타입의 두 하위 객체가 결과적으로 동일한 offset에 위치하게 되며, 이는 C++의 object layout rules에서 허용되지 않는다. NonEmpty 클래스의 Base 클래스인 Empty 클래스 중 하나는 offset 0 바이트, 다른 하나는 offset 1 바이트에 배치되도록 결정하는 것이 가능하지만 전체 NonEmpty 객체는 아래 1 바이트의 크기를 가질 수 없다 (아래 그림 참조). 

EBCO에 대한 제약의 근거는 두 포인터가 동일한 객체를 가리키는지 여부를 비교할 수 있는 것이 바람직하다라는 사실에서 비롯된다. 포인터는 대부분 내부적으로 단지 주소로만 표현되기 때문에 주소가 서로 달라야 다른 객체라고 확인할 수 있다.

 

이러한 제약 조건이 중요해 보이지 않을 수도 있다. 하지만 실제로 많은 클래스들에서 공통의 type aliases만 정의하는 empty 클래스들을 상속받는 경우가 많다. 따라서 이와 같은 클래스의 두 하위 객체가 동일 객체 내에서 사용된다면 두 하위 객체는 최적화되지 않는다.

이러한 제약 조건에도 EBCO는 템플릿 라이브러리에서 중요한 최적화 방식이다. 수 많은 기법에서 새로운 type alias를 도입하거나 데이터는 추가하지 않으면서 기능을 추가하는 목적만을 위해 base 클래스를 도입하기 때문이다.

 

Members as Base Classes

EBCO에는 데이터 멤버에 해당하는 것을 갖지 않는데, 데이터 멤버를 가지면 멤버에 대한 포인터 표현에 몇 가지 문제가 발생할 수 있기 때문이다. 결과적으로 멤버 변수로 생각되는 것을 (private) base 클래스로 구현하는 것이 바람직할 때도 있지만, 여기에는 나름의 문제가 있다.

템플릿 문맥에서는 템플릿 파라미터는 empty 클래스 타입으로 치환될 수 있다. 템플릿 타입 파라미터에 대해서 알려진 것이 없다면 EBCO를 쉽게 이용할 수 없다. 아래의 간단한 예제를 살펴보자.

template<typename T1, typename T2>
class MyClass {
private:
    T1 a;
    T2 b;
    ...
};

위 코드에서 템플릿 파라미터는 emtpy 클래스 타입으로 치환될 수 있다. 그렇다면 MyClass<T1, T2>라는 표현은 최적이 아닐 것이며, MyClass<T1, T2>를 인스턴스화할 때마다 메모리를 낭비하게 된다.

템플릿 인자를 base 클래스로 만들면 이 문제를 피할 수 있다.

template<typename T1, typename T2>
class MyClass : private T1, private T2 {};

그러나 여기에도 나름의 문제가 있다.

  • 이와 같은 방식은 T1이나 T2가 클래스가 아닌 타입이나 union 타입으로 치환되는 경우 제대로 동작하지 않는다.
  • 또한 두 파라미터가 같은 타입으로 치환되면 동작하지 않는다 (상속 단계를 더 추가하면 쉽게 해결할 수는 있음).
  • 인자로 치환된 클래스가 final이라면 에러가 발생한다.

위와 같은 문제를 해결하더라도 base 클래스를 추가하기 위해 주어진 클래스의 인터페이스를 바꿔야 한다는 문제는 계속 남는다. 위의 MyClass 클래스의 경우에는 영향을 받는 인터페이스가 없으므로 문제가 되진 않지만, 템플릿 파라미터에서 상속받게 된다면 멤버 함수가 virtual인지 아닌지에 영향을 미치게 된다. 분명히 EBCO를 활용하는 이러한 방식에는 많은 문제로 가득 차 있다.

 

템플릿 파라미터가 클래스 타입으로 치환된다고 알려져 있고, 클래스 템플릿의 다른 멤버를 사용할 수 있는 일반적인 경우에 대해 보다 실용적인 방법이 사용될 수 있는데, 주요 아이디어는 EBCO를 사용하여 잠재적인 empty 타입 파라미터를 다른 멤버와 병합하는 것이다. 예를 들어, 아래와 같은 코드 대신

template<typename CustomClass>
class Optimizable {
private:
    CustomClass info;  // might be empty
    void* storage;
    ...
};

아래와 같이 구현하는 것이 낫다.

template<typename CustomClass>
class Optimizable {
private:
    BaseMemberPair<CustomClass, void*> info_and_storage;
    ...
};

BaseMemberPair의 구현을 살펴보자 읺더라도 Optimizable의 구현이 장황해졌다는 것은 분명하다. 하지만 다양한 템플릿 라이브러리에 따르면 이러한 클래스를 사용했을 때 얻는 성능 향상이 더 크기 때문에 쓸만하다고 한다.

 

BaseMemberPair의 구현은 꽤 간결하다.

template<typename Base, typename Member>
class BaseMemberPair : private Base {
private:
    Member mem;

public:
    // constructor
    BaseMemberPair(Base const& p, Member const& m) : Base(b), mem(m) {}
    // access base class data via first()
    Base const& base() const {
        return static_cast<Base const&>(*this);
    }
    Base& base() {
        return static_cast<Base&>(*this);
    }
    // access member data via second()
    Member const& member() const {
        return this->mem;
    }
    Member& member() {
        return this->mem;
    }
};

위와 같은 구현에서 캡슐화된(and possibly storage-optimized) 데이터 멤버에 접근하기 위해서 first()와 second()라는 멤버 함수를 사용해야 한다.

 

아래에서 이러한 기법들을 활용하는 여러 패턴들에 대해서 살펴볼 예정이다.

The Curiously Recurring Template Pattern (CRTP)

CRTP라는 다른 패턴도 있다. 이 패턴은 derived 클래스를 템플릿 인자로 base 클래스 중 하나에 전달하는 기법을 사용하는 클래스를 일컫는다. 이를 간단히 구현한 코드는 다음과 같다.

template<typename Derived>
class CuriousBase {
    ...
};

class Curious : public CuriousBase<Curious> {
    ...
};

위 예제에서는 nondependent base 클래스를 보여준다. Curious 클래스는 템플릿이 아니고, 따라서, 중속된 base class의 name visibility 문제에 안전하다. 그러나, 이는 CRTP의 고유 특성은 아니다. 대신, 아래의 다른 예제 코드를 살펴보자.

template<typename Derived>
class CuriousBase {
    ...
};

template<typename T>
class CuriousTemplate : public CuriousBase<CuriousTemplate<T>> {
    ...
};

파생 클래스(CuriousTemplate)을 이의 base 클래스의 템플릿 파라미터로 전달하면 base 클래스는 virtual 함수를 사용하지 않고 derived 클래스에 자신의 동작을 커스터마이즈할 수 있다. 멤버 함수(constructor, destructor, subscript operators)만 가능하거나, derived 클래스에 종속된 구현이 필요할 때 CRTP를 유용하게 사용할 수 있다.

 

CRTP를 간단히 응용하면 특정 클래스 타입의 객체가 얼마나 많이 생성되었는지 추적할 수 있다. 모든 생성자에서 정수형 static 데이터 멤버를 증가시키고 소멸자에서 그 값을 감소시켜서 이를 쉽게 구현할 수 있다. 이를 모든 클래스에 제공하는 것은 귀찮을 수 있다. 또한, 이 기능을 CRTP가 아닌 단 하나의 base 클래스를 통해 구현하려면 여러 derived 클래스의 객체를 카운트할 때 혼동될 수 있다. 대신 아래와 같은 템플릿을 사용해보자.

#include <cstddef>

template<typename CountedType>
class ObjectCounter {
private:
    inline static std::size_t count = 0; // number of existing objects

protected:
    // default constructor
    ObjectCounter() {
        ++count;
    }
    // copy constructor
    ObjectCounter(ObjectCounter<CountedType> const&) {
        ++count;
    }
    // move constructor
    ObjectCounter(ObjectCounter<CountedType>&&) {
        ++count;
    }
    // destructor
    ~ObjectCounter() {
        --count;
    }

public:
    // return number of existing objects
    static std::size_t live() {
        return count;
    }
};

특정 클래스 타입에 대한 소멸되지 않은 객체의 수를 카운트하고 싶다면 해당 클래스를 ObjectCounter 템플릿에서 파생시키면 된다. 예를 들어, 다음과 같이 객체의 갯수를 카운트하는 문자열 클래스를 정의하는데 사용할 수 있다.

template<typename CharT>
class MyString : public ObjectCounter<MyString<CharT>> {
};

int main()
{
    MyString<char> s1, s2;
    MyString<wchar_t> ws;
    std::cout << "num of MyString<char>: " << MyString<char>::live() << std::endl;
    std::cout << "num of MyString<wchar_t>: " << MyString<wchar_t>::live() << std::endl;
}

 

The Barton-Nackman Trick

이 기법은 당시 함수 템플릿이 오버로딩이 될 수 없다는 사실과 대부분의 컴파일러에서 네임스페이스를 지원하지 않았다는 사실을 이용해 만들어진 기법이다.

 

'==' 연산자를 정의하려는 템플릿 클래스 Array가 있다고 가정해보자. 이 연산자를 클래스 템플릿의 멤버로 선언할 수 있지만, this 포인터에 바인딩되어 있는 첫 번째 인자가 두 번째 인자와 다른 conversion rules을 따르기 때문에 좋은 practice는 아니다. '==' 연산자는 각각의 인자에 대칭을 이루도록 되어 있으므로 namespace 범위 함수로 선언하는 것이 좋다. 따라서, 아래와 같은 구현이 일반적이다.

template<typename T>
class Array {
public:
    ...
};

template<typename T>
bool operator==(Array<T> const& a, Array<T> const& b) {
    ...
}

그러나 함수 템플릿을 오버로딩할 수 없다면, 이 코드로 인해 문제가 발생한다. 이 scope에서 다른 == 연산자를 선언할 수 없지만, 다른 클래스 템플릿에 대해 == 연산자 템플릿이 필요할 수 있다. Barton과 Nackman은 이 문제를 클래스 내에서 normal friend function으로 정의된 연산자를 정의하여 해결하였다.

template<typename T>
class Array {
    static bool areEqual(Array<T> const& a, Array<T> const& b);
public:
    ...
    friend bool operator==(Array<T> const& a, Array<T> const& b) {
        return areEqual(a, b);
    }
};

Array<float>로 인스턴스화되었다고 가정해보자. 그 결과로 friend 연산자 함수가 선언되지만, 이 함수 자체는 함수 템플릿의 인스턴스가 아니다. 이 함수는 템플릿이 아닌 일반 함수이며, 인스턴스 과정에 따라서 global scope에서 주입되었다. 따라서, 함수 템플릿의 오버로딩이 언어 기능으로 추가되기 전에도 == 연산자를 오버로딩할 수 있었다.

 

1994년 이후 friend function 정의에 대한 name lookup 방식이 변경되었기 때문에 표준 C++에서 Barton-Nackman trick이 예전만큼 유용하지는 않다.

표준 C++에서는 이제 argument-dependent lookup을 통해 friend 함수 선언을 찾는다. 즉, 함수 호출에서의 인자 중에서 적어도 하나는 friend 함수를 포함하는 클래스를 연관된 클래스로 포함하고 있어야 한다는 것을 의미한다. 인자가 friend 함수를 포함하는 클래스로 변환될 수 있지만 직접적으로 관련되지 않는 클래스 타입일 경우에는 friend 함수가 발견되지 않는다. 아래 예시 코드를 통해서 이를 확인할 수 있다.

class S {};

template<typename T>
class Wrapper {
private:
    T object;
public:
    Wrapper(T obj) : object(obj) {} // implicit conversion from T to Wrapper<T>
    friend void foo(Wrapper<T> const&) {}
};

int main()
{
    S s;
    Wrapper<S> w(s);
    foo(w);     // OK: Wrapper<S> is a class associated with w
    foo(s);     // ERROR: Wrapper<S> is not associated with s
}

위 예제 코드에서 함수 foo()는 Wrapper<S>, 즉, w와 관련된 클래스에 선언되어 있는 friend 이므로 foo(w)의 호출은 유효하다. 하지만 foo(s) 호출에서 foo(Wrapper<S> const&) 함수는 S 타입의 인자인 s와 관련이 없는 Wrapper<S> 클래스에 선언되어 있으므로 visible하지 않다. 따라서 S 타입에서 Wrapper<S>로 유효한 implicit conversion(Wrapper<S>의 생성자)이 있더라도 condidate function으로 foo가 발견되지 않기 때문에 이 변환은 절대로 고려되지 않는다. Barton-Nackman Trick에서는 friend name injection을 통해 friend 함수인 foo()가 visible하므로 foo(s) 호출이 성공할 것이다.

 

모던 C++에서 클래스 템플릿에 friend 함수를 선언하는 것이 그냥 일반 함수 템플릿을 정의하는 것보다 나은 점은 문법적인 면밖에 없다.

Friend 함수 선언은 자신을 둘러싸고 있는 클래스의 private과 protected 멤버에 접근할 수 있고, 클래스 템플릿의 템플릿 파라미터 전체를 다시 써줄 필요가 없다. 하지만 friend 함수 정의가 CRTP와 결합되면 유용하게 사용할 수 있는데, 아래의 Operator Implementations에서 조금 더 자세히 살펴보자.

 

Operator Implementations

연사자를 오버로딩하는 클래스를 구현할 때, 서로 다르지만 관련있는 연산자들을 모두 오버로딩하는 것이 일반적이다. 예를 들어, == 연산자를 구현한다면 != 연산자도 구현할 가능성이 높고, < 연산자를 구현하는 경우에는 관련된 다른 연산자(>, <=, >=)도 구현할 가능성이 높다. 대다수의 경우에는 이들 연산자 중 하나의 정의만 실제로 필요하고 나머지는 그 연산자로 정의할 수 있다. 예를 들면, != 연산자는 == 연산자를 사용하여 정의할 수 있다.

bool operator!=(X const& x1, X const& x2) {
    return !(x1 == x2);
}

많은 타입들이 != 연산자를 위와 비슷한 방식으로 정의하므로 이를 템플릿으로 바꾸면 편리할 것이다.

template<typename T>
bool operator!=(T const& x1, T const& x2) {
    return !(x1 == x2);
}

실제로 C++ 표준 라이브러리에도 위와 같은 정의가 <utility> 헤더에 포함되어 있다. 다만, std 네임스페이스에 위치할 경우에 문제가 발생할 수 있어서 std::rel_ops 네임스페이스에 정의되어 있다. std 네임스페이스에 위치시키는 경우, 이들 정의가 visible일 때 인스턴스화에 실패하고 두 인자 모두에 정확히 일치해야 한다는 문제가 발생한다고 한다 (어떤 문제인지 명확하게 이해하지는 못했다). 예를 들어, != 연산자를 가지는 어떤 타입에서 이러한 문제가 발생할 수 있다고 언급하고 있다. 다만, 이러한 문제는 적절한 == 연산자를 가진 타입에 대해서만 템플릿화된 != 정의를 인스턴스화하도록 하여 해결할 수 있다고 한다. 하지만, 다른 문제가 하나 남아있는데, 템플릿화된 제너럴한 정의는 파생 클래스에서 베이스 클래스로 변환히 필요한 사용자 정의보다 선호된다는 것이다.

 

이러한 연산자 템플릿은 CRTP를 베이스로하여 다르게 구현할 수 있다. CRTP를 사용하면 제너럴한 연산자 정의가 가능하여 코드 재사용성이 높아지면서 지나치게 제너럴한 연산자를 선호하는 문제도 해결할 수 있다.

template<typename Derived>
class EqualityComparable {
public:
    friend bool operator!=(Derived const& x1, Derived const& x2) {
        return !(x1 == x2);
    }
};

class X : public EqualityComparable<X>
{
public:
    friend bool operator==(X const& x1, X const& x2) {
        // implement logic for comparaing two objects of type X
        return true;
    }
};

int main()
{
    X x1, x2;
    if (x1 != x2) {}
}

위 구현은 CRTP와 Barton-Nackman trick을 결합하였다. EqualityComparable<>은 CRTP를 사용하여 파생된 클래스의 operator== 정의를 기반하여 파생된 클래스의 operator!=를 제공한다.

 

CRTP를 사용하면 최종적으로 만들어지는 파생 클래스의 정체성을 유지하면서 동작은 베이스 클래스로 분해할 때 유용하다. Barton-Nackman trick을 함께 사용하면 몇 가지 연산을 기반으로 다양한 연산자에 대한 제너럴한 정의를 제공할 수 있다.

Facades

CRTP와 Barton-Nackman trick을 조금 더 확장하면 CRTP 베이스 클래스로 클래스의 public 인터페이스의 대부분 또는 전체 인터페이스를 CRTP 파생 클래스에서 노출하는 더 작은 인터페이스로 정의할 수 있다. 즉, CRTP 파생 클래스의 인터페이스 구현을 기반으로 클래스의 많은 인터페이스를 쉽게 구현할 수 있다는 것이다. 이러한 패턴을 파사드(facade) 패턴이라고 한다.

 

쉽게 와닿지 않을 수 있는데, 파사드 패턴으로 반복자를 구현해보면서 자세히 살펴보자.

파사드 패턴을 활용하면 표준 라이브러리의 요구 사항을 만족시키는 반복자를 만드는 과정을 획기적으로 줄일 수 있다. 반복자 타입에 필요한 인터페이스는 상당히 많으며, 타입에 따라서 제공해야 하는 인터페이스가 증가한다. 클래스 템플릿 IteratorFacade를 구현하는 뼈대를 보면서 반복자 인터페이스에 요구되는 사항이 무엇인지 살펴보자.

template<typename Derived, typename Value, typename Category,
         typename Reference = Value&, typename Distance = std::ptrdiff_t>
class IteratorFacade
{
public:
    using value_type = std::remove_const_t<Value>;
    using reference = Reference;
    using pointer = Value*;
    using difference_type = Distance;
    using iterator_category = Category;

    // input iterator interface
    reference operator*() const { ...}
    pointer operator->() const { ... }
    Derived& operator++() { ... }
    Derived operator++(int) { ... }
    friend bool operator==(IteratorFacade const& lhs, IteratorFacade const& rhs) { ... }
    ...
    // bidirectional iterator inferface
    Derived& operator--() { ... }
    Derived operator--(int) { ... }
    
    // random access iterator interface
    reference operator[](difference_type n) const { ... }
    Derived& operator+=(difference_type n) { ... }
    ...
    friend difference_type operator-(IteratorFacade const& lhs, IteratorFacade const& rhs) { ... }
    friend bool operator<(IteratorFacade const& lhs, IteratorFacade const& rhs) { ... }
    ...
};

간결하게 표현하기 위해 일부 선언은 생략되어 있다. 그럼에도 구현할 인터페이스가 상당히 많다는 것을 알 수 있는데, 다행히 이 인터페이스들은 몇 가지 핵심 연산으로 줄일 수 있다.

  • For all iterators:
    • dereference() - 반복자가 가리키는 값에 액세스 (일반적으로 * 연산자와 -> 연산자 사용)
    • increment() - 반복자를 이동시켜 시퀀스 내 다음 요소를 가리키도록 함
    • equals() - 두 반복자가 시퀀스 내 동일한 요소를 가리키는지 체크
  • For bidirectional iterators:
    • decrement() - 반복자를 이동시켜 시퀀스 내 이전 요소를 가리키도록 함
  • For random-access iterators:
    • advance() - 반복자를 n 스텝만큼 앞으로 또는 뒤로 이동
    • measureDistance() - 한 반복자를 시퀀스 내 다른 반복자로 이동시킬 때 필요한 스텝 계산

파사드의 역할이 핵심 연산을 다른 인터페이스에 적용하는 것이므로, 반복자 인터페이스 전체를 구현하기 위한 핵심 연산자만 구현하면 된다. IteratorFacade의 대부분은 반복자 문법을 최소한의 인터페이스에 대응시키도록 구현하는 것 뿐이다. 

 

아래 예제 코드에서는 asDerived()라는 멤버 함수를 통해 CRTP 파생 클래스에 접근하며, 나머지 구현은 직관적이다. 여기서는 operator*, operator++, operator== 만 구현하였다.

template<typename Derived, typename Value, typename Category,
         typename Reference = Value&, typename Distance = std::ptrdiff_t>
class IteratorFacade
{
public:
    using value_type = std::remove_const_t<Value>;
    using reference = Reference;
    using pointer = Value*;
    using difference_type = Distance;
    using iterator_category = Category;

    // input iterator interface
    reference operator*() const {
        return asDerived().dereference();
    }
    Derived& operator++() {
        asDerived().increment();
        return asDerived();
    }
    Derived operator++(int) {
        Derived result(asDerived());
        asDerived().increment();
        return result;
    }

    friend bool operator==(IteratorFacade const& lhs, IteratorFacade const& rhs) {
        return lhs.asDerived().equals(rhs.asDerived());
    }

private:
    Derived& asDerived() { return *static_cast<Derived*>(this); }
    Derived const& asDerived() const {
        return *static_cast<Derived const*>(this);
    }
};

 

Defining a Linked-List Iterator

앞서 구현한 IteratorFacade를 사용하여 간단한 linked list 클래스에 대한 반복자를 구현해보자. 이 구현은 IteratorFacade에서 필요로 하는 인터페이스를 위한 dereference(), increment(), equals() 인터페이스만 구현해주면 된다.

template<typename T>
class ListNode
{
public:
    T value;
    ListNode<T>* next = nullptr;
    ~ListNode() { delete next; }
};

template<typename T>
class ListNodeIterator
: public IteratorFacade<ListNodeIterator<T>, T, std::forward_iterator_tag>
{
    ListNode<T>* current = nullptr;

public:
    T& dereference() const {
        return current->value;
    }
    void increment() {
        current = current->next;
    }
    bool equals(ListNodeIterator const& other) const {
        return current == other.current;
    }
    ListNodeIterator(ListNode<T>* current = nullptr) : current(current) {}
};

이 예제에서는 forward iterator로 동작하기 위해 필요한 구현만 제공한다. 조금 더 복잡한(양방향, random-access) 반복자를 정의할 때에서 구현은 그리 많지 않다.

Hiding the interface

위에서 구현한 IteratorFacade의 단점은 ListNodeIterator의 dereference(), equals()와 같은 연산을 public 인터페이스로 노출시켜야 한다는 점이다. 이러한 요구 사항을 없애려면 IteratorFacadeAccess라는 분리된 액세스 클래스를 통해 파생된 CRTP 클래스에서 모든 연산을 수행하도록 IteratorFacade를 수정해면 된다.

template<typename Derived, typename Value, typename Category,
         typename Reference = Value&, typename Distance = std::ptrdiff_t>
class IteratorFacade;

// 'friend' this class allow IteratorFacade access to core iterator operations
class IteratorFacadeAccess
{
    // only IteratorFacade can use these definition
    template<typename Derived, typename Value, typename Category,
             typename Reference, typename Distance>
    friend class IteratorFacade;

    // input iterator interface
    template<typename Reference, typename Iterator>
    static Reference dereference(Iterator const& i) {
        return i.dereference();
    }
    template<typename Iterator>
    static void increment(Iterator& i) {
        i.increment();
    }
    template<typename Iterator>
    static bool equals(Iterator const& li, Iterator const& ri) {
        return li.equals(ri);
    }
};

template<typename Derived, typename Value, typename Category,
         typename Reference, typename Distance>
class IteratorFacade
{
public:
    using value_type = std::remove_const_t<Value>;
    using reference = Reference;
    using pointer = Value*;
    using difference_type = Distance;
    using iterator_category = Category;

    // input iterator interface
    reference operator*() const {
        return IteratorFacadeAccess::dereference<reference>(asDerived());
    }
    Derived& operator++() {
        IteratorFacadeAccess::increment(asDerived());
        return asDerived();
    }
    Derived operator++(int) {
        Derived result(asDerived());
        IteratorFacadeAccess::increment(asDerived());
        return result;
    }

    friend bool operator==(IteratorFacade const& lhs, IteratorFacade const& rhs) {
        return IteratorFacadeAccess::equals(lhs.asDerived(), rhs.asDerived());
    }
    friend bool operator!=(IteratorFacade const& lhs, IteratorFacade const& rhs) {
        return !(IteratorFacadeAccess::equals(lhs.asDerived(), rhs.asDerived()));
    }

private:
    Derived& asDerived() { return *static_cast<Derived*>(this); }
    Derived const& asDerived() const {
        return *static_cast<Derived const*>(this);
    }
};

여기서 핵심은 필요한 핵심 연산 각각에 대해 정적 멤버 함수를 제공하여 제공된 반복자의 (non-static) 멤버 함수를 호출한다. 정적 멤버 함수들은 private 멤버이므로 IteratorFacade 내에서만 액세스가 가능하다. 따라서 NodeListIterator는 IteratorFacadeAccess를 friend로 선언하여 파사드가 원하는 인터페이스를 private로 유지할 수 있다.

template<typename T>
class ListNode
{
public:
    T value;
    ListNode<T>* next = nullptr;
    ~ListNode() { delete next; }
};

template<typename T>
class ListNodeIterator
: public IteratorFacade<ListNodeIterator<T>, T, std::forward_iterator_tag>
{
    friend class IteratorFacadeAccess;
    ListNode<T>* current = nullptr;

    T& dereference() const {
        return current->value;
    }
    void increment() {
        current = current->next;
    }
    bool equals(ListNodeIterator const& other) const {
        return current == other.current;
    }
public:
    ListNodeIterator(ListNode<T>* current = nullptr) : current(current) {}
};


int main()
{
    ListNode<int> head{1};
    head.next = new ListNode<int>{2};
    head.next->next = new ListNode<int>{3};

    auto it = ListNodeIterator(&head);
    std::cout << *it << std::endl;
    ++it;
    std::cout << *it << std::endl;

    return 0;
}

Iterator Adapters

IteratorFacade를 사용하면 현재 반복자를 받아서 실제 시퀀스에 대한 변형된 view를 제공하는 새로운 반복자를 리턴하는 반복자 어댑터도 쉽게 만들 수 있다. 예를 들어, 아래의 Person 이라는 값을 저장하는 컨테이너가 있다고 가정해보자.

struct Person {
    std::string firstName;
    std::string lastName;

    friend std::ostream& operator<<(std::ostream& os, Person const& p) {
        return os << p.lastName << ", " << p.firstName;
    }
};

여기서 컨테이너 내의 모든 Person 값을 반복하는 것이 아니라 firstName만 살펴보고 싶고, 이를 가능케 해주는 반복자 어댑터 ProjectionIterator를 구현한다. 이 클래스는 데이터 멤버에 대한 포인터를 위해 기본 반복자의 값을 투영한다.

template<typename Iterator, typename T>
class ProjectionIterator : public IteratorFacade<ProjectionIterator<Iterator, T>,
                                                 T,
                                                 typename std::iterator_traits<Iterator>::iterator_category,
                                                 T&,
                                                 typename std::iterator_traits<Iterator>::difference_type>
{
    using Base = typename std::iterator_traits<Iterator>::value_type;
    using Distance = typename std::iterator_traits<Iterator>::difference_type;

    Iterator iter;
    T Base::* member;

    friend class IteratorFacadeAccess;

    T& dereference() const {
        return (*iter).*member;
    }
    void increment() {
        ++iter;
    }
    bool equals(ProjectionIterator const& other) const {
        return iter == other.iter;
    }

public:
    ProjectionIterator(Iterator iter, T Base::* member) : iter(iter), member(member) {}
};

template<typename Iterator, typename Base, typename T>
auto project(Iterator iter, T Base::* member) {
    return ProjectionIterator<Iterator, T>(iter, member);
}

위 구현은 다음과 같이 사용할 수 있다.

int main()
{
    std::vector<Person> authors = {
        {"David", "Vandevoorde"},
        {"Nicolai", "Josuttis"},
        {"Douglas", "Gregor"}
    };
    std::copy(project(authors.begin(), &Person::firstName),
            project(authors.end(), &Person::firstName),
            std::ostream_iterator<std::string>(std::cout, "\n"));

    return 0;
}

위 코드는 authors 컨테이너 각 Person 객체의 firstName을 한 줄에 하나씩 출력한다.

'프로그래밍 > C & C++' 카테고리의 다른 글

[C++] Argument Parser (python argparse like)  (0) 2024.01.02
[C++] Tuple 구현  (0) 2024.01.01
[C++] Typelists  (0) 2023.12.23
[C++] 메타프로그래밍  (0) 2023.12.16
[C++] Type Erasure  (4) 2023.12.15

관련글

댓글

​

티스토리툴바