2013-02-21

boost::string_ref に c_str() がない理由

C++ Boost

string_ref について

Boost 1.53.0 で追加された String_Ref は、文字列の所有権を持たずに先頭のポインタとサイズだけを持つクラスです。

const string& の引数を受け取る関数に const char* を渡すと、不要な string オブジェクトが作成されてしまいますが、string_ref を使うことで string と const char* の両方に対応しつつ、余計なアロケーションを防ぐことができます。

サンプルは Faith and Brave - C++で遊ぼう boost::string_ref を参照してください。

string_ref は length() や begin/end(), operator[] など、string とよく似たインターフェイスを持っていますが、c_str() メンバ関数はありません。どうしてでしょう？

c_str() がない理由を考える

string_ref の substr() は、効率のために新しい文字列を作成せず、元のポインタの位置とサイズを変更しただけの新しい string_ref を返します。

そのため、substr() された string_ref から C 言語形式の文字列のポインタを取得した場合、意図する終端でそのポインタが null-terminate している保証がありません。

次のようなコードの動作を見てみましょう。

# include <iostream>
# include <boost/utility/string_ref.hpp>

void Print( const boost::string_ref& str )
{
	std::cout << str << '\n'
			  << str.data() << '\n'
			  << &str[0] << '\n';
}

int main()
{
	const boost::string_ref str = "The quick brown fox";

	Print(str.substr(4,5));
}

quick
quick brown fox
quick brown fox

文字列のポインタと長さを受け取るコンストラクタでも同じことが起こります。

// ...

int main()
{
	const boost::string_ref str("The quick brown fox",3);

	Print(str);
}

The
The quick brown fox
The quick brown fox

c_str() は string_ref 自身が表現する文字列と一致する、null-terminated な文字列へのポインタを返す
string_ref はオリジナルの文字列データを変更しない
string_ref はアロケーションを行わない

という、ユーザーが期待する条件が共存できないため c_str() メンバ関数は実装されなかったのでしょう。

上記のコードで示したように、const char* を受け取る関数に string_ref を使うときは注意が必要です。

2013-02-19

--> 演算子

C++

新しい演算子が採用されたようです。

# include <iostream>

int main()
{
	int x = 10;

	do
	{
		std::cout << x << '\n';
	}
	while(x --> 0);
}

ネタ元 : What is the name of this operator: “-->”? (stackoverflow)

while だと 10 が出力されないので do-while にしました。
こういうの好き。

2013-02-17

C++11 の乱数ライブラリ <random>

C++

C++11 では、新しい乱数ライブラリのヘッダ <random> が追加されました。
一様にランダムな整数を生成する「乱数生成エンジン」と、値を特定の方法で分布させる「分布生成器」が用意されています。

乱数生成エンジンは

線形合同法
メルセンヌ・ツイスター
Lagged Fibonacci 法
ハードウェアエントロピーソース（時刻や CPU カウンター、I/O の状態など大量の低レベルシステム情報）を利用した非決定論的（予測不可能）な乱数生成

の 4 種類が実装されています。非決定論的な乱数生成以外の手法では、初期シードから擬似乱数列を生成します。

分布生成器は

一様分布
正規分布
ベルヌーイ分布
ポアソン分布

をはじめ多数のアルゴリズムが実装されています。

非決定論的な乱数生成エンジン std::random_device を使ってランダムな値を出力してみましょう。プログラムを実行するたびに結果は変わります。

# include <iostream>
# include <random>

int main()
{
	std::random_device rd;

	for(int i=0; i<10; ++i)
	{
		std::cout << rd() << '\n';
	}
}

std::random_device は毎回ハードウェアエントロピーソースを収集するため、実行速度が遅いのが欠点です。
パフォーマンスが必要な用途には、初期シードから長周期の乱数列を高速に生成するメルセンヌ・ツイスターの使用を検討しましょう。

次の例では、メルセンヌ・ツイスターの初期シードに std::random_device で生成した乱数を与えています。

# include <iostream>
# include <random>

int main()
{
	std::random_device rd;

	std::mt19937 mt(rd());

	for(int i=0; i<10; ++i)
	{
		std::cout << mt() << '\n';
	}
}

シードを配列で与えることもできます。

# include <iostream>
# include <random>
# include <array>

int main()
{
	std::random_device rd;

	std::array<unsigned,100> seeds;

	for(auto& s : seeds)
	{
		s = rd();
	}

	std::seed_seq seq(seeds.begin(),seeds.end());

	std::mt19937 mt(seq);

	for(int i=0; i<10; ++i)
	{
		std::cout << mt() << '\n';
	}
}

