2016-08-16

C++1z ランダムサンプリングアルゴリズム

C++

C++1zでは<algorithm>ヘッダに、範囲の中から指定された個数の要素をランダムに抽出するsample()アルゴリズムが定義されます。

#include <iostream>
#include <string>
#include <iterator>
#include <random>
#include <algorithm>

int main()
{
    const std::string input = "abcdef";

    // inputから3要素を無作為抽出する。
    // デフォルトの乱数生成器を使用する
    {
        std::string result;
        std::sample(input.begin(),
                    input.end(),
                    std::back_inserter(result),
                    3);
        std::cout << result << std::endl;
    }

    // inputから3要素を無作為抽出する。
    // 乱数生成器を明示的に渡す
    {
        std::random_device seed_gen;
        std::mt19937 engine {seed_gen()};

        std::string result;
        std::sample(input.begin(),
                    input.end(),
                    std::back_inserter(result),
                    3,
                    engine);
        std::cout << result << std::endl;
    }
}

選ばれる確率は等確率になります。

範囲の要素数が、指定された抽出数よりも小さい場合、範囲の要素数だけ抽出されます。

乱数生成器を渡さない場合、スレッドローカルな乱数生成器が関数内で定義されます。この記事の執筆時点で実装がないので実際にどうなるかはわかりませんが、おそらくdefault_random_engineが使われることになるので、自分で乱数生成器を渡すのがよいと思います。

このアルゴリズムの最適化の余地として、以下の2つの実装がありえます：

出力をランダムアクセスで行うバージョン : KnuthのAlgorithm R (Reservoir sampling)
出力を前から順番に行うバージョン : KnuthのAlgorithm S (Selection sampling)

イテレータカテゴリによってこれらの実装が、コンパイル時に自動的に選択されるようになる可能性があります。

宣言

// <algorithm>
namespace std {
    template <class PopulationIterator, class SampleIterator, class Distance>
    SampleIterator sample(PopulationIterator first, PopulationIterator last,
                          SampleIterator out, Distance n);

    template <class PopulationIterator, class SampleIterator,
              class Distance, class UniformRandomNumberGenerator>
    SampleIterator sample(PopulationIterator first, PopulationIterator last,
                          SampleIterator out, Distance n,
                          UniformRandomNumberGenerator&& g);
}

参照

The Art of Computer Programming, Volume 2: Seminumerical Algorithms
random_sample - SGI STL
random_sample_n - SGI STL
N3547 Three <random>-related Proposals
Three <random>-related Proposals, v2
N3842 A sample Proposal
N4531 std::rand replacement, revision 3
- C++1zではいまのところ、この提案はsampleのデフォルト乱数生成器インタフェースだけ採択されている
P0220R0 Adopt Library Fundamentals TS for C++17
P0220R1 Adopt Library Fundamentals V1 TS Components for C++17 (R1)

お断り

この記事の内容は、C++1zが正式リリースされる際には変更される可能性があります。正式リリース後には、C++日本語リファレンスサイトcpprefjpの以下の階層の下に解説ページを用意する予定です。

言語機能 - cpprefjp C++日本語リファレンス

2016-08-09

C++1z 文字列検索アルゴリズム

C++

C++1zでは、文字列内の文字列を高速に検索するためのアルゴリズムとして、「ボイヤー・ムーア法 (Boyer-Moore)」と「ボイヤー・ムーア・ホースプール法 (Boyer-Moore-Horspool)」が導入されます。

これは、既存のstd::search()アルゴリズムを拡張する形で行われ、検索アルゴリズムを外部から指定するためのパラメータが追加されます。

#include <iostream>
#include <string>
#include <algorithm>
#include <functional>

int main()
{
    // ボイヤー・ムーア法で、文字列内の特定文字列を検索
    const std::string corpus = "…"; // 検索対象
    const std::string pattern = "…"; // 対象の中に見つけたい文字列

    auto it = std::search(
                corpus.begin(),
                corpus.end(),
                std::boyer_moore_searcher(
                    pattern.begin(),
                    pattern.end()
                ));
    if (it != corpus.end()) {
        std::cout << "found" << std::endl;
    }
    else {
        std::cout << "not found" << std::endl;
    }
}

