C++17 optionalの実装について

C++17で、optionalが標準ライブラリに入ることが決定した。

そして、C++17 optionalはconstexprに対応している。

以前からその実装について気になっていたので調べたついでに少しまとめる。

optionalとは

無効値を取ることのできる型である。

C++17 optionalはBoost.Optionalの実装を元に設計された。

Boost.Optionalに関しては以下の記事が詳しい。

d.hatena.ne.jp

C++03 Boost.Optionalの実装

C++03時代のBoost.Optionalの実装についても触れておく。

C++03 Boost.Optionalの実装は単純だ。

予めoptionalオブジェクト内にデータを格納するストレージを確保しておき、
適切なタイミングでplacement newをして、初期化する。

また、オブジェクトを破棄する際には、必要があれば明示的デストラクタ呼び出しを行う。

ストレージの確保には、(C++11以降でいうところの)std::aligned_storageのようなものを用いる。

つまり、optionalの内部で領域の動的確保は行われない。

下記のコードはBoost.Optionalの実装のイメージだ(故に正確ではない)。

template <typename T>
class optional {
    //  storage
    typename std::aligned_storage<sizeof(T), alignof(T)>::type storage_;
    bool init_;
    
    //  pointer to storage
    T* ptr() {
        return static_cast<T*>(static_cast<void*>(&storage_));
    }
    
public:
    // default constructor
    optional() : init_(false) {}
    
    // value constructor
    optional(const T& val) : init_(true) {
        //  placement new
        new (&storage_) T(val);
    }
    
    //  destructor
    ~optional() {
        if (init_) {
            // explicit destructor call
            ptr()->~T();
        }
    }
};

見て分かる通り、この実装のoptionalクラスはtrivialデストラクタを持たない。

更には引数付きコンストラクタはconstexprコンストラクタの条件を満たさない。

なので、このままではconstexpr対応の条件であるリテラル型クラスの条件を満たさない。

C++17 optionalはどのような実装により、constexpr対応を果たしたのだろうか。

その前に

上のコードでは、Tの型に関わらずoptional<T>型はデストラクタで明示的デストラクタ呼び出しを行っているが、
実際には、Tがtrivialデストラクタをもつ場合は明示的デストラクタ呼び出しを省略できる。

そのため、Tがtrivialデストラクタを持つときには、optional型もまたtrivially destructibleとなれる。

実装について

さて、ようやくC++17 optionalの実装を確認する。

constexpr対応のoptionalの実装は以下のリポジトリのものを参考にした。

github.com

だが、実際のソースコードは一息に読むには長いので、部分部分に分解して見ていく。

まずは、optional<T>型の定義を確認する。

定義は上記のリポジトリ、optional.hppファイルの350行目付近である。

// 350行目付近
template <class T>
class optional : private OptionalBase<T>
{
   ...
};

optional<T>型はOptionalBase<T>型を継承している。

OptionalBase<T>型はそのすぐ上で定義されている。

// 341行目付近
template <class T>
using OptionalBase = typename std::conditional<
    is_trivially_destructible<T>::value,
    constexpr_optional_base<typename std::remove_const<T>::type>,
    optional_base<typename std::remove_const<T>::type>
>::type;

std::conditional<B, X, Y>::typeは、B == trueの時 X型になり、B == falseの時 Y型となる。

ようは、条件分岐のようなものだ。

この場合の分岐条件は、

is_trivially_destructible<T>::value

つまり、Tがtrivialデストラクタを持つかどうかだ。

Tがtrivialデストラクタを持つ時、OptionalBase<T>は、constexpr_optional_base<T>となり、
Tが非trivialデストラクタを持つ時、OptionalBase<T>は、optional_base<T>となる。

双方の定義を確認する。

// 296行目付近
template <class T>
struct optional_base
{
    bool init_;
    storage_t<T> storage_;

    ...

    ~optional_base() { if (init_) storage_.value_.T::~T(); }
};

// 319行目付近
template <class T>
struct constexpr_optional_base
{
    bool init_;
    constexpr_storage_t<T> storage_;

