2015-02-05

<shared_mutex>ヘッダのリファレンス作成が完了しました

C++

<shared_mutex> - cpprefjp

C++のリファレンスサイトcpprefjpでは、C++14への対応も進めています。

今回、C++14での大きなライブラリ追加として、<shared_mutex>ヘッダのリファレンスを作成しました。

cpprefjpサイトのC++14対応状況は、GitHub リポジトリの以下のWikiにまとめてあります：

C++14の対応状況 - cpprefjp/site

編集への参加は、常時受け付けています！

2015-02-03

shared_timed_mutexで並行キューを実装した

C++

Readers Writerロックで、並行キューを実装した。

値を返し、例外を投げないpop()も実装しておいた。

実装： shand/concurrent/queue.hpp

インタフェース

namespace shand {
 
template <class T> // Tは、例外を投げないムーブコンストラクタを持っていること
class concurrent_queue {
public:
    concurrent_queue() {}
 
    concurrent_queue(const concurrent_queue&) = delete;
    concurrent_queue& operator=(const concurrent_queue&) = delete;
 
    // write access
    void push(const T& x);
    void push(T&& x);
    boost::optional<T> pop() noexcept;
    void clear();
 
    // read access
    std::size_t size() const;
    bool empty() const;
};
 
} // namespace shand

サンプルコード

#include <iostream>
#include <thread>
#include <shand/concurrent/queue.hpp>
 
void producer(shand::concurrent_queue<int>& que)
{
    for (int i = 0; i < 100; ++i) {
        que.push(i);
    }
}
 
void consumer(shand::concurrent_queue<int>& que)
{
    int i = 0;
    for (;;) {
        if (boost::optional<int> x = que.pop()) {
            std::cout << x.get() << std::endl;
            ++i;
        }
 
        if (i > 30) // てきとうなところで終了する
            return;
    }
}
 
int main()
{
    shand::concurrent_queue<int> que;
 
    std::thread t1(producer, std::ref(que));
    std::thread t2(consumer, std::ref(que));
 
    t1.join();
    t2.join();
}

出力：

値を返し、例外を投げないpop()の実装

値を返し、例外を投げないpop()は、以下のようにして実装しています。

戻り値は、コピーではなくムーブで返す
空の場合を考慮して、optionalで返す
クラスのテンプレートパラメータは、例外を投げないムーブコンストラクタを持っている型のみを受け付ける
optionalのムーブコンストラクタは、Tのムーブが例外を投げなければ、例外を投げない(と、1.57.0のドキュメントに書いていた)

テンプレートパラメータの要件部分：

template <class T>
class concurrent_queue {
    static_assert(
        std::is_nothrow_move_constructible<T>::value,
        "Type T must be nothrow move constructible");
    …
};

pop()の実装部分：

// que_はstd::deque<T>
boost::optional<T> pop() noexcept
{
    std::lock_guard<std::shared_timed_mutex> lock(mutex_);
    if (que_.empty())
        return boost::none;

    T front = std::move(que_.front());
    que_.pop_front();
    return front;
}

参照

2015-01-29

boost::optionalのパターンマッチ as 文

C++

boost::optionalを0 or 1要素のRangeと見なす。

#include <memory>
#include <boost/optional.hpp>

namespace boost {
    template <class T>
    T* begin(boost::optional<T>& opt) noexcept
    {
        return opt.is_initialized() ?
                    std::addressof(opt.get()) :
                    nullptr;
    }

    template <class T>
    T* end(boost::optional<T>& opt) noexcept
    {
        return opt.is_initialized() ?
                    std::addressof(opt.get()) + 1 :
                    nullptr;
    }
}

#include <iostream>
int main()
{
    boost::optional<int> opt = 3;

    for (int& x : opt) {
        std::cout << x << std::endl;
    }
}

出力：

ただし、elseが書けない。

2015-01-28

boost::optionalをパターンマッチする関数

C++

match function on sum types - std-proposals

Vicenteさんが標準向けに提案していた関数を元に、boost::optional用のパターンマッチ関数を作ってみました。

実装
- shand/match.hpp
- shand/type_traits/is_callable.hpp
コード例
- libs/match/example/match.cpp
テスト
- libs/match/test/match.cpp

インタフェース：

// shand/match.hpp