検索アルゴリズムは以下の3つが用意されます。

default_searcher
boyer_moore_searcher
boyer_moore_horspool_searcher

default_searcherはこれまで通りのstd::search()の動作をします。

宣言

// <algorithm>
namespace std {
    template <class ForwardIterator, class Searcher>
    ForwardIterator search(ForwardIterator first, ForwardIterator last,
                           const Searcher& searcher);
}

// <functional>
namespace std {
    // 検索ポリシークラス
    template <class ForwardIterator, class BinaryPredicate = equal_to<>>
    class default_searcher;

    template <class RandomAccessIterator,
              class Hash = hash<
                      typename iterator_traits<RandomAccessIterator>::value_type
                    >,
              class BinaryPredicate = equal_to<>>
    class boyer_moore_searcher;

    template <class RandomAccessIterator,
              class Hash = hash<
                      typename iterator_traits<RandomAccessIterator>::value_type
                    >,
              class BinaryPredicate = equal_to<>>
    class boyer_moore_horspool_searcher;
}

Boostと標準の差異

Boost 1.50.0でBoost Algorithm Libraryがリリースされ、そこに文字列検索のアルゴリズムが含まれています。Boost 1.61.0現在は、std::search()を拡張するようなポリシーベースの設計ではなく、アルゴリズムごとに別名の関数が定義されています。

Boostの方には、標準に追加される2つのアルゴリズムに加えて、knuth_morris_pratt_search()アルゴリズムがあります。これはKMP法という名前で知られているアルゴリズムです。(クヌース・モリス・プラット法)

参照

お断り

言語機能 - cpprefjp C++日本語リファレンス

2016-08-08

C++1z 多相アロケータとメモリプール

C++

C++1zから、アロケートする型を規定しないアロケータと、それを利用したメモリプールの仕組みが導入されます。

std::allocator<T>クラスは型Tのオブジェクトをアロケートする機能を提供しますが、アロケートする型ごとにアロケータオブジェクトが必要になり、メモリリソースを共有することが難しい仕組みになっています。

C++1zの多相アロケータは、あらゆる型のオブジェクトをアロケートする基本的な仕組みとなります。

この目的のために<memory_resource>ヘッダが新設され、大きく以下の2つのクラスが定義されます：

std::pmr::polymorphic_allocator
std::pmr::memory_resource

polymorphic_allocatorクラスは共有メモリリソースを使用するメモリアロケータ。memory_resourceクラスは共有メモリリソースの基本クラスになります。

memory_resourceから派生したクラスを共有メモリリソースとして使用できます。標準では<memory_resource>ヘッダに、以下の3つのメモリリソースが定義されます。

std::pmr::synchronized_pool_resource : スレッドセーフなメモリプール
std::pmr::unsynchronized_pool_resource : スレッドセーフではないメモリプール
std::pmr::monotonic_buffer_resource : 一度に全てを解放するような状況で使用する、高速なメモリアロケートを行う特殊なメモリリソース

また、多相アロケータとメモリリソースを扱いやすくするために、フリーストアを使用する標準の全てのコンテナに対して、polymorphic_allocatorを指定済みの別名がstd::pmr名前空間に定義されます。これを使用してコードを書くと、以下のようになります。

#include <memory_resource>
#include <vector>
#include <string>

int main()
{
    // スレッドセーフなメモリプールを使用する
    std::pmr::synchronized_pool_resource mem_res;

    // vとsでメモリリソースを共有する
    std::pmr::vector<int> v(&mem_res);
    std::pmr::string s(&mem_res);
}

polymorphic_allocatorクラスはmemory_resourceオブジェクトへのポインタをコンストラクタで受け取るので、コンテナにメモリリソースへのポインタを渡せば、polymorphic_allocatorにメモリリソースが伝搬されます。メモリリソースをコンテナに渡さない場合は、グローバルなデフォルトのメモリリソースが使用されます。デフォルトのメモリリソースは、std::pmr::set_default_resource()関数で設定できます。