    ...

    ~constexpr_optional_base() = default;
};

「...」で省略した部分はどちらのクラスもほぼ同じであった。

違いは2点。

1つ目は、storage_ メンバ変数の型、

2つ目は、デストラクタでのメンバの明示的デストラクタ呼び出しの有無だ。

constexpr_optional_baseは、Tがtrivialデストラクタを持つため、明示的デストラクタ呼び出しを省略しているのだろうと予想できる。

では、storage_t と constexpr_storage_t の定義を確認する。

// 266行目付近
template <class T>
union storage_t
{
  unsigned char dummy_;
  T value_;

  ...

  ~storage_t(){}
};

// 281行目付近
template <class T>
union constexpr_storage_t
{
    unsigned char dummy_;
    T value_;

    ...

    ~constexpr_storage_t() = default;
};

このoptionalは、ストレージにstd::aligned_storageのような型を使わず、共用体を使って実現しているようだ。

storage_t と constexpr_storage_t の定義の違いは、デストラクタの定義のみである。

ではこの違いは何故必要なのか。

これには、C++11の「共用体の制限解除」が関係している。

C++11以降では非trivialデストラクタを持つオブジェクトも共用体のメンバにすることが可能になった。

しかし、その時その共用体のデストラクタは暗黙的にdeleteされる。

そのため、非trivialデストラクタを持つT型のメンバ value_ を持つstorage_tには空のデストラクタ定義が必要になる。

さらに、共用体のコンストラクタの初期化子を使って value_ を初期化すれば、T型のコンストラクタが呼び出されるため、
optional<T>のコンストラクタ内での placement new の必要がなくなる。

以上をもって、Tがリテラル型である場合に、constexpr_storage_t<T>、constexpr_optional_base<T>、optional<T>の全てがリテラル型の条件を満たし、コンパイル時のオブジェクト構築が可能となる。

#include <type_traits>
#include <string>
#include <cassert>

template <typename T>
union storage_t {
	char dummy_;
	T value_;

	template <typename... Args>
	constexpr storage_t(Args&&... args) : value_(args...) {}

	~storage_t() {}
};

template <typename T>
union constexpr_storage_t {
	char dummy_;
	T value_;

	template <typename... Args>
	constexpr constexpr_storage_t(Args&&... args) : value_(args...) {}

	~constexpr_storage_t() =default;
};

template <typename T>
struct optional_base {
	bool init_;
	storage_t<T> storage_;
    
	template <typename... Args>
	constexpr optional_base(Args&&... args)
		: init_(true), storage_(args...) {}

	~optional_base() { if (init_) storage_.value_.~T(); }
};

template <typename T>
struct constexpr_optional_base {
	bool init_;
	constexpr_storage_t<T> storage_;

	template <typename... Args>
	constexpr constexpr_optional_base(Args&&... args)
		: init_(true), storage_(args...) {}

	~constexpr_optional_base() =default;
};

template <typename T>
using OptionalBase = std::conditional_t<
	std::is_trivially_destructible<T>::value,
	constexpr_optional_base<T>,
	optional_base<T>
>;

template <typename T>
class optional : OptionalBase<T> {
public:
	constexpr optional(const T& value) : OptionalBase<T>(value) {}

	constexpr const T& operator*() const {
		return OptionalBase<T>::storage_.value_;
	}
};

int main() {
    // constexpr
    constexpr optional<int> a(42);
    static_assert(*a == 42);
    
    // 非constexpr
    /*constexpr*/ optional<std::string> b("nyan");
    assert(*b == "nyan");
}

コンマ

ふと不思議に思ったものがあった。
線形代数ライブラリEigenの行列、ベクトルの初期化方法だ。

Eigen::Vector3d v;
v << 1.0, 2.0, 3.0;
v;  //  (1, 2, 3)

なんだか妙なことをしている。
どのようなしくみになっているのかを確かめるために実装を調べた。

どうやら コンマ演算子オーバーロードしているようだ。
はじめに <<演算子 で CommaInitializer なる中間オブジェクトを生成し、CommaInitializer の コンマ演算子オーバーロード で値を格納しているらしい。