乱数を、サイコロ [1,6] やゲームのスコア [0.0,10.0] のように、特定の型と範囲に分布させるには、分布生成器を使います。
一様分布生成器 uniform distribution を使って、今述べた 2 つの範囲に一様に分布する乱数を作りましょう。

# include <iostream>
# include <random>

int main()
{
	std::random_device rd;

	std::mt19937 mt(rd());

	std::uniform_int_distribution<int> dice(1,6);

	std::uniform_real_distribution<double> score(0.0,10.0);

	for(int i=0; i<10; ++i)
	{
		std::cout << dice(mt) << '\n';
	}

	for(int i=0; i<10; ++i)
	{
		std::cout << score(mt) << '\n';
	}
}

一様分布の場合、整数型に対しては uniform_int_distribution, 浮動小数点数型に対しては uniform_real_distribution と区別することに注意しましょう。

正規分布やポアソン分布などの特殊な分布を再現したい場合は
http://ja.cppreference.com/w/cpp/numeric/random
を参考にしてください。

[おまけ]
Visual Studio の std::random_device が利用するハードウェアエントロピーソースの一覧
http://blogs.msdn.com/b/michael_howard/archive/2005/01/14/353379.aspx の 2 件目のコメント

2013-02-14

Boost.Multiprecision で桁あふれしない階乗と円周率 1 万桁

C++ Boost

Boost 1.53.0 では、多倍長精度の整数、有理数、浮動小数点数を扱う Multiprecision ライブラリが追加されました。
どの数値型も基本的な演算子に対応し、浮動小数点数は Boost.Math を含む pow や sin などの数学関数に対応しています。

整数型は、コンパイル時に精度が固定された int128_t 型や int256_t 型などのほか、メモリが許す限り実行時にどこまでも精度を拡張できる cpp_int 型が用意されています。
cpp_int 型を使って、桁あふれしない階乗関数を書いてみましょう。

# include <iostream>
# include <boost/multiprecision/cpp_int.hpp>

using namespace boost::multiprecision;

cpp_int Factorial( unsigned n )
{
	cpp_int x = 1;

	while(n)
	{
		x *= n--;
	}

	return x;
}

int main()
{
	std::cout << Factorial(3) << '\n';

	std::cout << Factorial(100) << '\n';

	std::cout << Factorial(300) << '\n';
}

6
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
306057512216440636035370461297268629388588804173576999416776741259476533176716867465515291422477573349939147888701726368864263907759003154226842927906974559841225476930271954604008012215776252176854255965356903506788725264321896264299365204576448830388909753943489625436053225980776521270822437639449120128678675368305712293681943649956460498166450227716500185176546469340112226034729724066333258583506870150169794168850353752137554910289126407157154830282284937952636580145235233156936482233436799254594095276820608062232812387383880817049600000000000000000000000000000000000000000000000000000000000000000000000000

浮動小数点数型はコンパイル時に精度（桁数）を指定します。
50 桁の cpp_dec_float_50, 100 桁の cpp_dec_float_100 型があらかじめ用意されています。
2 の平方根を 100 桁、Boost.Math の constants::pi を使って円周率を 1 万桁表示してみましょう。

# include <iostream>
# include <boost/multiprecision/cpp_dec_float.hpp>
# include <boost/math/constants/constants.hpp>

using namespace boost::multiprecision;
using namespace boost::math::constants;

int main()
{
	const cpp_dec_float_100 f = 2.0;

	std::cout << std::setprecision(101)
			  << sqrt(f)
			  << '\n';

	std::cout << std::setprecision(10001)
			  << pi<number<cpp_dec_float<10000>>>()
			  << '\n';
}

1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727
3.14159265358979323846264338327950288419716939937510582097494459230781640628620...05600101655256375679

ドキュメントによると
The actual precision of a cpp_dec_float is always slightly higher than the number of digits specified in the template parameter, actually how much higher is an implementation detail but is always at least 8 decimal digits.
と、実際には cpp_dec_float は指定した桁数より少し大きい精度を持っていますが、心配な場合は必要な分より大きい精度を指定しておくといいでしょう。

cpp_dec_float の桁数は、内部計算で桁落ちが発生しないよう 14368 が最大値となっていて、それを超えるとコンパイルエラーが発生します。 (boost 1.53.0)