読者です 読者をやめる 読者になる 読者になる

Boost.Multi-index ランク付きインデックス

C++

Boost 1.59.0から、Boost.Multi-indexに、ranked indiciesというのが入ります。

これは、キーが何番目に大きいかを対数時間で取得できる、連想配列のインデックスです。

イメージとしては、mapに対してit = m.find(key)をして得たイテレータに、distance(m.begin(), it)としてイテレータの位置を求めるのが、容易になるという感じです。

#include <iostream>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ranked_index.hpp>
#include <boost/multi_index/member.hpp>

struct Person {
    int age = 0;
    std::string name;

    Person() {}
    Person(int age, const std::string& name)
        : age(age), name(name) {}
};

using namespace boost::multi_index;
using Container = boost::multi_index_container<
    Person,
    indexed_by<
        ranked_non_unique<member<Person, int, &Person::age>>
    >
>;

int main()
{
    Container c;

    c.emplace(3, "Alice");
    c.emplace(1, "Bob");
    c.emplace(4, "Carol");

    // キー値2を持つ要素が、何番目に大きいかを取得する
    auto it = c.emplace(2, "Hoge").first;
    std::size_t n = c.rank(it);
    std::cout << n << std::endl; // 1

    // キー値4の要素が、何番目に大きいかを取得する
    std::cout << c.find_rank(4) << std::endl; // 3

    // 最後尾にある要素へのイテレータを取得する
    std::cout << c.nth(c.size() - 1)->name << std::endl; // Carol
}

ランク用インタフェースのほかに、mapと同じくイテレータを扱うfind()lower_bound()のインタフェースも持っています。

Boost 1.59.0のリリースノート翻訳をはじめました

C++

いつものように、boostjpサイトで、リリースノートの翻訳をやっています。

Boost.勉強会 #17 東京を開催しました

C++

発表資料は、上記ページにまとめてあります。

東京での開催は、1年2ヶ月ぶりとなりました。最近だいぶ気持ちが落ち込んでいて、当日の朝まで非常に憂鬱な状態だったのですが、参加者のみなさんの熱気で、おかげさまで回復できました。

またネタがたまってきた頃にでも開催しますので、何か発表ネタがある方は「今度こういう発表したい」のような連絡をいただけると、開催しやすいです。

C++14対応のC++ポケットリファレンス 第2版

おかげさまでご好評いただいております書籍『C++ポケットリファレンス』ですが、この度、C++規格の最新バージョンC++14(ISO/IEC 14882:2014)に対応した改訂版を出版します。

基本文法、ライブラリの各章において、C++14で追加された機能の解説を加筆しました。

また、それ以外の項目についても、解説の加筆や改善を行っています。

ページ数も16ページほど増量し、544ページになっています。そろそろポケットに収納するのは厳しいかもしれません。

コンパイラC++14への対応も非常に早いので、より多くの方にC++14の機能を使っていただければ幸いです。

C++ポケットリファレンス』第2版は、2015年6月4日に発売予定です。電子書籍版は、技術評論社Digital Publishingサイトで販売を予定しています。

追記

PDF版はこちらです:

gihyo.jp

Boost.勉強会 #17 東京の募集を開始しました

C++

2015/05/30(土)に、Boost.勉強会 東京を開催します!

Boost 1.58.0がリリースされました

C++

いつものように、boostjpサイトで、リリースノートの日本語訳を作成して公開しています。

新ライブラリ

今回の新ライブラリは、以下の2つです。

  • Endian
    • プロセッサのエンディアンに関係なく、適切なバイトオーダーに変換する型と関数。
  • Sort
    • 一般的な状況でO(n*log(n))よりも高速な、ハイブリッドな基数ソートであるスプレッドソート(spreadsort)を含む。

主な更新内容