namespace shand {

// 1引数版
template <class T, class F>
void match(boost::optional<T>& x, F f);

template <class T, class F>
void match(const boost::optional<T>& x, F f);

// 2引数版
template <class T, class F1, class F2>
void match(boost::optional<T>& x, F1 f1, F2 f2);

template <class T, class F1, class F2>
void match(const boost::optional<T>& x, F1 f1, F2 f2);

}

関数の型F、F1、F2は、以下のいずれかのシグニチャを持たせます：

R(T&) : optionalオブジェクトが有効な値を持っていれば呼ばれる
R() : optionalオブジェクトが無効な値なら呼ばれる

使用例：

#include <iostream>
#include <boost/optional.hpp>
#include <shand/match.hpp>

int main()
{
    boost::optional<int> a = 3;
    shand::match(a, [](int& x) { // 有効な値を持っていれば呼ばれる
        std::cout << x << std::endl;
    });
 
    boost::optional<int> b;
    shand::match(b, [] { // 無効な値なら呼ばれる
        std::cout << "none" << std::endl;
    });
 
    shand::match(a, // 有効な場合と無効な場合で関数を呼び分ける
        [](int& x) { std::cout << x << std::endl; },
        [] { std::cout << "none" << std::endl; }
    );
}

出力：

3
none
3

この関数は、「optionalオブジェクトが有効な状態かどうか判定してから中身を取り出す」という二段階の処理を同時に行い、「じつは無効な状態なのに中身を取り出そうとした」というミスを防ぐために使用します。

expectedのmap()メンバ関数のようなものです。

実装技術の話

関数から引数の型を取り出して「有効な値用の関数か、無効の値用の関数か」を判定するのではなく、関数が特定のシグニチャで呼び出し可能かを調べるis_callableメタ関数を使用して、判定しています。

is_callable<F, T&>::value == true(FがT&型を受け取って呼び出し可能な関数か、が真)なら有効な値用の関数と見なしています。

is_callable<F>::value == true(引数なし)で無効な値用の関数と見なしています。

参照

2015-01-27

std::beginとstd::endの使い方

C++

コンテナからイテレータを取り出すstd::begin()関数とstd::end()関数は、テンプレート外では名前空間修飾を付けて呼び出す使い方でいいが、テンプレート内で使用する場合は、using宣言した上で名前空間修飾なしに呼び出す必要がある。(std::swap()と同じ)

#include <iterator>

template <class Range>
void f(const Range& r)
{
    using std::begin;
    using std::end;

    auto first = begin(r);
    auto last = end(r);

    // use first, last...
}

#include <vector>
int main()
{
    std::vector<int> v = {1, 2, 3};
    int ar[] = {4, 5, 6};

    f(v);
    f(ar);
}

これは、標準外で定義されるbegin()／end()関数を考慮するため。

標準外では、begin()／end()メンバ関数を持っていないコンテナのための非メンバ関数版begin()／end()関数が定義される。そのため、これらの非メンバ関数は、名前空間修飾をせず、ADLで呼び出す。

std名前空間のbegin()／end()をusing宣言しているのは、配列版を考慮するため。std::vectorやstd::dequeはstd名前空間で定義されるのでADLでbegin()／end()を呼び出せるが、配列は名前空間に属さないので、ADLで呼び出せない。そのため、配列版のオーバーロードが定義されるstd名前空間だけは、using宣言する必要がある。

2015-01-23

隣接要素を処理するfor_each

C++

稀によく使うので書いた。const版のみ実装した。

実装：

adjacent_for_each.cpp - Gist

template <class InputRange, class BinaryFunction>
void adjacent_for_each(const InputRange& range, BinaryFunction f)
{
    // for ADL
    using std::begin;
    using std::end;
 
    auto first = begin(range);
    auto last = end(range);
 
    if (first == last)
        return;
 
    while (std::next(first) != last) {
        const auto& a = *first;
        ++first;
        const auto& b = *first;
        f(a, b);
    }
}

サンプルコード：

#include <iostream>
#include <vector>
 
int main()
{
    const std::vector<int> v = {1, 2, 3};
 
    adjacent_for_each(v, [](int a, int b) {
        std::cout << a << " : " << b << std::endl;
    });
}

出力：

1 : 2
2 : 3

参照

adjacent_zipped

2015-01-14

shared_ptrをweak_ptrに変換するヘルパ関数