#include <memory_resource>
#include <vector>
#include <string>

int main()
{
    // スレッドセーフなメモリプールを
    // デフォルトのメモリリソースとして使用する
    std::pmr::synchronized_pool_resource mem_res;
    std::pmr::set_default_resource(&mem_res);

    // vとsでメモリリソースを共有する。
    // デフォルトのメモリリソースを使用する
    std::pmr::vector<int> v;
    std::pmr::string s;
}

最初のデフォルトメモリリソースとして何が使われるかは未規定です。

参照

お断り

言語機能 - cpprefjp C++日本語リファレンス

2016-08-03

C++1z 文字配列をコピーせず参照してbasic_stringライクな操作をするstring_view

C++

C++1zでは、所有権を持たない文字列クラスとして、basic_string_viewクラスが導入されます。その別名として、char文字配列を扱うstring_view、char32_t文字配列を扱うu32string_viewなどが定義されます。

このクラスは、文字列リテラルような文字配列に対して、basic_stringクラスが提供するような便利なメンバ関数を使うためのものです。文字配列はbasic_stringクラスに代入できますが、その際に動的メモリ確保が行われます。しかし、basic_stringクラスの機能を使いたいだけで、basic_stringオブジェクトとして扱いたいわけではないという状況で、basic_string_viewクラスを使用します。

basic_string_viewクラスのために、<string_view>ヘッダが新設されます。

#include <iostream>
#include <string_view>

std::string_view extract_part(const std::string_view& str)
{
    // 文字列リテラルから部分文字列を抽出する
    return str.substr(2, 3);
}

int main()
{
    // 返された部分文字列の先頭文字を参照する
    if (extract_part("ABCDEFG").front() == 'C') {
        // …
    }
}

basic_string_viewは実装内部では文字配列へのポインタと長さくらいしか持たず、動的メモリ確保もしないので軽量です。

string_viewのリテラル

basic_string_viewクラス向けのsvというリテラル演算子も定義されます。

namespace std {
inline namespace literals {
inline namespace string_literals {

constexpr string_view    operator "" sv(const char* str, size_t len) noexcept;
constexpr u16string_view operator "" sv(const char16_t* str, size_t len) noexcept;
constexpr u32string_view operator "" sv(const char32_t* str, size_t len) noexcept;
constexpr wstring_view   operator "" sv(const wchar_t* str, size_t len) noexcept;

}
}
}

using namespace std::string_literals;
std::string_view sv = "ABCD"sv;

basic_stringとのインタフェース差異

std::basic_string_viewクラスは、std::basic_stringクラスとほぼ同じインタフェースを提供しますが、完全に同じではありません。ここでは、大きめな差異を示します：

basic_string_viewは、アロケータのインタフェースを持たない。クラスのテンプレートパラメータにAllocatorがなく、コンストラクタやメンバ関数のインタフェースもアロケータを受け取らない
basic_string_viewは、remove_prefix()、remove_suffix()メンバ関数を持つ。ポインタを後ろにずらすか、長さを減らすかするだけの関数
basic_stringクラスのbasic_stringを受け取るインタフェースに、basic_string_viewクラスからの変換機能が追加される
basic_string_viewは、入力ストリーム演算子を持たない。出力ストリーム演算子は持つ
basic_string_viewは、assign()、append()、push_back()、pop_back()、insert()、erase()、replace()、operator+=といった動的メモリ確保が必要になる操作や、破壊的な操作は持たない

Boost実装

basic_string_viewはBoostで実験的な実装が行われ、標準への最初の提案バージョンがBoost 1.59.0でbasic_string_refという名前で導入された
Boost 1.61.0でbasic_string_viewという名前に変更され、古い名前は非推奨となっている

参照

更新履歴

2017/01/24 16:20 string_viewのリテラルについて追記

お断り

言語機能 - cpprefjp C++日本語リファレンス

2016-08-02

