C++17の標準ライブラリ

発表者:江添亮

言語:C++

仕事:ドワンゴ

趣味:ボルダリング、factorio

C++17

2017年に発行される予定の標準規格

変更点

多数のマイナーな問題の修正

コア言語の新機能は少ない

新しいライブラリが多い

C++17の標準ライブラリの紹介

正式な規格はまだ変わる可能性がある

文字列検索

みんな文字列検索してますか?

boyer moore search

Robert S. BoyerとJ Strother Mooreが1977に発表した

高速な文字列検索アルゴリズム

みんな知ってるよね?

知らない方に朗報

Donald Knuth著

The Art of Computer Programming Vol.4A

アスキードワンゴから今秋発売予定

コード例

    auto pattern = "..."s ;
    auto text = "..."s ; 

    auto bm_search = 
        make_boyer_moore_searcher
            ( begin(pattern), end(pattern) ) ;

    auto iter = bm_search( begin(text), end(text) ) ;

ジェネリックな実装になっている

char型以外でも使用可能

よくあるcharに対するBM法の実装

パターン中の文字に対応するスキップ数をテーブルで持っておく

// charの全状態数
std::size_t skip_table[256] ;

std::string pattern ;
auto len = pattern.size() ;

std::fill_n( table, 256, len ) ;

for ( auto c : pattern )
{
    skip_table[c] = len-- -1 :
}

char16_tなら?

// 524KB
// sizeof(size_t) == 8
std::size_t skip_table[65536] ;

char32_tなら?

// 34GB
std::size_t skip_table[4294967296] ;

パターンに含まれている文字種は少ないので

unordered_mapで管理すればいい

std::basic_string<T> pattern ;
auto len = pattern.size() ;

std::unordered_map<T, std::size_t> skip_table ;

for ( auto c : pattern )
{
    skip_table[c] = len-- -1 ;
}

unordered連想コンテナーを使うことで

hash対応した任意の型に対して使用できる

charの場合に最適化することも可能

boyer_moore_horspool_searcher

実行時間と引き換えにメモリ消費量が少ない版

optional<T>

T型のオブジェクトを持っているかもしれないクラス

期待するオブジェクトを生成できず

エラー通知の必要のある関数

// 除算する関数
int div( int x, int y )
{
    if ( y != 0 )
        return { x / y } ;
    else
        return // どうする? 
}

よくある対応

特別な値を返す

この場合は使えない

結果として通知する型はすべての値を取りうる

よくある対応

戻り値と引数で結果を返す

極めて読みづらい

// 戻り値でエラー通知、引数で結果
bool div( int x, int y, int & result ) ;
// 戻り値で結果、引数でエラー通知
int div( int x, int y, bool & error ) ;

よくある対応

グローバル変数

並列処理と相性が悪い

if ( (fp = fopen("foobar", "r")) == NULL )
{
    if ( errno == EINVAL )
        std::cout << "引数が間違っている\n" ;
    else if ( errno == ENOMEM )
        std::cout << "メモリが足りない\n" ;
}
<

よくある対応

例外

この場合、頻繁に発生する可能性があるので使いづらい

解決策

optional<T>

値を格納するか、していないクラス

使い方

関数側

std::optional<int> div( int x, int y )
{
    if ( y != 0 )
        return { x / y } ;
    else
        return {} ;
}

使い方

呼び出し元

値がある場合boolに変換される

値はoptional::value()で取り出せる

void f( int x, int y )
{
    auto result = div( x, y ) ;

    if ( result )
        // 値あり
        result.value() ;
    else
        // 値なし
}

値がないのにvalue()を呼び出すと例外

bad_optional_accessがthrowされる

auto result = div( 1, 0 ) ;
result.value ; // 例外

value_or

値がないときにデフォルト値を使う

auto result = div( 1, 0 ) ;
result.value_or(0) ; // 0

any

どんな型でも格納できるクラス

使い方

It Just Works.

std::any a ;
a = 0 ; // int
a = 0.0 ; // double
a = "hello"s ; // std::string
a = std::vector<int>{} ;

どんな型でも代入できる

CopyConstructibleでさえあればいい

テンプレートとか考える必要なし

値の取り出し方

any_cast<T>を使う

値を取り出すには型を指定する必要がある

型を間違えるとbad_any_castがthrowされる

void f( std::any a )
{
    auto x = std::any_cast<int>(a) ;
}

anyへのポインターを渡すと結果もポインターになる。

型が違うとnullptrが返る

void f( std::any a )
{
    auto p = std::any_cast<int>( &a ) ;
    if ( p != nullptr )
        *p ; // int   
}

string_view

文字列ラッパー

文字列を扱う方法がバラバラだ

ライブラリはそれぞれに対応する必要がある

// null終端配列
void f( const char * str ) ;
// 配列と要素数
void f( const char * str, std::size_t len ) ;
// basic_string
void f( std::string const str ) ;

string_view

文字列の差異を吸収してくれる

文字列は所有しない

使い方

関数側

引数をstring_viewで受けるだけ


void f( std::string_view str )
{
// std::stringと同じ感覚で使える。
} ;