更新はたくさんありますが、目立ったところをいくつか列挙します。

  • Boost.Fusionのstd::tupleアダプトが正式サポートになった
    • Flastさんががんばってpull requestを送りまくってくれました。お疲れさまでした。
  • Boost.Variantのapply_visitor()関数に、ジェネリックラムダを指定できるようになった。
    • C++14サポートです。
  • Boost.Geometryの、disjoint()intersects()がサポートする組み合わせが増えた
  • Boost.Containerに、small_vectorというコンテナが追加された
    • 小さな要素数に最適化されたvector。テンプレートパラメータで指定された要素数の領域を事前に確保することにより、その要素数を超えない限り、insert()push_back()でメモリ確保を行わない。
    • static_vectorとは異なり、フリーストアからメモリ確保し、キャパシティを超えた領域の拡張が可能。
    • LLVMのSmallVectorクラスを参考にしている
  • Boost.Containerのランダムアクセスイテレータをサポートするコンテナに、nth()index_of()メンバ関数が追加された。

Boost.Graph Graphvizの情報をユーザー定義型に読み込む

C++

Boost.Graphのadjacency_listクラスには、Bundleプロパティという仕組みを使って、頂点や辺の情報を、任意のユーザー定義型に保持できます。

そのような作りになっているグラフオブジェクトに、Graphvizのデータを読み込むサンプルコードを、以下の示します。

読み込むGraphvizデータ(graph.dot)

digraph G {
0 [name="A", pos="(0,0)", id=1];
1 [name="B", pos="(-3,3)"];
2 [name="C", pos="(3,3)"];
3 [name="D", pos="(0,6)"];

0->1;
0->2;
1->3;
2->3;
}

このデータを読み込むコード:

#define BOOST_GRAPH_USE_SPIRIT_PARSER // for header only
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/optional.hpp>
#include <fstream>
#include <iostream>

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

std::ostream& operator<<(std::ostream& os, const Point& p)
{
    return os << '(' << p.x << ',' << p.y << ')';
}

std::istream& operator>>(std::istream& is, Point& p)
{
    if (is.get() != '(') {
        is.setstate(std::ios_base::failbit);
        return is;
    }

    is >> p.x;
    if (!is) {
        is.setstate(std::ios_base::failbit);
        return is;
    }

    if (is.get() != ',') {
        is.setstate(std::ios_base::failbit);
        return is;
    }

    is >> p.y;
    if (!is) {
        is.setstate(std::ios_base::failbit);
        return is;
    }

    if (is.get() != ')') {
        is.setstate(std::ios_base::failbit);
    }
    return is;
}

namespace boost {
    template <class T>
    std::ostream& operator<<(std::ostream& os, const boost::optional<T>& x)
    {
        if (x) {
            os << x.get();
        }
        else {
            os << "";
        }
        return os;
    }

    template <class T>
    std::istream& operator>>(std::istream& is, boost::optional<T>& x)
    {
        T result;
        if (is >> result) {
            x = result;
        }
        return is;
    }
}

struct Vertex {
    int nodeId;
    std::string name;
    boost::optional<int> id;
    Point pos;
};

using Graph = boost::adjacency_list<
    boost::listS,
    boost::vecS,
    boost::directedS,
    Vertex
>;

void load(Graph& g)
{
    boost::dynamic_properties dp;
    dp.property("node_id", boost::get(&Vertex::nodeId, g));
    dp.property("name", boost::get(&Vertex::name, g));
    dp.property("id", boost::get(&Vertex::id, g));
    dp.property("pos", boost::get(&Vertex::pos, g));

    std::ifstream file("graph.dot");
    if (!boost::read_graphviz(file, g, dp)) {
        throw std::runtime_error("can't load graph.dot file.");
    }
}

int main()
{
    Graph g;
    load(g);

    std::cout << "name : " << g[0].name << std::endl;
    std::cout << "pos : " << g[0].pos << std::endl;
}

出力:

name : A
pos : (0,0)