C++

実装： shand/to_weak.hpp - GitHub

// shand/to_weak.hpp
#include <boost/config.hpp>
#include <memory>

namespace shand {

template <class T>
std::weak_ptr<T> to_weak(const std::shared_ptr<T>& sp) BOOST_NOEXCEPT
{
    return sp;
}

C++14から入った、ラムダ式のキャプチャでの初期化で使用する。

#include <iostream>
#include <memory>
#include <shand/to_weak.hpp>

int main()
{
    std::shared_ptr<int> sp(new int(3));

    auto f = [wp = shand::to_weak(sp)] { // これ
        if (std::shared_ptr<int> sp = wp.lock()) {
            std::cout << *sp << std::endl;
        }
    };

    f();
}

出力：

2014-12-26

正規分布の代わりに区間線形分布を使うのもいいかも

中央値(平均値)から、最小値と最大値に向けて左右対称で線形に出現確率が低くなるようなものには、std::piecewise_linear_distributionを使うのがよさそう。

std::normal_distributionは、与えるパラメータが平均値と標準偏差で、「平均値 ± 標準偏差」を超える値も出現するから、その外れ値を望まない場合に、std::piecewise_linear_distributionで代用できそう。

これは、正規分布がほしい、という状況ではなく、中央値付近の値がほしい、という状況です。

#include <random>
#include <array>
#include <fstream>

int main()
{
    std::random_device seed_gen;
    std::mt19937 engine(seed_gen());

    std::array<double, 3>
        intervals = {-1.0, 0.0, 1.0},
        densities = { 0.0, 1.0, 0.0};

    std::piecewise_linear_distribution<double> dist {
        intervals.begin(),
        intervals.end(),
        densities.begin()
    };

    std::ofstream file("dist.tsv");
    for (std::size_t n = 0; n < 1000 * 1000; ++n) {
        double result = dist(engine);
        file << result << "\n";
    }
}

f:id:faith_and_brave:20141226140153p:plain

参照

piecewise_linear_distribution - cpprefjp

2014-12-25

GCC 5.0のC++関係機能

C++ GCC

https://gcc.gnu.org/gcc-5/changes.html

網羅的ではなく、気になったものだけ抽出して書いています。

C++11、C++14関係の対応状況は、cpprefjpサイトにもほぼ反映しました。

C++14を全実装
- 変数テンプレート
- 宣言時のメンバ初期化を持つ型の集成体初期化を許可
- constexprの制限緩和
- サイズ付きデアロケーション
-std=c++14オプションが使えるようになる。旧-std=c++1yオプションは非推奨。
C++11周りのライブラリサポート改善
- std::listのsize()メンバ関数が、デフォルトでO(1)になる
- std::dequeとstd::vector<bool>に、ステートフルアロケータのサポートを追加。
- iostreamのクラスに、ムーブとswapのサポートを追加。
- std::alignとstd::aligned_unionのサポートを追加。
- is_trivially_*系の型特性を追加。
- IOマニピュレータのput_time、hexfloat、defaultfloatのサポートを追加。
- std::isblankをジェネリックなロケールで使えるようになった。
- std::shared_ptrのアトミック操作をサポート。
- std::notify_all_at_thread_exit()系の、スレッド終了時にfutureを準備完了状態にする機能をサポート。
C++14ライブラリ
- is_final型特性を実装
C++14後のLibrary Fundamentals TSの機能を追加。std::experimental名前空間で定義される。
- anyクラス(boost::anyと同じ)
- apply関数(タプルを展開して関数実行)
- sample関数(コンテナからN個の要素をランダム選択)
- search関数(文字列特化した探索アルゴリズム)
- 変数テンプレートの型特性をいくつか
- not_fn関数(not1とnot2を統合し、改善したもの)
新しい警告オプションとして、-Wsuggest-final-typesが入る。「このクラスにはfinalを付けたほうがいいよ」とオススメしてくれる。
拡張機能として、乱数の分布クラスlogistic_distribution(ロジスティック分布)とuniform_on_sphere_distribution(球状の一様分布、Boost.Randomにある)を追加。
IntelのCilk Plusをフルサポート。並列関係の新しい言語拡張。
Clangにもある__has_includeをサポート。ヘッダファイルがあるかどうかを調べられる。

2014-12-11

STLのイテレータインタフェース再考

C++

STLのイテレータは、コンテナとアルゴリズムをつなぐ中間インタフェース。STLではそのイテレータ自体のインタフェースとして、ポインタの構文を採用している。

ここではそのポインタの構文を、好んで使いたい構文ではないものとし、演算子ではなく名前のついた関数によるインタフェースで、イテレータを再設計してみる。

コード全体は以下を参照：

faithandbrave / modern_stl_iterator_interface_2014.cpp - Gist

新しいイテレータインタフェースによるアルゴリズムの実装

まず、新しいイテレータインタフェースを使用しているところ、すなわちアルゴリズムの中身から見てみる。

namespace my_stl {
…
template <class Iterator, class F>
void for_each(Iterator first, Iterator last, F f)
{
    using traits = my_stl::iterator_traits<Iterator>;
 
    // no use raw pointer interface
    Iterator it = first;
    while (!traits::equal(it, last)) {
        f(traits::dereference(it));
        it = traits::next(it);
    }
}

} // namespace my_stl

ここでは、iterator_traitsというクラスが、イテレータのインタフェースとなっている(標準ライブラリに同名のクラスがあるが、それとは別物)。

このクラスは、以下の静的メンバ関数で、イテレータを操作する：

関数	説明
`dereference()`	イテレータが指している要素を間接参照する
`next()`	イテレータをひとつ進める
`equal()`	2つのイテレータを等値比較する

これらは、STLのイテレータインタフェースとしてはそれぞれ、operator*()、operator++()、operator==()に相当する。

イテレータインタフェースの実装

このイテレータは、これらのメンバ名前による操作を直接サポートするイテレータクラスのみならず、従来のSTLと同様に、ポインタもサポートする。iterator_traitsクラスの実装は以下のようになっている：

namespace my_stl {
 
template <class Iterator>
struct iterator_traits {
    static typename Iterator::reference dereference(Iterator& it)
    {
        return it.dereference();
    }
 
