Boost.Random ジェネレータの状態を保存・復旧する - Faith and Brave - C++で遊ぼう
Boost.RandomやC++標準の乱数ジェネレータは、シードと乱数生成された回数さえ覚えておけば、状態を復旧できます。 乱数生成は分布クラス内部で行われるので、そういうことがしたい場合は、分布処理内での乱数生成回数を覚えておくために、ジェネレータをラップして乱数が生成される度にカウントアップするクラスを用意する必要があります。 #include <iostream> #include <boost/random.hpp> class logged_generator { std::size_t& generate_count_; boost::random::mt19937& gen_; public: typedef boost::random::mt19937 engine_type; typedef engine_type::result_type result_type; lo
Boost.Math 円周率は何桁でもいけた - Faith and Brave - C++で遊ぼう
Boost.Mathにある円周率を求める関数boost::math::constants::pi()ですが、単に定数を型Tにキャストして返すだけの実装だと思っていたら、実は違ったようです。定数で表現できる以上の桁数を要求された場合は、「ldexp(acos(T(0)), 1)」で計算するようになっていました(boost/math/constants/caluculate_constants.hpp)。 まず、組み込みの浮動小数点数型。これは単に定数が返されます。 #include <iostream> #include <boost/math/constants/constants.hpp> #include <boost/multiprecision/cpp_dec_float.hpp> namespace mp = boost::multiprecision; using boost:
Boost.Multiprecision ビット数指定の乱数生成 - Faith and Brave - C++で遊ぼう
Boost.Multiprecisionには、無限長の多倍長整数のために、ビット数指定の擬似乱数を生成するindependent_bits_engineクラスが定義されています。 以下は、256ビット範囲の整数を生成する例です。 #include <iostream> #include <boost/multiprecision/cpp_int.hpp> #include <boost/multiprecision/random.hpp> namespace mp = boost::multiprecision; int main() { // 256ビットの乱数を生成する using engine = boost::random::independent_bits_engine<boost::mt19937, 256, mp::cpp_int>; engine gen; for (int
Boost.Geometry touches - Faith and Brave - C++で遊ぼう
Boost 1.50.0になり、Boost.Geometryにtouches()アルゴリズムが追加されました。 この関数は、自身もしくは2つのジオメトリが空間的に接触しているかを判定するのに使用します。 まず1引数版。自己接触があるかを判定します。 #include <iostream> #include <boost/geometry.hpp> #include <boost/geometry/geometries/point_xy.hpp> #include <boost/geometry/geometries/polygon.hpp> #include <boost/assign/list_of.hpp> namespace bg = boost::geometry; typedef bg::model::d2::point_xy<int> point; typedef bg::mo
Boost.Algorithm clamp - Faith and Brave - C++で遊ぼう
Boost 1.50.0で、Boost Algorithmライブラリが新たに追加されました。これからいくつか紹介していこうと思います。 今回はclamp()です。 clamp()は、最小値と最大値を設定した上で値を渡すと、その範囲内に値を収めてくれる関数です。 意味的には、min(max(minval, x), maxval)と同じになります。 以下の例では、値が0から10の範囲外だったらその範囲に収める、ということをしています。 #include <iostream> #include <boost/algorithm/clamp.hpp> int main() { using boost::algorithm::clamp; int x = 11; x = clamp(x, 0, 10); int y = -1; y = clamp(y, 0, 10); std::cout << x
Boost.Graph 一筆書き - Faith and Brave - C++で遊ぼう
オイラー閉路というのを求めると、グラフの一筆書きの経路を得ることができます。 Boost.Graphにはオイラー閉路のためのアルゴリズムは用意されていないので、以下のページを参考にBoost.Graphベースで書いてみました。 無向オイラー路 - Spaghetti Source 今回一筆書きするのは、「サンタクロースの家」と呼ばれるグラフです。 サンタクロースの家を一筆書きするコード： #include <iostream> #include <deque> #include <string> #include <shand/graph/euler_path.hpp> #include <boost/graph/adjacency_list.hpp> enum {A, B, C, D, E, N}; const std::string name = "ABCDE"; int main()
Boost.Graph 最小全域木を作る - Faith and Brave - C++で遊ぼう
グラフに含まれるすべての頂点を含む最小の部分グラフを、最小全域木(minimum spanning tree)と言います。 Boost.Graphには、最小全域木を作るためのアルゴリズムとして、以下の2つの関数が用意されています。 boost::kruskal_minimum_spanning_tree() : クラスカル法 boost::prim_minimum_spanning_tree() : プリム法 これらを以下のグラフに適用すると 以下のような最小全域木(赤線部分)が手に入ります。 それぞれの使い方は以下のようになります。 boost::kruskal_minimum_spanning_tree() クラスカル法によって最小全域木を求めるboost::kruskal_minimum_spanning_tree()関数は、Output Iteratorで最小全域木の辺記述子(ed
Boost.Graph 最短単純路 - Faith and Brave - C++で遊ぼう
辺に重みのないグラフから最短経路を求めると、「最短単純路」という通過する辺が最も少ない経路が得られます。 Boost.Graphのboost::dijkstra_shortest_paths()は重みのないグラフを与えるとコンパイルエラーになるので、辺の重みを全て1に設定することで代用できます。 #include <iostream> #include <vector> #include <deque> #include <string> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/dijkstra_shortest_paths.hpp> typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, boost::no_
Boost.Graph Bundleプロパティ - Faith and Brave - C++で遊ぼう
Boost.Graphのグラフ構造には、Property Mapによって頂点・辺・グラフに任意のプロパティを持たせることができます。 ただ、プロパティが増えてくると管理しきれなくなってくるので、ひとまとめにしたくなります。 そこで、Boost.GraphにはBundleプロパティという機能が用意されています。これは、グラフ構造のプロパティ指定のところにユーザー定義クラスを指定するという機能です。 以下のサンプルでは、 頂点のBundleプロパティとして「名前」「人口」「郵便番号一覧」を持つCity(街)クラス。 辺のBundleプロパティとして「名前」と「距離」を持つHighway(高速道路)クラス。 グラフのBundleプロパティとして「名前」を持つCountry(国)クラス を設定しています。 そして、最短経路の計算の際に、Highwayクラスのdistanceメンバ変数を辺の重みとし
thread::yield()の実装 - Faith and Brave - C++で遊ぼう
他のスレッドに実行を切り替えるyield()関数ですが、たまたま実装を覗いてみたところ、Boost.ThreadのWindows実装では以下のようになっていました。 // libs/thread/src/win32/thread.cpp void yield() { Sleep(0); } 0秒スリープでした。シンプル。 .NET FrameworkのSystem.Threading.Thread.Yield()メソッドはbool値でスレッドが切り替えられたかどうかを返すようなので、そういうのが必要な場合はどう実装するんだろうと調べてみたら、そういう場合にはSwitchToThread()関数を使えばいいようです。この関数は、準備ができている他のスレッドに切り替えができたらTRUE、そうでなければFALSEを返します。
Boost.Graph トポロジカルソート - Faith and Brave - C++で遊ぼう
閉路を持たない有向グラフ(DAG : Directed Acyclic Graph)に順序を付けるトポロジカルソートのために、Boost.Graphにboost::topological_sort()関数が用意されています。 topological_sort()関数は、グラフに対するconst参照と、結果を返すためのOutput Iteratorを引数にとります。 以下の有向グラフに、トポロジカルソートを適用してみます： #include <iostream> #include <vector> #include <iterator> #include <utility> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/topological_sort.hpp> #include <boost/range/al
Boost.Graph 2つのグラフが同型かを調べる - Faith and Brave - C++で遊ぼう
Boost.Graphには、boost::isomorphism()(アイソモルフィズムと読む)という、2つのグラフが同型かを調べる関数が用意されています。 以下の2つのグラフが同型かどうかを調べてみます。この2つは、頂点の順番等は異なってますが、同じ形のグラフです。 g1: g2: #include <iostream> #include <vector> #include <utility> #include <boost/graph/isomorphism.hpp> #include <boost/graph/adjacency_list.hpp> typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS> Graph; const int vertex_count = 12; Graph
Boost.Math 円周率を取得する - Faith and Brave - C++で遊ぼう
C++標準では、三角関数のためのsin(), cos()関数などは用意されているのに、なぜか円周率を取得するための関数や定数が用意されていません。VC++やGCCはM_PIというマクロを提供していますが、汎用的ではないです。 Boost.Mathには、円周率を取得するためのboost::math::constants::pi()関数が用意されています。Boostが使える環境ならこれを使えばよさそうですね。 #include <iostream> #include <limits> #include <boost/math/constants/constants.hpp> int main () { double pi = boost::math::constants::pi<double>(); std::cout.precision(std::numeric_limits<double>
Boost.Heap 値の更新 - Faith and Brave - C++で遊ぼう
Boost.Heapの特徴の一つとして、「値を変更できる」というのがあります。 キューに一旦登録した値へのハンドルを持っておき、それを使ってupdate()/update_lazy()による更新を行うことができます。 #include <iostream> #include <algorithm> #include <boost/heap/fibonacci_heap.hpp> int main () { boost::heap::fibonacci_heap<int> que; decltype(que)::handle_type h1 = que.push(3); decltype(que)::handle_type h2 = que.push(1); que.push(4); que.update(h1, 6); // すぐに更新 que.update_lazy(h2, 8); //
Boost.Heap iteratorとordered_iterator - Faith and Brave - C++で遊ぼう
Boost.Heapの優先順位付きキューの特徴として、「イテレータを持っている」というのがあります。 さらに、iteratorに加えてordered_iteratorというを持っている優先順位付きキューのバリエーションがあります。 これらの違いを確認しようと思います。 まず、イテレータを使わない場合の操作。pushしてpopしていきます。 この操作では、優先順に処理されます。 #include <iostream> #include <boost/heap/fibonacci_heap.hpp> int main () { boost::heap::fibonacci_heap<int> que; que.push(3); que.push(1); que.push(4); while (!que.empty()) { std::cout << que.top() << std::endl
Boost.Chrono durationの丸め演算 - Faith and Brave - C++で遊ぼう
Boost.Chronoには、duration間の型変換において丸めが発生する場合に明示的に切り捨てを行うためのduration_cast()という関数が用意されていました。 Boost 1.48.0から、従来のduration_cast()に加えて、切り捨てを行うfloor()、最近接偶数への丸めを行うround()(※四捨五入ではない)、切り上げを行うceil()という、3つの関数が追加されました。 #include <iostream> #include <boost/chrono/duration.hpp> #include <boost/chrono/chrono_io.hpp> #include <boost/chrono/floor.hpp> #include <boost/chrono/round.hpp> #include <boost/chrono/ceil.hpp>
Boost.Context アルゴリズムを中断可能にする - Faith and Brave - C++で遊ぼう
既存のアルゴリズム関数の実行を中断可能にしてみました。 対象は、Boost.Graphの最短経路計算アルゴリズムです。 #include <iostream> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/dijkstra_shortest_paths.hpp> #include <boost/assign/list_of.hpp> #include <functional> #include "continuation.hpp" typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, boost::no_property, boost::property<boost::edge_weight_t, int> > G
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://faithandbrave.hateblo.jp/entry/20120510/1336641311
Boost.Contextがucontextのラッパーじゃない理由 - Faith and Brave - C++で遊ぼう
Boostに新しい多倍長演算のライブラリが提出されてる - Faith and Brave - C++で遊ぼう