C++1z 型安全な共用体variantクラス

C++

C++1zから、型安全な共用体(type-safe union)の実装であるvariantクラスが導入されます。

このクラスは、テンプレート引数で与えた候補型のリストに含まれる型のオブジェクトを代入できる型です。また、ビジター関数オブジェクトを使用することにより、現在代入されている型のオブジェクトを、安全に操作できます。

variantクラスとその関連操作のために、<variant>ヘッダが新設されます。

#include <iostream>
#include <variant>
#include <string>

struct visitor {
    void operator()(int x)
    { std::cout << "int : " << x << std::endl; }

    void operator()(const std::string& x)
    { std::cout << "std::string : " << x << std::endl; }

    void operator()(double x)
    { std::cout << "double : " << x << std::endl; }
};

int main()
{
    // vには、int, std::string, doubleのいずれかが代入される。
    // デフォルト構築では、0番目の型が値初期化される。
    // ここではint()の値を持つ
    std::variant<int, std::string, double> v;

    v = 3;       // int値を代入
    v = "hello"; // 文字列を代入
    v = 1.23;    // double値を代入

    // どの型が代入されているかに関わらず、共通の操作を適用する
    std::visit([](auto x) { std::cout << x << std::endl; }, v);

    // 代入されている型ごとに異なる処理を適用する
    std::visit(visitor(), v);

    // 代入されている値を取り出す
    // 指定した型の値が入っていなかったら例外が送出される
    try {
        double d = std::get<double>(v);
    }
    catch (std::bad_variant_access& e) {
        std::cout << e.what() << std::endl;
    }

    // 代入されている値を取り出す
    // 指定した型の値が入っていなかったらヌルポインタが返る
    if (double* p = std::get_if<double>(&v)) {
    }
    else {
        std::cout << "doesn't contains double value" << std::endl;
    }
}

出力：

1.23
double : 1.23

std::variantのデフォルトコンストラクタは、第1テンプレート引数に指定された型を値初期化します。variantを空にしたい場合には、std::monostateという空のクラスをvariantの第1テンプレート引数に指定することになります。

そのほかに、variantが不正な状態として空になる場合があります。これは、以下のように代入する型を変更する状況で、処理の内部で例外が発生した場合です：

struct S { operator int() { throw 42; }};
variant<float, int> v{12.f};
v.emplace<1>(S());

ここではemplace()メンバ関数の中で例外が発生しますが、その際はvariantオブジェクトは不正な状態となります。このような状態では、valueless_by_exception()という述語メンバ関数がtrueを返し、現在代入されている型のインデックスを取得するindex()がstd::variant_npos値を返すようになります。

Boostと標準の差異

Boost 1.61.0時点のvariantと標準に予定されているものには、以下のような差異があります。

Boostのvariantには「決して空にならない保証 (Never empty guarantee)」がある。そのために、標準とは違い不正な状態というものにはならない
Boostのvariantはビジターを適用するためにapply_visitor()非メンバ関数を持つ。標準ではvisit()非メンバ関数
Boostのvariantは代入されている型のインデックスを取得するwhich()メンバ関数を持つ。標準ではindex()メンバ関数
Boostのvariantには再帰的定義のためのrecursive_variantがあるが、標準にはない

参照

お断り

言語機能 - cpprefjp C++日本語リファレンス

2016-08-01

C++1z 統一的な有効値と無効値の表現をもつoptionalクラス

C++

C++14で入りそうで入らなかったoptionalクラスですが、C++1zで入ることになりました。

optionalは、テンプレート引数で指定した型の値を有効値、std::nulloptという特殊なオブジェクトを無効値と見なす型です。

ひとつの型で有効値と無効値を表すために、intだったら負の値、ポインタだったらヌル、文字列だったら空文字列を無効値として使用されてきました。これは関数の仕様として無効値の範囲を定義する方法ですが、optionalクラスは型として無効値の表現を持ちます。

#include <iostream>
#include <optional>