使い方

呼び出し側

string_viewが差異を吸収

// null終端配列
f( str ) ;
// 配列と要素数
f( std::string_view{str, len} ) ;
// basic_string
f( str ) ;

乱択

みんな乱択してますか?

乱択とは

ある要素の集合からN個の要素をランダムに選ぶ

みんな知ってるよね?

知らない方に朗報

Donald Knuth著

The Art of Computer Programming Vol.2

アスキードワンゴから発売中

C++17なら簡単

std::vector<int> input = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } ;
std::size_t const n = 5 ;
std::vector<int> output( n ) ;
std::sample( begin(input), end(input), begin(output), n ) ;

gcdとlcm

追加される

std::gcd( m, n ) ;
std::lcm( m, n ) ;

先ほどのスライドがわからなかった方に朗報

Donald Knuth著

The Art of Computer Programming Vol.1

アスキードワンゴから発売中

source_location

ソースコード情報の取得ライブラリ

ソースコード中の情報がほしい

どうする?

int main(){
    if ( !f() )
    {
        std::cout <<
            "in function X,"
            " f() returned false"
            " in filename Y at line Z." ;
    }

}

Cプリプロセッサーマクロを使う

__FILE__, __LINE__, __func__が使える

ただしその場に書かなければならない。

その場に定数として展開される

単なるトークン列の置き換え

使いづらい

ソースコード情報をC++の言語から扱いたい

ちゃんとC++でサポートされていて

コードの中で使えるもの

そこでsource_location

ソースコードの情報を取得できる

オブジェクトとして保持できる

使い方

// この場所のソースコード情報を取得
auto s = std::source_location::current() ;
// 行数
auto line = s.line() ;
// 行頭からの文字数
auto column = s.column() ;
// ファイル名
auto file_name = s.file_name() ;
// 関数名
auto function_name = s.function_name() ;

関数のデフォルト実引数に使った場合

呼び出し元のソースコード情報が得られる

void log
(
    std::string msg,
    std::source_location s = std::source_location::current()
)
{
    // ログを取る
}

int main()
{
    log("main executed.") ; // この場所のソースコード情報を取得
}

乱数

みんな知ってるよね?

知らない方に朗報

Donald Knuth著

The Art of Computer Programming Vol.2

アスキードワンゴから発売中

言いたい

ところだが

Knuth本は乱数の均一分布方法についてまともに解説していない

はっきりいって時代遅れ

texのように

C言語時代の乱数ライブラリ

rand関数

はっきり言ってクソ

  • 乱数の範囲がクソ
  • 乱数の生成もクソ
  • 使われ方もクソ

乱数の範囲がクソ

rand()の戻り値Nの範囲は

\[0 \leq N \leq RAND\_MAX \]

乱数の範囲を変える方法はない

乱数の生成もクソ

rand()はどのように乱数を生成するのか規定していない

周期が短く、規則性がある、貧弱な実装もある

乱数の生成方法を変える手段もない

使われ方もクソ

実際にほしい乱数は0からRAND_MAXまでの範囲ではない

6面ダイスを実装するなら1から6までの範囲で均一に分布する乱数がほしい

ではどうするのか?

現実に書かれているクソコード

このようなコードを書いてはならない

int dice()
{
    return rand()%6 + 1 ;
}

何故か

乱数の生成方法がわからない

値が均一に分布しないため

6面ダイスならば1から6まで6種類の値がそれぞれ等確率で出るはず

C++11の乱数ライブラリ

とても美しい設計

世のプログラマーの乱数需要はだいたい満たしている

<random>

乱数エンジン

(random number engine)

生の乱数ビット列を生成するクラス

線形合同法: minstd_rand, minstd_rand0

メルセンヌツイスター: mt19937, mt19937_64

Ranlux: ranlux24_base, ranlux48_base, ranlux24, ranlux48

KnuthのAlgorithm B: knuth_b

/dev/urandom : random_device

デフォルトの乱数: default_random_engine

使い方

operator ()を呼び出すだけ

std::knuth_b knuth ;
std::cout << knuth() << '\n' ;

ではさっそく

これでは一様に分布しない

int dice()
{
    thread_local std::knuth_b knuth ;
    return knuth()%6 + 1 ;
}

なぜ一様に分布しないのか

6通りに分布させる必要がある

コンピューターはバイナリで乱数を表現する

最低3bit必要

3 bitは8通りに分布する

\(\frac{6}{8}\)は割り切れない

割り切れるバイナリ乱数はあるのか?

\[2^n \bmod 6 = 0\]

となるn(\(n \geq 1\))を探せばよい

よーし探すぞ

\[ 2^n \bmod 6 = 2^n \bmod {2 \times 3} = 2^{n-1} \bmod 3 \]

2は3で割り切れない

存在しなかったよ

無限のビット列を持ってこい

6通りに均一に分布させる方法

  1. 3bitの乱数rを生成
  2. 6以上ならばgoto 1.
  3. 乱数rは6通りに分布している
