[Effective STL] 10. 할당자(Allocator)의 제약 사항

항목 10. 할당자(allocator)의 일반적인 사항과 제약 사항에 대해 잘 알아두자

 

 

 

할당자의 기원

• 16비트 운영체제(DOS) 시절, 라이브러리 제작자들이 near, far 포인터 구분에 힘을 덜 쓸 수 있도록
• 메모리 모델의 추상층으로 개발된 것이다.
• 그처럼 STL 할당자 역시 객체 메모리 관리를 편하게 하기 위해 설계되었다.

 

 

 

STL 할당자의 문제

• 몇몇 부분에서 효율성 저하가 판명되었다.
• 사실상 operator new, operator new[]와 동일한 기능이지만, 인터페이스는 전혀 비슷하지 않다.
  • 심지어 malloc과도 비슷하지 않다.

 

 

 

할당자의 제약 사항 1. pointer / reference 타입

• 할당자는 자신에게 정의된 메모리 모델의 포인터와 참조자에 대한 typedef 타입을 제공한다.(모던에서는 using)
  • C++ 표준안에 따르면... 
  • 타입 T에 대한 디폴트 할당자(std::allocator<T>)의 경우 아래와 같은 typedef 타입을 제공한다.
    • std::allocator<T>::pointer
    • std::allocator<T>::reference
  • 사용자 정의 할당자도 이런 형식으로 typedef 타입을 제공하도록 정해져 있다.
• 헌데, C++에서는 참조자를 흉내낼 수 있는 방법이 없다. reference 타입을 어떻게 제공해야 할까?
  • 프록시 객체를 쓸 수 있겠지만, 그럼에도 문제점이 있다.(항목 18 참조)(MEC++ 항목 30 참조)
• 더군다나 pointer / refercne 타입을 잘 지정했다손 쳐도, T*, T&를 직접 사용해버리는 STL 구현 코드들에서는 의미가 없다.

 

 

 

할당자의 제약 사항 2. 동일한 타입의 할당자 객체간의 동등 제약

• 그리고 할당자는 객체이다.
  • 멤버 함수, 중첩(nested) 타입, typedef 타입(pointer, reference 등)을 가질 수 있다는 뜻이다.
  • 하지만 표준안에 의하면 같은 타입의 모든 할당자 객체는
    • 동등(equivalent)하며 항상 상등 비교(compare equal)를 수행한다고 가정하고 구현되어야 한다고 한다.

  • template<typename T>
    class SpecialAllocator { ... };
    typedef SpecialAllocator<Widget> SAW; // SpecialAllocator for Widget
    
    list<Widget, SAW> L1;
    list<Widget, SAW> L2;
    ...
    L1.splice(L1.begin()), L2); // L2의 노드를 L1의 앞으로 옮긴다.

  • 이 상황에서 L1이 삭제된다고 하면?
    • L1 기존의 노드들은 L1의 할당자로 해제가 된다.
    • L2에서 온 노드들은? L1의 할당자로 해제되어도 되는가?
    • 그렇기에 같은 타입의 모든 할당자는 동등해야 한다는 표준안이 있는 것이다.
• 타입 별 할당자 객체는 동등해야 한다는 제약은 무척 가혹하다.
  • 이식 가능한 할당자(다른 STL 구현 코드에서도 제대로 동작하는 할당자) 객체는 상태를 가지면 안된다는 뜻이므로.
  • 상태를 가지지 않는단 말은, 비정적(non-static) 데이터 멤버가 없어야 함을 뜻한다.
  • 즉, 힙에서 메모리를 할당하는 SpecialAllocator<int>와 다른 힙에서 메모리를 할당하는 SpecialAllocator<int>는 동시에 존재할 수 없다.
    • 이 두 할당자는 동등하다고 할 수 없기 때문이다.
  • 그리고 이 동등 제약은 컴파일러가 잡아내 주지 않는다.
    • 사용자가 전적으로 지키도록 노력해야 한다...

 

 

 

할당자의 제약 사항 3. 이질적인 인터페이스

• 동일하게 저수준 메모리 할당을 수행하는 operator new와 인터페이스가 전혀 다르다.