    static Iterator next(const Iterator& it)
    {
        return it.next();
    }
 
    static bool equal(const Iterator& a, const Iterator& b)
    {
        return a.equal(b);
    }
};
 
template <class T>
struct iterator_traits<T*> {
    static T& dereference(T* it)
    {
        return *it;
    }
 
    static T* next(T* it)
    {
        return ++it;
    }
 
    static bool equal(const T* a, const T* b)
    {
        return a == b;
    }
};

} // namespace my_stl

iterator_traitsは、デフォルト実装としてのインタフェースのほかに、ポインタに対する特殊化を行っている。これによって、ポインタもイテレータとして振る舞えるようにしてある。

また、これと同じように、自分が使っているコンテナのイテレータが、デフォルトのインタフェースを持っておらず、ポインタでもない場合は、iterator_traitsクラスを特殊化してアダプトすれば、そのイテレータもまたアルゴリズムに適用可能になる。

今回用意したコンテナクラスは、singly_linked_listという名前の単方向リンクリスト。このコンテナクラスには、デフォルト実装の、dereference()、next()、equal()というメンバ関数を持つイテレータを持たせている。

ユーザーコード

コンテナとイテレータの実装は簡単なものなので省略して、コンテナと配列(ポインタ)をアルゴリズムに適用できているところを確認する。

#include <iostream>
int main()
{
    my_stl::singly_linked_list<int> ls;
    ls.push_front(3);
    ls.push_front(2);
    ls.push_front(1);
 
    my_stl::for_each(ls.begin(), ls.end(), [](int& x) {
        std::cout << x << std::endl;
    });
 
    int ar[3] = {4, 5, 6};
    my_stl::for_each(ar, ar + 3, [](int& x) {
        std::cout << x << std::endl;
    });
}

出力：

まとめ

ここでは、STLの「ポインタもイテレータとして振る舞えるようにする」という設計方針を維持したまま、イテレータのインタフェースを見直してみた。近年、データ構造とアルゴリズムをつなぐ中間インタフェースを用意するライブラリが増えてきた。Boost.Graph、Boost.Geometryなどが参考になる。これらのライブラリによって、中間インタフェースの設計がさらに洗練されたので、それを大元であるSTLの設計に適用した、というのが今回の試みだ。

Rangeが出てくると話はまた違ってくるのだが、いまイテレータを再設計するならこうなる、というのを示してみた。