C++編【標準ライブラリ】 第32章 アロケータ

この章の概要

この章の概要です。

関連する話題が、以下のページにあります。

アロケータ

アロケータとは、動的なメモリの割り当てと解放を抽象化する特別なオブジェクトのことです。 標準ライブラリにおいては、STLコンテナが要素を格納する場所を確保するために、アロケータを使用しています。 例えば、vector は次のように定義されています。

namespace std {
	template <typename T, typename Allocator = allocator<T> >
	class vector {
	};
}

テンプレートパラメータ Allocator がアロケータですが、 特に気にしていなければ、std::allocator というデフォルトのアロケータが使用されます。 デフォルトのアロケータについては、後の項で取り上げます

C++ においては、動的なメモリの割り当てには new演算子を、解放には delete演算子を使うことが標準的な方法ですが、 場合によっては他の方法が必要になることがあります。 そのようなときには、目的に合ったアロケータクラスを定義して、上記のテンプレートパラメータに指定すれば、 STLコンテナが、メモリの割り当てや解放が必要になったとき、そのアロケータが持つ機能が呼び出されるようになります。

独自にアロケータを定義する理由は幾つか考えられますが、 よくあるのは、デフォルトの new/delete が遅いので、より高速になるように最適化した、メモリ割り当て機構を作るというものです。 例えば、あらかじめ確保しておいた巨大なメモリ領域(メモリプール)を切り出して使うようにするなどです。 いずれにせよ、特別なメモリ割り当て機構が必要になる状況では、アロケータの仕組みが活用できます。

デフォルトのアロケータ

まず、デフォルトのアロケータ (std::allocator) が、どのように定義されているかを確認しておきましょう。 これを理解すれば、同じようにメンバを用意して、その実装をカスタマイズすれば、独自のアロケータになります。

C++11 では、メンバに変更があります。

以下が、デフォルトのアロケータの定義例です。

namespace std {
	template <typename T>
	class allocator {
	public:
		typedef size_t    size_type;
		typedef ptrdiff_t difference_type;
		typedef T*        pointer;
		typedef const T*  const_pointer;
		typedef T&        reference;
		typedef const T&  const_reference;
		typedef T         value_type;
		
		template <typename U>
		struct rebind {
			typedef allocator<U> other;
		};
		
		allocator() throw() {}
		allocator(const allocater&) throw() {}
		template <typename U> allocator(const allocator<U>&) throw() {}
		
		~allocator() throw() {}
		
		pointer allocate(size_type num, allocator<void>::const_pointer hint = 0)
		{
			return static_cast<pointer>(::operator new(num * sizeof(T)));
		}

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

		void construct(pointer p, const T& value)
		{
			new((void*)p) T(value);
		}

		void destroy(pointer p)
		{
			((T*)p)->~T();
		}
		
		pointer address(reference value) const { return &value; }
		const_pointer address(const_reference value) const { return &value; }
		
		size_type max_size() const throw()
		{
			return numeric_limits<size_t>::max() / sizeof(T);
		}
	};
	
	template <>
	class allocator<void> {
	public:
		typedef void*        pointer;
		typedef const void*  const_pointer;
		typedef void         value_type;
	
		template <typename U>
		struct rebind {
			typedef allocator<U> other;
		};
	};
	
	template <typename T1, typename T2>
	bool operator==(const allocator<T1>&, const allocator<T2>&) throw()
	{
		return true;
	}
	
	template <typename T1, typename T2>
	bool operator!=(const allocator<T1>&, const allocator<T2>&) throw()
	{
		return false;
	}
}

テンプレートパラメータ T は、このアロケータが扱う対象の型です。 また、void型で特殊化(【言語解説】第23章)されたバージョンも定義されています。

コンストラクタとデストラクタは、特に何も行っていません。

allocateメンバ関数は、メモリ領域の割り当てを行います。 オブジェクトの生成はここでは行わないので、operator new(【言語解説】第36章)を呼び出しています。 第1引数の num は、必要なオブジェクトの個数であることに注意して下さい。 実際に割り当てられるサイズ(バイト数)は、「sizeof(T) * num」です。
第2引数は、メモリ割り当てルーチンに与えるヒントです。 実装方法によっては有効に活用できることもありますが、必要なければ無視しておけます。
戻り値は、割り当てられたメモリ領域のアドレスを返します。 なお、メモリ割り当てに失敗した場合は、std::bad_alloc例外が送出されます