int main()
{
    // 有効値3を代入
    std::optional<int> opt = 3;

    // 有効かを判定
    if (opt) {
        // 有効値を取り出す
        int& x = opt.value();
        std::cout << x << std::endl;
    }

    // 無効値を代入
    opt = std::nullopt;
    if (!opt) {
        std::cout << "nullopt" << std::endl;
    }
}

出力：

3
nullopt

これにより、関数を定義するプログラマが、有効値かエラーかのどちらかを戻り値として返したい場合には、値の仕様を考える必要なく、optionalを戻り値の型に設定すればよくなります。

optionalクラスは、新設される<optional>ヘッダで定義されます。

Boostと標準の差異

optionalクラスは、Boostで古くから提供されていた機能で、それをベースに標準の仕様が策定されました。標準の仕様が固まっていくにつれてBoostの方も合わせて機能が更新されていっているので、Boost 1.61.0時点では、この2つの差異はかなり小さくなっています。(標準の仕様を考えている人とBoost.Optionalのメンテナは同一人物です)

その前提で、現状の差異は以下のようになっています：

標準は全面的にconstexpr対応している
Boostの無効値はboost::none、標準の無効値はstd::nullopt
標準では、anyとvariantとの共通設計のために、有効値を持つか判定するhas_value()メンバ関数、make_optional()非メンバ関数が定義される
標準はoptional<T&>の部分特殊化が定義されない
標準では入出力のストリーム演算子が定義されない (出力フォーマットの合意が得られなかった)
標準はハッシュサポートがある

補足として、expectedクラスにあるようなモナドインタフェース(bind()、map())や、0 or 1要素のRangeとして扱う機能はありません。

参照

お断り

言語機能 - cpprefjp C++日本語リファレンス

2016-07-29

C++1z なんでも代入できるanyクラス

C++

C++1zでは、コピー可能かムーブ可能であればどんな型でも代入できるanyクラスが入ります。C++には全ての型の継承元のobjectクラスというものはないので、その代わりにこのクラスを使えます。

このクラスのために、<any>ヘッダが新規追加されます。

#include <iostream>
#include <any>
#include <string>

int main()
{
  std::any a = 3; // int値を代入
  a = std::string("hello"); // stringオブジェクトを代入

  // 中身を取り出す
  // 取り出せなかったらstd::bad_any_cast例外
  try {
    std::string s = std::any_cast<std::string>(a);
    std::cout << s << std::endl;
  }
  catch (std::bad_any_cast& e) {
    std::cout << "bad_any_cast" << std::endl;
  }

  // 中身を取り出す
  // こちらは取り出せなかったらヌルポインタが返る
  if (std::string* s = std::any_cast<std::string>(&a)) {
    std::cout << *s << std::endl;
  }
  else {
    std::cout << "null" << std::endl;
  }
}

出力：

hello
hello

Boostと標準の差異

標準に採択されたanyは、Boostにあるanyとほぼ同じです。Boost 1.61.0時点のanyとの差異は、constexpr対応していることに加え、optionalとvariantと共通の設計にするために、標準側に以下の機能があるくらいです：

make_any()非メンバ関数
in placeコンストラクタ
emplace()メンバ関数
reset()メンバ関数
has_value()メンバ関数

この共通設計のために、Boostにある以下のメンバ関数はありません：

clear()メンバ関数
empty()メンバ関数

参照

お断り

言語機能 - cpprefjp C++日本語リファレンス

2016-07-28

C++1z shared_ptr::weak_type

C++

C++1zから、shared_ptrの入れ子型としてweak_typeが追加されます。

これは、shared_ptr<T>に対するweak_ptr<T>型の別名です。

shared_ptrの要素型を取り出してweak_ptrのテンプレート引数を埋めることが冗長なコードになっていたための対処です。

shared_ptr<T> sptr = …;

// shared_ptrをweak_ptrに変換してラムダ式に渡す
auto f = [wptr = typename decltype(sptr)::weak_type(sptr)] {
  // この関数が呼ばれたときには、wptrが指す先のオブジェクトが死んでいる可能性がある
  if (wptr.lock()) {
    …
  }
}