// operator new 인터페이스
// 매개변수로 바이트 수를 받는다.
// 리턴값으로 raw pointer를 제공한다.
void* operator new(size_t bytes);

// allocator 인터페이스
// 매개변수로 객체의 갯수를 받는다.
// 리턴값으로 T*를 제공한다.(pointer는 거의 항상 T*라고 봐도 좋다.)
// 헌데.. 아래에서 상세히 설명한다.
pointer allocator<T>::allocate(size_type numObjects);

• 매개변수의 차이
  • sizeof(int) == 4인 플랫폼이 있다면,
    • operator new에는 4를 넘겨야 한다.
    • allocator<T>::allocate에는 1을 넘겨야 한다.
• 리턴값의 차이
  • allocator<T>::allocate에서는 T*를 반환한다.
  • 하지만, 이는 사기극이나 마찬가지이다.
  • 사실 리턴된 포인터는 T 객체를 가리키지 않는다.
  • 왜냐하면 T는 아직 만들어지지조차 않았기 때문이다.
  • 실제로 T 객체를 만드는 것은 allocator<T>::allocate를 호출하는 호출자(caller)이다.

 

 

 

할당자의 제약 사항 4. 컨테이너에서는 호출되지 않는 할당자

• 대부분의 표준 컨테이너는 자신이 생성될 때, 같이 붙어온 할당자를 한 번도 호출하지 않는다.

list<int> L; // list< int, allocator<int> >와 똑같다.
// 하지만 allocator<int>는 전혀 불리지 않는다.

set<Widget, SAW> S;
// 역시 SAW는 전혀 불리지 않는다.

• list의 구현을 잠깐 살펴보자면

template< typename T, typename Allocator = allocator<T> >
class list
{
pirvate:
    Allocator alloc; // 타입 T의 객체에 대한 할당자
    
    // 연결 리스트 내의 노드
    struct ListNode
    {
        T data;
        ListNode* prev;
        ListNode* next;
    };
    ...
}

• 리스트에 새 노드가 하나 추가되면 할당자에서 필요한 메모리를 떼어 와야 할 것이다.
  • 헌데 리스트가 필요한 것은 T 크기의 메모리가 아니라 T를 담고 있는 ListNode에 대한 메모리이다!
  • 근데 Allocator는 ListNode가 아니라 T를 할당해준다..
• 할당자 쪽에서 이런 일을 해주는 typedef 타입이 있긴 하다.
  • other 라는 이름이다.
  • 하지만, other는 rebind라는 구조체 안에 들어 있는 중첩 typedef 타입인데,
  • rebind 자체 역시 할당자 클래스 안에 중첩되어 있고,
  • 할당자 클래스는 템플릿이다.

template<typename T>
class allocator
{
public:
    template<typename U>
    struct rebind
    {
        typedef allocator<U> other;
    };
    ...
};

// ListNode에 대한 템플릿 타입 매개변수를 지정해 주어야 하므로, 아래와 같아질 것이다.
// Allocator::rebind<ListNode>::other

• 결론적으로, 커스텀 할당자를 만들기로 마음 먹었고, 표준 컨테이너에서도 사용할 생각이라면
  
  • 반드시 rebind 템플릿을 제공해야 한다.
  • 표준 컨테이너는 이것이 있을 것으로 가정하기 때문이다.

 

 

 

정리

• 표준 컨테이너를 지원하는 커스텀 할당자를 만들 때는 아래 규칙을 따르자.
  • 할당자를 템플릿으로 만들자.
  • pointer와 reference라는 typedef 타입을 제공하되,
    • 항상 pointer는 T*, reference는 T&이도록 하자.
  • 확장성, 동등성을 보장하기 위해 할당자에는 비정적 데이터 멤버를 넣지 말자.
  • 이질적인 할당자의 allocate 인터페이스를 숙지하자.
    • 매개변수로는 객체의 갯수를 넘긴다.
    • 리턴값으로는 T* 포인터(pointer typedef 타입)를 넘긴다.
  • rebind 중첩 템플릿을 꼭 제공하자.