あるクラス(例えば、MyClass)のオブジェクトを確保するとして、allocateメンバ関数が行っていることは、 領域を作ることだけであることに注意して下さい。 これだけでは、オブジェクトのインスタンス化は行われていません。 インスタンス化を行うのは、constructメンバ関数の役目です。

オブジェクトの解体は destroyメンバ関数で、 割り当てられたメモリ領域の解放は、deallocateメンバ関数で行われます。

addressメンバ関数は、引数で渡された参照型の値を、ポインタ型に変換して返します。

max_sizeメンバ関数は、割り当て可能なオブジェクトの最大数を返します。

最後に、rebind構造体テンプレートと、そのメンバにある other という typedef ですが、 これは、このアロケータが本来扱う型 (テンプレートパラメータ T)以外の型を確保しなければならないときに利用されます。
例えば、std::list<int> は、int型の要素を扱うので、一見すると int型を割り当てるアロケータが使えそうですが、 実際には、リスト構造を実装するにあたって、前後の要素を指し示すためのポインタ変数もセットで管理しなければなりません(アルゴリズムとデータ構造編【データ構造】第4章)。 そのため、要素が追加されたときに確保する型は、int型ではなく struct Node {int v; Node* next; Node* prev;} のような型になります。 この Node型のためのアロケータを作り出すために、rebind の仕組みがあります。 恐らく、std::list には、次のような定義が含まれており、必要なときにはこのアロケータが使用されます。

typedef typename Allocator::rebind<Node>::other NodeAllocator;
NodeAllocator  node_allocator;


ここで、STLコンテナがアロケータをどう使うのか、少し例を挙げておきます。 例えば、vector のコンストラクタには、初期サイズを指定するタイプのものがありますが、 この実装は、次のような感じになります。

template <typename T, typename Allocator = allocator<T> >
class vector {
public:
	typedef std::size_t  size_type;
	
	T*         elems;
	Allocator  allocator;
	
	vector(size_type size, const T& val, const Allocator& a) : allocator(a)
	{
		// 必要なメモリ領域を確保する
		elems = allocator.allocate(size);
		
		// オブジェクトを生成する
		for (size_type i = 0; i < size; ++i) {
			allocator.construct(&elems[i], val);
		}
	}
};

メモリ領域の確保と、オブジェクトの生成を個別に、かつアロケータを利用して行われていることが分かると思います。

第5章で説明したように、vector には「サイズ」と「容量」の概念がありますが、 allocator の allocateメンバ関数を使って確保されたメモリ領域が「容量」で、 allocator の constructメンバ関数を使って確保されたオブジェクトの個数が「サイズ」です。

C++11 (デフォルトのアロケータ)

C++11

C++11 になって、デフォルトのアロケータは、メンバの一部に変更が加わっています。 ただし、意味としては変化はありませんし、追加や削除もありません。

namespace std {
	template <typename T>
	class allocator {
	public:
		typedef size_t    size_type;
		typedef ptrdiff_t difference_type;
		typedef T*        pointer;
		typedef const T*  const_pointer;
		typedef T&        reference;
		typedef const T&  const_reference;
		typedef T         value_type;
		
		template <typename U>
		struct rebind {
			typedef allocator<U> other;
		};
		
		allocator() noexcept {}
		allocator(const allocater&) noexcept {}
		template <typename U> allocator(const allocator<U>&) noexcept {}
		
		~allocator() noexcept {}
		
		pointer allocate(size_type num, allocator<void>::const_pointer hint = 0)
		{
			return static_cast<pointer>(::operator new(num * sizeof(T)));
		}

		void deallocate(pointer p, size_type num)
		{
			::operator delete(p);
		}
		
		template <typename T, typename... Args>
		void construct(T* p, Args&&... args)
		{
			::new(p) T(std::forward<Args>(args)...);
		}
		
		template <typename T>
		void destroy(T* p)
		{
			p->~T();
		}
		
		pointer address(reference value) const { return &value; }
		const_pointer address(const_reference value) const { return &value; }
		
		size_type max_size() const noexcept
		{
			return numeric_limits<size_t>::max() / sizeof(T);
		}
	};
	
	template <>
	class allocator<void> {
	public:
		typedef void*        pointer;
		typedef const void*  const_pointer;
		typedef void         value_type;
	
		template <typename U>
		struct rebind {
			typedef allocator<U> other;
		};
	};
	