Bundleプロパティに設定されたユーザー定義型と、Graphvizの情報をマッピングするには、boost::dynamic_propertiesクラスを使用します。ここに、属性名と、それに相当するBundleプロパティのメンバ変数を列挙していきます。

ここでは、Graphvizの頂点データに含まれる、以下の情報を読み込んでいます:

  • ノードID (頂点ID)
    • これは、0, 1, 2, 3といった頂点のIDにあたります。"node_id"という名前で、このIDを読み込めます。このIDがいらない場合は、読み込まなくてもいいです。
  • 頂点の名前
    • nameという名前に設定された属性は、std::string型のメンバ変数に読み込んでいます。
  • ID
    • 頂点に、ノードID以外の任意のIDを持たせています。これは省略可能な要素とし、boost::optional<int>型に読み込んでいます。そのための入出力ストリーム演算子を用意してあります。
  • 頂点の表示位置
    • 表示位置は、ユーザー定義型のPoint型に読み込んでいます。これは、(x,y)という形式で書いています。

頂点や辺の各属性を読み込む際には、その型の入力ストリーム演算子が呼ばれます。ここで、任意のフォーマットになっているユーザー定義型のデータを読み込めます。

boost::optionalの読み込みについては、公式の入出力ストリームとはフォーマットが異なることに注意です。ここでは、その属性を読み込めなかった場合に無効な状態、読み込めた場合に有効な状態としています。boost::optional公式のフォーマットを使用する場合には、<boost/optional/optional_io.hpp>をインクルードしてください。

optionalに関連して。属性が記載されていない場合には、operator>>は呼ばれず、その型のデフォルト値が設定されます。

C++14標準ライブラリの小さな変更 その8

C++

その1その2その3その4その5その6その7に引き続き、C++14の標準ライブラリに入った小さな変更を紹介していきます。

vectorとdequeの複数要素を挿入する操作の、強すぎる保証を緩和

C++11までこれらの関数は、以下のような保証をしていました。

要素の挿入操作で例外が発生した場合、副作用が発生しない

これはつまり、複数の要素を挿入する際に、後ろの方の要素が、コピーで例外を送出した場合、ここまで成功した挿入もなかったことにする、ということを意味します。これはバックアップ情報を持っておく必要があり、コストが高いこともあって、現実的でない強い保証です。

C++14では、挿入操作で例外が発生した場合には、例外が発生したその単一要素のみ、副作用が発生しない、という保証に変わりました。

コンテナの等値比較に、last2をとるequalアルゴリズムを使用するようになった

C++03およびC++11では、以下と同等の戻り値である、となっていました。

return distance(x.begin(), x.end()) == distance(y.begin(), y.end())
        && equal(x.begin(), x.end(), y.begin());

C++14では、std::equal()アルゴリズムに、last2を受け取るオーバーロードが追加されたので、それを使用します。

return equal(x.begin(), x.end(), y.begin(), y.end());

このlast2を受け取るオーバーロードは、一度の横断で、要素数が等しいかと、それらの要素が等しいかの両方を判定します。

C++11では、コンテナのsize()メンバ関数は、計算量が全てO(1)になったので、実際の実装ではdistance()の代わりにsize()メンバ関数が使用されていたでしょうから、パフォーマンスはとくに変わらないでしょう。

forward_listについては、Cの実装とゼロオーバーヘッドにするという目的があるため、size()メンバ関数を持っていません。そのため、distance()size()メンバ関数で置き換えて使用できなかったので、forward_listはこの変更でパフォオーマンスアップが期待できるでしょう(内部の実装用にlast2を受け取るequal()アルゴリズムを持っていなければ)。

async関数の戻り値の型に、decayを適用するようになった

C++11

namespace std {
  template <class F, class... Args>
  future<typename result_of<F(Args...)>::type>
    async(F&& f, Args&&... args);

  template <class F, class... Args>
  future<typename result_of<F(Args...)>::type>
    async(launch policy, F&& f, Args&&... args);
}

