カスタムアロケータとfinal

先日カスタムアロケータを使ったときに気づいたことの備忘録です。

## アロケータを指定できるテンプレートクラス

STLコンテナなどはテンプレート引数でカスタムアロケータを指定できますが、
先日自分でもそのようなクラスを作っていました。

```c++
#include <memory>
#include <type_traits>
// 任意の型のインスタンス一つをplacement new/deleteしやすくするためのクラス
template<typename T, typename A = std::allocator<T>>
struct typed_storage
{
	typed_storage(const A& al = {})
		:al{ al }
	{}

	// 自己責任で構築
	template<typename ...Arg>
	void construct(Arg&&...arg)
	{
		std::allocator_traits<A>::construct(al, getAddress(), std::forward<Arg>(arg)...);
	}

	// 自己責任で破棄
	void destroy()
	{
		std::allocator_traits<A>::destroy(al, getAddress());
	}

	// 関係ないけどconstありなし以外同じ記述の関数を1つの記述でカバーできないものか・・・
	T& operator()()
	{
		return *getAddress();
	}

	const T& operator()() const
	{
		return *getAddress();
	}

private:
	A al;  // アロケータ
	std::aligned_storage_t<sizeof(T), alignof(T)> storage; // ストレージ

	T* getAddress() {
		return reinterpret_cast<T*>(&storage);
	}
	const T* getAddress() const {
		return reinterpret_cast<T*>(&storage);
	}
};

int main() {
	// ほんとはstringなどを指定する
	typed_storage<int> intStorage;
	intStorage.construct();
	intStorage() = 42;
	intStorage.destroy();
}
```

このクラス自体はなんてことはないのですが、いざ作ってみると気になる点が。
アロケータをメンバに保持しなくてはいけないので、T型のストレージに過ぎないクラスなのにsizeofの結果がTより大きくなってしまいます。
それもstd::allocatorのような**空のクラス**であってもです（！）
c/c++ではvoid以外のどんな型でもsizeofの結果は1以上と決められています。でないと上記の場合でもアロケータのアドレスとストレージのアドレスが
重なってしまいかねないからです。そういうことするならunionです。

## カスタムアロケータを圧縮する

そこで、無駄な領域を取らないように**Empty Base Optimization**と呼ばれる最適化を利用して以下のように作り変えてみました。

```c++
#include <memory>
#include <type_traits>
// 任意の型のインスタンス一つをplacement new/deleteしやすくするためのクラス
template<typename T, typename A = std::allocator<T>>
struct typed_storage
{
	typed_storage(const A& al = {})
		:data{ al }
	{}

	template<typename ...Arg>
	void construct(Arg&&...arg)
	{
		std::allocator_traits<A>::construct(data.getAllocator(), getAddress(), std::forward<Arg>(arg)...);
	}

	void destroy()
	{
		std::allocator_traits<A>::destroy(data.getAllocator(), getAddress());
	}

	T& operator()()
	{
		return *getAddress();
	}

	const T& operator()() const
	{
		return *getAddress();
	}

private:
	// アロケータがEBO可能かどうか判定して保持の仕方を変える
	template<typename Al, bool = std::is_empty_v<Al> && !std::is_final_v<Al>>
	struct allocator
	{
		Al isntance;
		Al& getAllocator()
		{
			return isntance;
		}
	};

	template<typename Al>
	struct allocator<Al, true> : Al
	{
		Al& getAllocator()
		{
			return *this;
		}
	};

	// データ本体（ストレージ＋アロケータ）
	struct Data : allocator<A>
	{
		std::aligned_storage_t<sizeof(T), alignof(T)> storage;
		Data(const A& al)
			:allocator<A>{al}
		{}
	} data;
	T* getAddress() {
		return reinterpret_cast<T*>(&data.storage);
	}
	const T* getAddress() const {
		return reinterpret_cast<T*>(&data.storage);
	}
};

int main() {
	// ほんとはstringなどを指定する
	typed_storage<int> intStorage;
	static_assert(sizeof(int) == sizeof(typed_storage<int>)); // OK
	intStorage.construct();
	intStorage() = 42;
	intStorage.destroy();
}
```

ポイントとなるのは

```c++
std::is_empty_v<T> && !std::is_final_v<T>
```

この部分でアロケータが**空クラスでかつfinal指定されていない**ことを判定し、それによってallocatorクラスを
「EBOの効く継承で保持するもの」と「ただのコンポジションのもの」に切り替えています。
クラスを切り替えてもどちらもdata.getAllocator()でアロケータを取得できるので使う側ではどちらに振り分けられたか
気にする必要がありません。
この仕組みによって無駄なアロケータ領域を節約することが出来ました。
ちなみにSTLコンテナはどうなってるのか気になったのでMSVCの実装をのぞいてみたところ上記と全く同じことをしていました。
そのため例えアロケータが空クラスでEBOが効くとしても几帳面にfinal指定しているとSTLコンテナ一つにつきポインタ一個分くらい余分に無駄にしてしまいます。

## まとめ

アロケータを指定できるコンテナを作ることはそんなにないと思うのでEBOを利用したアロケータの保持実装については頭の片隅にでも置いとけばいいと思います。
カスタムアロケータならもう少し作る機会も多いと思います、その時は空クラスにできそうなら無駄にfinal指定をしないで節約するようにしましょう。
ただ、c++17以降が使えるならよほどでもない限りpolymorphic_allocatorを使う方がいろいろ捗ると思います。