	template <typename T1, typename T2>
	bool operator==(const allocator<T1>&, const allocator<T2>&)
	{
		return true;
	}
	
	template <typename T1, typename T2>
	bool operator!=(const allocator<T1>&, const allocator<T2>&)
	{
		return false;
	}
}

VisualC++ 2013/2015/2017、clang 3.7 はこの変更に対応しています。

アロケータを定義する

デフォルトのアロケータの作りを踏まえて、独自のアロケータを定義できます。
大半のメンバは、デフォルトのアロケータのままで構いません。 変更が必要なのは、allocateメンバ関数、deallocateメンバ関数、max_sizeメンバ関数ぐらいです。

試しに、確保済みになっているメモリ領域のサイズを管理するアロケータを作ってみます。

#include <iostream>
#include <limits>
#include <vector>

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

	template <typename U>
	struct rebind {
		typedef MyAllocator<U> other;
	};

	MyAllocator() throw() {}
	MyAllocator(const MyAllocator& rhs) throw() {}
	template <typename U> MyAllocator(const MyAllocator<U>& rhs) throw() {}

	~MyAllocator() throw() {}

	pointer allocate(size_type num, std::allocator<void>::const_pointer hint = 0)
	{
		const std::size_t size = num * sizeof(T);
		pointer const p = static_cast<pointer>(::operator new(size));

		msTotalSize += size;
		return p;
	}

	void deallocate(pointer p, size_type num)
	{
		const std::size_t size = num * sizeof(T);
		msTotalSize -= size;

		::operator delete(p);
	}

	void construct(pointer p, const T& value)
	{
		new((void*)p) T(value);
	}

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

	pointer address(reference value) const { return &value; }
	const_pointer address(const_reference value) const { return &value; }

	size_type max_size() const throw()
	{
		return std::numeric_limits<size_t>::max() / sizeof(T);
	}

	size_type get_total_size() const
	{
		return msTotalSize;
	}

private:
	static size_type  msTotalSize;
};

template <typename T>
typename MyAllocator<T>::size_type MyAllocator<T>::msTotalSize = 0;


template <>
class MyAllocator<void> {
public:
	typedef void*        pointer;
	typedef const void*  const_pointer;
	typedef void         value_type;

	template <typename U>
	struct rebind {
		typedef MyAllocator<U> other;
	};
};

template <typename T1, typename T2>
bool operator==(const MyAllocator<T1>&, const MyAllocator<T2>&) throw()
{
	return true;
}

template <typename T1, typename T2>
bool operator!=(const MyAllocator<T1>&, const MyAllocator<T2>&) throw()
{
	return false;
}


int main()
{
	typedef MyAllocator<int> IntAllocator;
	typedef std::vector<int, IntAllocator> IntAllocatorVector;

	IntAllocator myAllocator;

	// 「サイズ」10 で初期化
	IntAllocatorVector v(10, 0, myAllocator);
	std::cout << myAllocator.get_total_size() << std::endl;

	// 100個の要素を追加
	for (int i = 0; i < 100; ++i) {
		v.push_back(0);
	}
	std::cout << myAllocator.get_total_size() << std::endl;

	// 要素をクリア
	// 「サイズ」は 0 になるが、「容量」は変わらない。
	v.clear();
	std::cout << myAllocator.get_total_size() << std::endl;

	// 「容量」も 0 に切りつめる
	IntAllocatorVector().swap(v);
	std::cout << myAllocator.get_total_size() << std::endl;
}

実行結果:

40
652
652
0

ほとんどの部分が、デフォルトの allocator をコピーしたものになっています。 変わっているのは、クラス名と、allocateメンバ関数と deallocateメンバ関数で、 あとは管理のための静的メンバ変数を追加したぐらいです。

allocateメンバ関数の第2引数の型については、std::allocator<void>::const_pointer のままにしていますが、 ここを MyAllocator<void>const_pointer にすると、clang 3.7 ではエラーになります。 そもそも、絶対に const void* 型なので、直接「const void*」と書いてしまっても問題は無いです。


なお、アロケータオブジェクトは状態を持つことができない点に注意して下さい。 つまり、静的でないメンバ変数を持つことはできません
アロケータがメンバ変数を持てない理由は、同じ型のオブジェクトのために作られるアロケータオブジェクトは、 互いを等価なものであるとみなす必要があるためです。 例えば、MyAllocator1 を使う std::list と、MyAllocator2 を使う std::list があるとき、 前者の list の要素を後者の list へつなぎ変えたら(ない継ぎ)、 確保したときに使ったアロケータでは無い方のアロケータを使って解放することになってしまいます。 恐らく、これでは想定した結果にならないでしょう。

