8. STL Custom Allocator

std의 Container들에는 Allocator(할당자)가 존재한다.
이 Allocator들은 Container들의 메모리를 관리한다.

기본적으로 표준의 Allocator를 사용하지만, 사용자가 직접 만들어준다면, 자신이 만든 Allocator를 사용할 수 있다.

 

일단 흔히 사용하고 있는 vector에 있는 오버로딩된 함수를 보자

	std::vector<int> temp;

이 vector의 템플릿을 한번 보게 되면,

template <class _Ty, class _Alloc = allocator<_Ty>>
class vector { // varying size array of values
private:
    template <class>
    friend class _Vb_val;
    friend _Tidy_guard<vector>;

    using _Alty        = _Rebind_alloc_t<_Alloc, _Ty>;
    using _Alty_traits = allocator_traits<_Alty>;

이런식으로 템플릿 변수형을 하나가 아닌 두개를 넣을 수 있게 돼있다.
기본적으로 사용할 경우

std::vector<int,std::allocator<int>> temp;

이렇게 사용이 된다.

 

이 안에 있는 allocator를 직접 만들어 사용해보자.

 

Custom Allocator

template<typename T>
class Allocator
{
public:
	// typedefs
	typedef T value_type;
	typedef value_type* pointer;
	typedef const value_type* const_pointer;
	typedef value_type& reference;
	typedef const value_type const_reference;
	typedef std::size_t size_type;
	typedef std::ptrdiff_t difference_type;

public:
	// convert an allocator<T> to allocator<U>
	template<typename U>
	struct Rebind
	{
		typedef Allocator<U> other;
	};

public:
	inline explicit Allocator() {}
	inline ~Allocator() {}
	inline explicit Allocator(Allocator const&) {}
	template<typename U>
	inline explicit Allocator(Allocator<U> const&) {}

	// address
	inline pointer address(reference r) { return &r; }
	inline const_pointer address(const_reference r) { return &r; }
	   
	// memory allocation
	inline pointer allocate(size_type cnt, typename std::allocator<void>::const_pointer = 0)
	{
		return reinterpret_cast<pointer>(::operator new(cnt* sizeof(T)));
	}

	inline void deallocate(pointer p, size_type) 
	{
		::operator delete(p);
	}

	// size
	inline size_type maxSize() const
	{
		return INT_MAX / sizeof(T);
	}

	// construction/destruction
	inline void construct(pointer p, const T& t)
	{
		new(p)T(t);
	}

	inline void destroy(pointer p) { p->~T(); }

	inline bool operator==(Allocator const&) 
	{
		return true; 
	}
	inline bool operator!=(Allocator const& a) 
	{
		 return !operator==(a);
	}
};

펼쳐보면 직접 만든 Allocator의 소스가 있다. 이제 하나씩 살펴보자

 

public:
	// typedefs
	typedef T value_type;
	typedef value_type* pointer;
	typedef const value_type* const_pointer;
	typedef value_type& reference;
	typedef const value_type const_reference;
	typedef std::size_t size_type;
	typedef std::ptrdiff_t difference_type;

위에 정의된 타입들은 무조건 있어야 한다. (정의한 타입 이름도 같아야 한다. 난 몰랐다 이거때문에 한시간을 날렸다..ㅠㅠ 허ㅏ헣) 없으면 에러난다.

public:
	// convert an allocator<T> to allocator<U>
	template<typename U>
	struct Rebind
	{
		typedef Allocator<U> other;
	};

이 Rebind도 있어야 한다.
Rebind는 내부에서 명시된 데이터 T를 다른 타입으로 만들 필요가 있어서 넣어줘야 한다. vector나 list의 경우에는 만들어도 딱히 사용하지 않지만, 트리같은 구조에서 사용하게 된다. (여기 마지막 Rebind 참고)

7. CRTP, Static Plymophism and Rebind

public:
	inline explicit Allocator() {}
	inline ~Allocator() {}
	inline explicit Allocator(Allocator const&) {}
	template<typename U>
	inline explicit Allocator(Allocator<U> const&) {}

Allocator가 내부에서 리바인드 된 경우에 원래 Allocator를 받는 생성자를 정의하게 돼있다.
지금 만들어 사용하는 경우에는 템플릿 U를 사용하지 않아서 따로 구현하진 않았다. 하지만, U를 사용 한다면 구현이 필요하다.

 

	// address
	inline pointer address(reference r) { return &r; }
	inline const_pointer address(const_reference r) { return &r; }

이렇게 정의한 이유는 그냥 사용해 버리면 내부에서 코드 호환이 되지 않는다. 그래서 컨테이너의 내부에선 항상 Allocator의 Address 이런식으로 사용하도록 구현돼있다.

 

// memory allocation
inline pointer allocate(size_type cnt, typename std::allocator<void>::const_pointer = 0)
{
	return reinterpret_cast<pointer>(::operator new(cnt* sizeof(T)));
}

inline void deallocate(pointer p, size_type) 
{
	::operator delete(p);
}

메모리를 할당하는 함수다.
void의 const_pointer를 파라미터를 받도록 구현돼있습니다. 그리고 전역의 operator new 를 호출했다. 기존과 차이점은 없다.

그리고 delete다... 간단하다.

 

	// size
	inline size_type maxSize() const
	{
		return INT_MAX / sizeof(T);
	}

	// construction/destruction
	inline void construct(pointer p, const T& t)
	{
		new(p)T(t);
	}

	inline void destroy(pointer p) { p->~T(); }

	inline bool operator==(Allocator const&) 
	{
		return true; 
	}
	inline bool operator!=(Allocator const& a) 
	{
		 return !operator==(a);
	}

maxSize는 그냥 할당할 수 있는 최대 크기를 반환한다.
그리고 construct는 메모리 할당을 한 다음에 emplace new 가 호출될수 있기 때문에 메모리를 할당 후 생성 할때 cosntruct를 통해 하도록 돼있다.
그리고 != 를 operator를 하기 위해선 operator == 를 정의 해주어야 한다.

 

void main()
{
	std::ostream_iterator<int> out(std::cout, ",");

	std::list<int, Allocator<int>> list1 = { 1, 3, 5, 7, 9 };
	std::copy(list1.begin(), list1.end(), out);
	std::cout << std::endl;

	std::list<int, Allocator<int>> list2 = { 10, 30, 50, 70, 90 };

	auto it = list1.begin();
	std::advance(it, 2);

	list1.splice(it, list2);
	std::copy(list1.begin(), list1.end(), out);
	std::cout << std::endl;
	std::copy(list2.begin(), list2.end(), out);
	std::cout << std::endl;
}

마지막 main이다.
간단 하다. 하지만 중간에 advence는 it이터레이터에 2를 더한것 그러니까 list1[0]에서 list1[2]로 이동했다.
splice는 이터레이터에 리스트를 삽입하는 것으로

{1, 3, 10, 30, 50, 70, 90, 5, 7, 9} 으로 만들어 준다.

 

결과값

1,3,5,7,9,
1,3,10,30,50,70,90,5,7,9,