int dice()
{
    thread_local std::knuth_b knuth ;
    auto rand_3bit = [&]{ return knuth() & 0b111 ; } ;
    auto r = rand_3bit() ;

    while ( r >= 6 )
    {
        r = rand_3bit() ;
    }

    return r + 1 ;
}

こんなのいちいち

手で書いていられるか

分布ライブラリ

(distribution)

生の乱数ビット列を望みの分布に加工するクラス

プログラマーは望みの分布の情報だけ書けばよい

整数の一様分布

\(a \geq r \geq b\)の範囲に一様に分布する乱数rを返す

int dice()
{
    thread_local std::knuth_b knuth ;
    std::uniform_int_distribution<int> dist( 1, 6 ) ;
    return d( knuth ) ;
}

浮動小数点数の一様分布

\(a \geq r \gt b \)の範囲の浮動小数点数の乱数rを返す

範囲に注意

値bは返さない

namespace Math {
double random()
{
    thread_local std::knuth_b knuth ;
    std::uniform_real_distribution dist( 0.0, 1.0 ) ;
    return dist( knuth ) ;
} 

}

その他の分布

ベルヌーイ分布、二項分布、幾何分布、負の二項分布

ポアソン分布、指数分布、ガンマ分布、ワイブル分布、極値分布

正規分布、対数正規分布、カイ二乗分布、コーシー分布、F分布、t分布

離散分布系: 離散確率分布、区分的定数分布、区分的線形分布

どの分布も目的に応じて役に立つ

ベルヌーイ分布の使い方

ある確率pでtrueを、1 - pの確率でfalseを返す

お題: 宝箱

  • 30%の確率で宝が入っている
  • 70%の確率で空っぽである
  • 宝が入っているかどうかをboolで返す関数を書け

素人の実装

0から9までの一様分布する整数の乱数を作って

2以下だったらtrueを返す

値の範囲を与える必要がある

比較も自分で書く必要がある

間違いの元

bool open_chest()
{
    thread_local std::default_random_engine e ;
    std::uniform_int_distribution<int> dist( 0, 9 ) ;

    return dist( e ) <= 2 ;
}

C++プログラマーの実装

確率だけ与えればよい

bool open_chest()
{
    thread_local std::default_random_engine e ;
    std::bernoulli_distribution dist( 0.3 ) ;

    return dist( e ) ;
}

結論

C++11でプログラマーはあらゆる需要を満たす

乱数ライブラリを手に入れた

めでたしめでたし

本当にそうか?

エンジンと分布が分かれている設計

実際に使うのは面倒じゃないか?

ベルヌーイだのポアソンだのと言われてわかるか?

ベルヌーイの歴史に興味がないので飛ばす

1680年

天空に突如として巨大な彗星が出現

昼間でも尾を引いて見えるほどの規模

数カ月間も続いた

一般大衆と坊主は大混乱

神がお怒りに違いない

その中、スイス、バーゼルで

彗星を見つめる一人の若い神学徒がいた

ヤコブ・ベルヌーイ

(1655-1705)

スイスのバーゼル生まれ

父親の意向で神学を学ぶ

後に数学者に転向

ベルヌーイは考える

この天変地異は物理学で説明できるはずだ

神学は己の生涯をかけるに値する学問ではない

己の人生は数学のためにある

ベルヌーイは圧倒的な数学力で頭角を現す

1686年にはバーゼル大学の教授になる

ベルヌーイの疑問

コインを投げて表になる確率は\(\frac{1}{2}\)

6面ダイスを投げて1がでる確率は\(\frac{1}{6}\)

しかし現実のコインやダイスには歪みがある

確率のわからないものに対してはどうすればいいのだ

ベルヌーイの発想

何度も試行した結果を観測し

  確率を計測すれば良い

しかし

何度計測すれば

十分に真の確率に近づいたと言えるのだろう

当時はこの問題に使える数学が発明されていなかった

ニュートンとライプニッツ

微積分を発明

嫌がらせのように読みにくい論文

ベルヌーイなら読めた

ベルヌーイ

大数の弱法則を発明

元の論文Ars conjectandiでは

黄金定理

そういう経緯がありまして

2種類の結果のうち

いずれかをランダムで出す

独立した試行を

ベルヌーイ試行と呼ぶようになった

閑話休題それはさておき

rand()ほど簡単に使えない

使い方を暗記するのは難しい分量

リファレンスを参照しながら書くしかない

初心者には理解することが多すぎて使えず

プログラマーには統計の知識を要求され

統計学の素養ある人間にもコード量が多くて使いづらい

しかし、rand()は問題がある。

プログラマーが本当に欲しかったもの

\[a \geq r \geq b \]

の範囲に一様分布する整数の乱数rを返す

randint( a, b ) ;

使い方

int dice()
{
    return std::randint( 1, 6 ) ;
}

randint()

生の欄数列から整数の範囲指定の一様分布までを一気に扱う関数

クラスではないのでオブジェクト管理が不要

randint()のオブジェクト

スレッドごとにdefault_random_engine型のオブジェクトを確保

予測不可能な状態に初期化される

万人に使いやすい乱数ライブラリ

質問

スライド資料

https://github.com/EzoeRyou/cpp17lib-slide