この問題を解決するためには、同じ型を扱うアロケータは、常に同じことをする必要があります。 そのため、少なくとも、時と場合によって動作を変更してしまうようなメンバを持つことはできません。

C++11 (アロケータを定義する)

C++11

C++11 では、独自のアロケータを定義する際に必要なメンバが削減されており、以下の定義だけで良くなりました。

template <typename T>
class MyAllocator {
public:
	// 確保する型
	using value_type = T;
	
	// デフォルトコンストラクタ、コピーコンストラクタ、ムーブコンストラクタ
	MyAllocator();
	MyAllocator(const MyAllocator&);
	MyAllocator(MyAllocator&&);
	
	// 別のテンプレート引数から生成するためのコンストラクタ
	template <typename U> MyAllocator(const MyAllocator<U>&);
	
	// メモリ領域を確保
	T* allocate(std::size_t n);
	
	// メモリ領域を解放
	void deallocate(T* p, std::size_t n);
};

template <typename T1, typename T2>
bool operator==(const MyAllocator<T1>&, const MyAllocator<T2>&)
{
	return true;
}

template <typename T1, typename T2>
bool operator!=(const MyAllocator<T1>&, const MyAllocator<T2>&)
{
	return false;
}

これは、新たに std::allocator_traits という構造体が導入されたためです。 従来のアロケータクラスで定義されていた大量の typedef などは、テンプレートパラメータ T されあれば定義できるものなので、 std::allocator_traits の側で自動的に定義されるようになっています。

アロケータを定義する」のところで取り上げたサンプルプログラムを書き換えると、次のようになります。

#include <iostream>
#include <vector>

template <typename T>
class MyAllocator {
public:
	using value_type = T;

	MyAllocator() {}
	MyAllocator(const MyAllocator&) {}
	MyAllocator(MyAllocator&&) {}
	template <typename U> MyAllocator(const MyAllocator<U>&) {}


	T* allocate(std::size_t num)
	{
		const std::size_t size = num * sizeof(T);
		T* const p = static_cast<T*>(::operator new(size));

		msTotalSize += size;
		return p;
	}

	void deallocate(T* p, std::size_t num)
	{
		const std::size_t size = num * sizeof(T);
		msTotalSize -= size;

		::operator delete(p);
	}

	std::size_t get_total_size() const
	{
		return msTotalSize;
	}

private:
	static std::size_t  msTotalSize;
};

template <typename T>
std::size_t MyAllocator<T>::msTotalSize = 0;


template <typename T1, typename T2>
bool operator==(const MyAllocator<T1>&, const MyAllocator<T2>&)
{
	return true;
}

template <typename T1, typename T2>
bool operator!=(const MyAllocator<T1>&, const MyAllocator<T2>&)
{
	return false;
}


int main()
{
	using IntAllocator = MyAllocator<int>;
	using IntAllocatorVector = std::vector<int, IntAllocator>;

	IntAllocator myAllocator;

	// 「サイズ」10 で初期化
	IntAllocatorVector v(10, 0, myAllocator);
	std::cout << myAllocator.get_total_size() << std::endl;

	// 100個の要素を追加
	for (int i = 0; i < 100; ++i) {
		v.push_back(0);
	}
	std::cout << myAllocator.get_total_size() << std::endl;

	// 要素をクリア
	// 「サイズ」は 0 になるが、「容量」は変わらない。
	v.clear();
	std::cout << myAllocator.get_total_size() << std::endl;

	// 「容量」も 0 に切りつめる
	v.shrink_to_fit();
	std::cout << myAllocator.get_total_size() << std::endl;
}

実行結果:

40
652
652
0

VisualC++ 2013/2015/2017、clang 3.7 のいずれでも、この対応が行われています。


練習問題

問題@ std::vector のコンストラクタの実装例を挙げました。これを踏まえると、デストラクタはどうなっていると考えられますか?
アロケータと関係の無いことについては気にしなくて良いです。

問題A std::list で独自のアロケータを使い、rebind のメカニズムが機能していることを確認して下さい。


解答ページはこちら

参考リンク

更新履歴

'2017/3/25 VisualC++ 2017 に対応。

'2017/2/25 新規作成。



前の章へ

次の章へ

C++編のトップページへ

Programming Place Plus のトップページへ