C++14

namespace std {
  template <class F, class... Args>
  future<
    typename result_of<
      typename decay<F>::type(typename decay<Args>::type...)
    >::type
  > async(F&& f, Args&&... args);

  template <class F, class... Args>
  future<
    typename result_of<
      typename decay<F>::type(typename decay<Args>::type...)
    >::type
  > async(launch policy, F&& f, Args&&... args);
}

ios_base::xallocがスレッドセーフになった

C++03

static int index = 0;
return index++;

C++14

static std::atomic<int> index(0);
return index++;

これでおわりにします

まだいくつかありますが、気にする必要のあるものはそれほどないので、このあたりで終わりにします。

さらに詳しく知りたい方は、cpprefjpのC++14対応まとめページからリンクを辿るか、cpprefjp/siteリポジトリのコミットログからC++14対応の歴史を抽出してください。

C++14標準ライブラリの小さな変更 その7

C++

その1その2その3その4その5その6に引き続き、C++14の標準ライブラリに入った小さな変更を紹介していきます。

condition_variableのwait系関数が例外を送出する仕様を変更

C++11までは、ミューテックスの取得関係で例外が送出される可能性があった。

C++14では、ミューテックスの取得関係では、wait系関数は例外を送出しない。その代わりにstd::terminate()関数を呼び出してプログラムが異常終了する。時計、時間演算関係で例外を送出する可能性がある。

tuple_sizeの特殊化が、必ずintegral_constantから派生するようになった

namespace std {
  template <class T> class tuple_size; // 先行宣言

  // C++11
  struct tuple_size<pair<T1, T2>> {
    static constexpr size_t value = 2;
  };

  // C++14
  struct tuple_size<pair<T1, T2>>
    : public integral_constant<size_t, 2> {};
}
namespace std {
  template <class T> class tuple_size; // 先行宣言

  // C++11
  template <class T, size_t N>
  struct tuple_size<array<T, N>> {
    static constexpr size_t value = N;
  };

  // C++14
  template <class T, size_t N>
  struct tuple_size<array<T, N>>
    : integral_constant<size_t, N> {};
}

is_null_pointer型特性を追加

ヌルポインタ型かを判定するis_null_pointer型特性が、<type_traits>に追加されました。

namespace std {
  template <class T> 
  struct is_null_pointer;
}

この型特性は、型Tstd::nullptr_tであればstd::true_typeから派生し、そうでなければstd::false_typeから派生します。

copy_ifに戻り値の仕様を追加

C++11で追加されたアルゴリズムstd::copy_if()ですが、戻り値の仕様が未規定だったので、C++14で以下の仕様が追加されました。

戻り値
コピー先の範囲の終端を返す。

mem_fnの不要なオーバーロードを削除

C++11:

namespace std {
  template<class R, class T> unspecified mem_fn(R T::*);
  template<class R, class T, class... Args>
  unspecified mem_fn(R (T::*)(Args...));
  template<class R, class T, class... Args>
  unspecified mem_fn(R (T::*)(Args...) const);
  template<class R, class T, class... Args>
  unspecified mem_fn(R (T::*)(Args...) volatile);
  template<class R, class T, class... Args>
  unspecified mem_fn(R (T::*)(Args...) const volatile);
  template<class R, class T, class... Args>
  unspecified mem_fn(R (T::*)(Args...) &);
  template<class R, class T, class... Args>
  unspecified mem_fn(R (T::*)(Args...) const &);
  template<class R, class T, class... Args>
  unspecified mem_fn(R (T::*)(Args...) volatile &);
  template<class R, class T, class... Args>
  unspecified mem_fn(R (T::*)(Args...) const volatile &);
  template<class R, class T, class... Args>
  unspecified mem_fn(R (T::*)(Args...) &&);
  template<class R, class T, class... Args>
  unspecified mem_fn(R (T::*)(Args...) const &&);
  template<class R, class T, class... Args>
  unspecified mem_fn(R (T::*)(Args...) volatile &&);
  template<class R, class T, class... Args>
  unspecified mem_fn(R (T::*)(Args...) const volatile &&);
}