恥ずかしながら今まで コンマ演算子オーバーロード可能であることを知らなかった。
そういえば、オーバーロード可能演算子に含まれている。

まあせっかくなので少し遊んでみたい。

#include <iostream>
using namespace std;

namespace hoge {
    template <typename Value>
    ostream& operator,(ostream& stream, Value value) {
        return stream << ',' << value;
    }
}

int main() {
    cout << 1,2,3,4,5;   // 1
    cout << endl;
    using namespace hoge;
    cout << 1,2,3,4,5;   // 1,2,3,4,5
    cout << endl;
}

出力

1
1,2,3,4,5

[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

さて、この記事を書いている途中、コンマ演算子オーバーロード用いた Boost.Assign なるものがあることを教えていただいた。

#include <boost/assign.hpp>

int main() {
    using namespace boost::assign;
    std::vector<int> v;

    v += 1,2,3,4,5; // [1,2,3,4,5]
}

[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ
内部は、Eigen のそれと似たようなものなのだろう。
Boost.Assign ではこれ以外にも演算子オーバーロードされているようだ。

このコードにはバグがある

今日はこのようなツイートを見た。


#include <stdio.h>

class base_class {
public:
    base_class() { x = 0; y = 0; }

public:
    int x;
    int y;
};

class derived_class : public base_class {
public:
    derived_class() { z = 0; }

public:
    int z;
};

void calc_class_members(base_class *b, int array_size)
{
    for(int i = 0; i < array_size; i++)
    {
        b[i].x = i;
        b[i].y = i;
    }
}

// Calling from external
int update_class_members(
    derived_class * class_array,    // Valid array
    int num_array )
{
    if( class_array == NULL )
        return -1;    // means error

    calc_class_members(class_array, num_array);

    return 0;// success
}

このコードの誤りは base_class と derived_class の大きさの違いによるものであるが、取り敢えず実行してみれば明らかである。

int main()
{
    constexpr int num_array = 5;
    derived_class class_array[num_array];

    update_class_members(class_array, num_array);
    
    for(auto&& a : class_array)
        printf("%d, %d, %d\n", a.x, a.y, a.z);
    
    puts("---");
    
    printf("%p, %p, %p\n", &class_array[0]
                         , &class_array[1]
                         , &class_array[2]);
    
    printf("%p, %p, %p\n", &static_cast<base_class*>(class_array)[0]
                         , &static_cast<base_class*>(class_array)[1]
                         , &static_cast<base_class*>(class_array)[2]);
}

実行結果
http://melpon.org/wandbox/permlink/mVYWFiM7eEieWFeE

0, 0, 1
1, 2, 2
3, 3, 4
4, 0, 0
0, 0, 0
---
0x7ffd2e5e31e0, 0x7ffd2e5e31ec, 0x7ffd2e5e31f8
0x7ffd2e5e31e0, 0x7ffd2e5e31e8, 0x7ffd2e5e31f0

この通り、derived_class は base_class よりも sizeof(int) だけ大きいため、
配列の先頭要素へのポインタ class_array を base_class* へとキャストした後に添字演算を行うとずれた位置にアクセスしてしまう。

問題の答えたるバグはおそらくこれのことで間違いないだろう。

ではこのプログラムが正しい動作をするように書き直したい。

まず思いついたのは calc_class_members を template化 することであるが、
それだけでは元々のプログラムの意図が損なわれてしまう。

そのため、template の型をチェックして、base_class の派生クラスでないものは弾いてしまおう。


だがそれ以前に、このコードは生ポインタを使っていたりととてもモダンなC++とは呼べない。なので、ついでに適当に手直しをしておく。

//#include <stdio.h> // そもそもいらない
#include <array>
#include <vector>

struct base_class {
    int x = 0;
    int y = 0;
};

struct derived_class : base_class {
    int z = 0;
};

template <typename type, typename allocator>
void calc_class_members(std::vector<type, allocator>& b)
{
    static_assert(std::is_base_of<base_class, type>::value, "");

    int i = 0;
    for(type& a : b)
    {
        a.x = i;
        a.y = i;

        i++;
    }
}

template <typename allocator>
void update_class_members(std::vector<derived_class, allocator>& class_array)
{
    // nullptr チェックの必要はない
    
    calc_class_members(class_array);
}


// あるいはこうだろうか
template <typename type, size_t n>
void calc_class_members(std::array<type, n>& b)
{
    static_assert(std::is_base_of<base_class, type>::value, "");

    int i = 0;
    for(type& a : b)
    {
        a.x = i;
        a.y = i;

        i++;
    }
}

template <size_t n>
void update_class_members(std::array<derived_class, n>& class_array)
{
    calc_class_members(class_array);
}
#include <iostream>

int main()
{
    auto class_array1 = std::vector<derived_class>{ 5 };
    auto class_array2 = std::array<derived_class, 5>{};

    update_class_members(class_array1);
    update_class_members(class_array2);

    std::cout << "class_array1" << std::endl;
    for(auto&& a : class_array1)
        std::cout << a.x << ", " << a.y << ", " << a.z << std::endl;

    std::cout << "class_array2" << std::endl;
    for(auto&& a : class_array2)
        std::cout << a.x << ", " << a.y << ", " << a.z << std::endl;
}

実行結果
http://melpon.org/wandbox/permlink/COZ8R4QW2OXFM6u8

class_array1
0, 0, 0
1, 1, 0
2, 2, 0
3, 3, 0
4, 4, 0
class_array2
0, 0, 0
1, 1, 0
2, 2, 0
3, 3, 0
4, 4, 0

お見かけした他の方のコード


なるほど、
こんな手は思いつきもしなかった。

文字列型をキーとしたunordered_map

プログラミングをしている際、文字列型をキーとした連想配列を扱いたい時がある。

そのような時に用いられるのは多くの場合unordered_mapだ。

using Map = unordered_map<string, int>;

Map m = {
	{ "a", 1 },
	{ "b", 2 },
	{ "c", 3 },
};
m["a"]; // 1
m["b"]; // 2

ところで、unordered_map の []演算子 の引数は (const key_type&) あるいは (key_type&&) である。

そして、今 key_type は std::string だ。

そのため、

m["a"];

m.operator[](string{"a"});

と同義だ。

なんでもないアクセスのために std::string のインスタンスが生成されている。そして、std::string のコンストラクタでは "a" という文字列を格納するためのバッファが確保される。バッファの確保は大抵の場合比較的遅い。

なにか良い方法はないか。


さて、boost::string_ref と言うものが存在する。詳細な説明は省略するが、要は文字列を格納したバッファへの ポインタ と 文字数 のみを保持するだけのクラスである。

string_ref は内部でポインタを保持するだけで、一切のバッファ確保を行わない。

つまり、こいつをキーに出来れば上のような問題は起きないのだ。

そして勿論、 string_ref 等のような独自定義の型であっても、==演算子オーバーロード(あるいはコンパレータ)とハッシュ値を求めるハッシャさえ存在すれば、unordered_mapのキーとして使える。

#include <boost/utility/string_ref.hpp>
#include <boost/functional/hash.hpp> // boost::hash_range

using namespace boost;

struct Hasher {
	size_t operator()(string_ref str) const {
		return hash_range(str.cbegin(), str.cend());
	}
};

using Map = unordered_map<string_ref, int, Hasher>;

Map m = {
	{ "a", 1 },
	{ "b", 2 },
	{ "c", 3 },
};
// バッファの確保は起こらない
m["a"]; // 1
m["b"]; // 2

一見これで良さそうだ。

だが、これにもまだ問題がある。

先程も述べたように、string_ref はあくまでバッファへのポインタを保持するクラスである。つまり、文字列の本体はどこかに存在していなくてはならないのだ。

そのため、

int main() {
	Map m;

	{
		string str = "###";
		m[str] = 42;
	}// もはやstrは存在しない

	m["###"]; // ?
}

このようなコードは未定義動作となる。

何故ならば、m["###"]; が実行されるときにはもうバッファの本体たる str は破壊されているからだ。


今必要なのは、キーを登録する際には std::string のようにバッファを確保し、ただアクセスするときには boost::string_ref のようにバッファを確保せず、比較とハッシュ値の算出のみを行う型である。

では、愚直に実装してみる。

#include <boost/optional.hpp>

using namespace boost;

class Key {
	optional<string> str;
	string_ref       ref;

public:
	Key(string_ref s, bool flag = false) {
		if(flag) {
			str = s.to_string();
			ref = *str;
		}
		else {
			ref = s;
		}
	}

	Key(const Key& key)
		: str(key.str), ref(str ? *str : key.ref) {}

	Key(Key&& key)
		: str(std::move(key.str)), ref(str ? *str : key.ref) {}

	bool operator==(const Key& key) const {
		return ref == key.ref;
	}

	string_ref str() const {
		return ref;
	}
};

struct Hasher {
	size_t operator()(const Key& key) const {
		return hash_range(key.str().cbegin(), key.str().cend());
	}
};

boost::optional を用いてバッファの有効/無効を表現した。

また、コンストラクタの第二引数のフラグのon/offによってバッファを確保するかどうかを分岐させている。

実際にキーとして使用するときには以下のようになる。

using Map = unordered_map<Key, int, Hasher>;

Map m = {
	{ Key{"a", true}, 1 },
	{ Key{"b", true}, 2 },
	{ Key{"c", true}, 3 },
};

m[{"a"}]; // 1

string_ref str = "b";
m[str]; // 2   暗黙の型変換

……………………。

テキトーに時間計測を行ってみた結果、確かに、string をキーとした時よりも、速かった。とは言えそこまで大した差ではない。

ぶっちゃけこんなことするくらいならばもっと別の箇所を見直したほうがいいような気がした。

v8を崇めよ

映画を見に行った。

今年頭の「楽園追放」ぶりの映画館だ。

お目当ては「ジュラシック・ワールド」、Twitterで某氏がご満悦のようであったので気になっていたのだ。

予約は済ませた。そして、映画館にたどり着いた。

 

――上映時間を間違えた。20:40からの上映にもかかわらず18:50着。我ながらどう勘違いしたのか分からない。そこでふとチケット売り場の上映情報を見た。「2D字幕・マッドマックス 19:05」。

そもそも今日はマッドマックスを見るために映画館に行くはずだったのだが、マッドマックスのレイトショーでの上演は22:00以降であったため、マッドマックスは次の機会に、取り敢えず本日のところは興味のあったジュラシック・ワールドを見ておこうと思ったのだ。

19:05は通常料金ではあるがまあ差分は大した出費ではない。チケットを購入した。

 

マッドマックスは全席ペアシートであった。

一人で悠々と、広い座席を専有してくつろぎつつ上映を待った。

 

 

本編開始2分から上映時間の7000秒間、口を閉じることすら忘れひたすらにv8エンジンに脳汁を絞られ続けた。

v8エンジンを崇めよ。

四則演算がしたかった

さて、文字列として与えられた数式を計算して、その結果を得たい。

まず思い浮かんだのは逆ポーランド記法である。

逆ポーランド記法ならば簡単に数式を解釈出来る。

数値が現れればスタックにプッシュ、演算子が現れれば数値をスタックからポップして計算結果をプッシュするだけだ。

以下のコードはD言語によって記述されている。また、コードを単純にするために入力された式の誤りは考えない。

import std.stdio;
import std.string;
import std.ascii:isDigit;
import std.conv:to;

T popBack(T)(ref T[] arr) {
	T back = arr[$-1];
	arr = arr[0..$-1];
	return back;
}

double npl(string[] tokens) {
	double[] stack;

	foreach(token; tokens) {
		if(token[0].isDigit) {
			//	数値はプッシュ
			stack ~= token.to!double;
		}
		else  {
			//	演算子ならポップ
			double b = stack.popBack();
			double a = stack.popBack();

			switch(token) {
			case "+": stack ~= a+b; break;
			case "-": stack ~= a-b; break;
			case "*": stack ~= a*b; break;
			case "/": stack ~= a/b; break;
			default : assert(0);
			}
		}
	}

	//	スタックの一番上が計算結果
	return stack[$-1];
}


double eval(string src) {
	return src.split(" ").npl();
}

void main() {
	readln().chomp.eval().writeln();
}
>dmd -run a.d
3 1 5 + 2 3 + * - 9 /
-3

逆ポーランド記法の数式

3 1 5 + 2 3 + * - 9 /

中置記法で表すと

(3-(1+5)*(2+3))/9 == -3

であるため、出力は正しい。

数式を文字列で受け取り、計算結果を返す関数eval()は、トークン列を受け取り計算結果を返す関数npl()にほとんどの処理を丸投げしている。

では、中置記法の数式を解析したい。調べてみるとおあつらえ向きのものが存在した。「操車場アルゴリズム」である。

これは、ようは中置記法から逆ポーランド記法の数式を生成するためのアルゴリズムと言える。

ひとまず括弧のことは考えずに数値と +-*/ の4つの演算子のみで構成された中置記法の数式を解析しようと思う。

import std.conv:to, parse;

double eval(string src) {
	string[] nplTokens;
	string[] opStack;

	while(src.length) {
		if(src[0].isDigit) {
			//	数値ならば読み進める
			nplTokens ~= src.parse!double().to!string;
		}
		else {
			//	演算子
			if(src[0] == '+' || src[0] == '-') {
				//	空になるまで取り出す
				while(opStack.length)
					nplTokens ~= opStack.popBack();
			}

			//	スタックにプッシュ
			opStack ~= src[0..1];
			src = src[1..$];
		}
	}

	//	残った演算子を全部取り出す
	foreach_reverse(op; opStack)
		nplTokens ~= op;

	//	変換結果を出力
	nplTokens.writeln();

	return nplTokens.npl();
}
>dmd -run b.d
3-1+5*2+3/9
["3", "1", "-", "5", "2", "*", "+", "3", "9", "/", "+"]
12.3333

mainとnplには手を加えていないため省略した。

いろいろと無駄は多いが、気にしないことにする。

次に、括弧の処理を加える。

コードの変更は少しだ。

double eval(string src) {
	string[] nplTokens;
	string[] opStack;

	while(src.length) {
		if(src[0].isDigit) {
			//	数値ならば読み進める
			nplTokens ~= src.parse!double().to!string;
		}
		else {
			//	演算子
			if(src[0] == '+' || src[0] == '-') {
				//	空になるか、左括弧まで取り出す
				while(opStack.length && opStack[$-1] != "(")
					nplTokens ~= opStack.popBack();
			}
			else if(src[0] == ')') {
				//	右括弧の時は左括弧まで取り出す
				while(opStack[$-1] != "(")
					nplTokens ~= opStack.popBack();

				//	左括弧は捨てる
				opStack.popBack();
			}

			//	右括弧でないならばスタックにプッシュ
			if(src[0] != ')')
				opStack ~= src[0..1];
		
			src = src[1..$];
		}
	}

	//	残った演算子を全部取り出す
	foreach_reverse(op; opStack)
		nplTokens ~= op;

	//	変換結果を出力
	nplTokens.writeln();

	return nplTokens.npl();
}
>dmd -run c.d
(3-(1+5)*(2+3))/9
["3", "1", "5", "+", "2", "3", "+", "*", "-", "9", "/"]
-3

効率もいいとは言えないし、現状柔軟性もなにもない。更にはエラーチェックもろくにしていないため妙なものを渡せば即落ちる危ういものではあるが、一応文字列として与えられた数式から計算結果を得られた。

今回はD言語でプログラムを記述したが、配列を柔軟に扱えるのはありがたい。

それから、個人的にD言語のUFCS(Uniform Function Call Syntax)は好きだ。

やり過ぎは良くないとはわかっているのだがついつい関数をぽんぽんと後ろに繋げていってしまう。