C++14:

namespace std {
  template<class R, class T>
  unspecified mem_fn(R T::*);
}

単に冗長なオーバーロードでした。

functionに、異なるシグニチャの関数オブジェクトが代入された際の挙動を追加

以下のオーバーロードについて、

template <class F>
function(F f);

template <class F, class Alloc>
function(allocator_arg_t, const Alloc& alloc, F f);

C++11までは、型Fstd::functionのテンプレートパラメータと同じシグニチャを持つことを「要件」として定義していました。

C++14では、異なるシグニチャの関数オブジェクトが渡された場合、オーバーロード解決の候補から外れます(SFINAEになる)。

こちらもC++14では以下のオーバーロードについて、

template<class F>
function& operator=(F&& f);

異なるシグニチャの関数オブジェクトが渡された場合、オーバーロード解決の候補から外れます。

vector<bool>にemplaceとemplace_backを追加

単に書き忘れです。

cpprefjpにどう書こうか悩んだのですが、暫定的に、std::vectorの各メンバ関数のページに書きました。

template <class... Args>
iterator emplace(const_iterator position, Args&&... args);

template <class... Args>
iterator vector<bool>::emplace(const_iterator position, Args&&... args); // C++14
template <class... Args>
void emplace_back(Args&&... args);

template <class... Args>
void vector<bool>::emplace_back(Args&&... args); // C++14

今日はここまで

ひとまずネタが尽きたのですが、cpprefjp側の対応が進んだらもう少し書きます。

C++14標準ライブラリの小さな変更 その6

C++

その1その2その3その4その5に引き続き、C++14の標準ライブラリに入った小さな変更を紹介していきます。

unique_ptr::reset(nullptr_t)の仕様を追加

配列版std::unique_ptr<T[]>クラスの、nullptrを受け取るreset()メンバ関数の仕様が、これまで未規定でした。C++14で、以下の仕様が規定されました。

reset(pointer())と同等の効果を持つ。

つまり、p.reset()するのと同じです。

allocator_traits::max_sizeのパラメータにconstを追加

単なる付け忘れです。

static size_type max_size(Alloc& a);                // C++11
static size_type max_size(const Alloc& a) noexcept; // C++14

is_signedとis_unsignedの符号判定の条件式を修正

C++11のstd::is_signedでは、以下の条件式で、算術型であることとその符号あるなしを判定していました。

is_arithmetic<T>::value && T(-1) < T(0)

しかし、算術型以外が渡された場合、T(-1) < T(0)という式でテンプレートの置き換え失敗が発生してしまうので、C++14で以下のように修正されました。

is_arithmetic<T>::value == trueの場合、integral_constant<bool, T(-1) < T(0)>::valueの
結果を真偽の結果とする。そうでなければ偽の結果とする。

std::is_unsignedも同様です。

is_destructibleに、オブジェクト型以外が渡された場合の仕様を追加

std::is_destructibleは、C++11では以下のようにして破棄可能であると判定していました。

型Tが完全型で
template <class U>
struct test { U u; };
があるときに test<T>::~test() がdelete宣言されていなければ、
型Tは破棄可能であると判断される。

この仕様では、オブジェクト型以外に対しては、未規定となっています。

C++14で、以下のように修正されました。

実行時に評価されない文脈で、オブジェクト型Tに対する式std::declval<T&>().~T()が有効であれば破棄可能、
そうでなければ破棄できないと判断される。

以下、オブジェクト型に含まれない型の場合の判断について記載する:
・Tがvoidの場合は破棄できない
・Tが参照型の場合は破棄可能
・Tが関数型の場合は破棄できない

今日はここまで

まだ続きます。