狠狠撸

狠狠撸Share a Scribd company logo

Brief introduction of Boost.ICL [PDF]

?
?
Y
yak1ex

Not yet presented anywhere. Uploaded via PDF, thus layout is nearer from original but without notes

1 of 15
Download to read offline
绍介 詳解 ICL (Interval Container Library) 2011/2/26 Boost 勉強会 #4 未発表 @yak_ex / 新 康孝
自己绍介 ? 氏名： 新 康孝 (あたらし やすたか) ? Twitter ID: yak_ex ? Web: http://yak3.myhome.cx:8080/junks ? C++ / Perl が主戦場 ? 現在、仕事でコードに触れていないので 競技プログラミング（TopCoder、Codeforces）で 潤い補充 ? 闇の軍団に憧れるただの C++ 好き – 今回は ICL のさわりだけ、というかさわりしか分からない
ぼくのかんがえた「ぶーすと」のぶんるい アプリより 小規模 大規模 実装より
ぼくのかんがえた「ぶーすと」のぶんるい アプリより ～1.25 test graph progress_display た んはココ thread 小規模 大規模 crc pool regex tokenizer lexical_cast random function array timer rational iteratorstype_traits any operators tuple 実装より
ぼくのかんがえた「ぶーすと」のぶんるい 異次元 アプリより ～1.30 preprocessor test spirit date_time graph filesystem progress_display た んはココ thread 小規模 format 大規模 crc pool regex tokenizer lexical_cast random function array lambda timer rational multi_array iteratorstype_traits any optional mpl tuple 実装より
ぼくのかんがえた「ぶーすと」のぶんるい 異次元 アプリより ～1.35 preprocessor test asio wave gil spirit date_time graph filesystem progress_display た statechart thread んはココ serialization 小規模 format program_options interprocess 大規模 crc pool regex tokenizer xpressive lexical_cast random bimap function multi_index array parameter lambda intrusive variant ptr_container range fusion timer rational foreach multi_array iteratorstype_traits any optional typeof mpl tuple 実装より
ぼくのかんがえた「ぶーすと」のぶんるい 異次元 アプリより ～1.40 preprocessor test asio wave accmulators gil spirit date_time graph filesystem progress_display た statechart thread んはココ serialization 小規模 format program_options proto interprocess 大規模 crc pool regex tokenizer xpressive lexical_cast random scope_exit bimap function unordered multi_index array parameter lambda flyweight intrusive variant ptr_container range fusion timer rational foreach multi_array iteratorstype_traits any optional typeof mpl tuple 実装より
ぼくのかんがえた「ぶーすと」のぶんるい 異次元 アプリより ～1.45 preprocessor test asio wave accmulators gil spirit date_time graph filesystem property_tree polygon progress_display た msm statechart thread んはココ serialization 小規模 uuid format program_options proto interprocess 大規模 crc pool regex tokenizer xpressive lexical_cast random scope_exit bimap function unordered multi_index array parameter lambda flyweight intrusive variant ptr_container range fusion timer rational foreach multi_array iteratorstype_traits any optional typeof mpl tuple 実装より
ぼくのかんがえた「ぶーすと」のぶんるい 異次元 アプリより ～1.46 preprocessor test asio wave accmulators gil spirit date_time graph filesystem property_tree ICL polygon progress_display た msm statechart thread んはココ serialization 小規模 uuid format program_options proto interprocess 大規模 crc pool regex tokenizer xpressive lexical_cast random scope_exit bimap function unordered multi_index array parameter lambda flyweight intrusive variant ptr_container range fusion timer rational foreach multi_array iteratorstype_traits any optional typeof mpl tuple 実装より
ここで競技コーディングのお時間です ? akira さん（仮名）はパーティーを開くことになりました。N 人 のお客さんが参加する予定ですが参加時間帯[si, ti)が皆ば らばらです。場所の予約のために参加人数の最も多い時間 帯を知りたいのでプログラムを作って akira さんを助けてあ げましょう。 – 1 ≦ N ≦ 1000 – -109 ≦ si < ti ≦ 109, si, ti は整数 (i=1,2,…,N) – 参加人数が同じ時間帯が隣接している場合、参加者が異なっていて も一つの時間帯と見なす – 同一参加人数の時間帯が複数ある場合は最長の時間帯を、同じ長 さの時間帯が複数ある場合は開始時刻がもっとも早い時間帯を返す – 入力： N<改行>s1<空白>t1<改行>…sN<空白>tN<改行> – 出力：開始時刻<空白>終了時刻<空白>人数<改行>
解答例全文 using ICL #include <iostream> #include <algorithm> #include <utility> #include 含めて 25 行 #include <boost/icl/interval_map.hpp> int main(void) { boost::icl::interval_map<int, int> sum; int n; std::cin >> n; for(int i = 0; i < n; ++i) { int s, t; std::cin >> s >> t; sum += std::make_pair(boost::icl::interval<int>::right_open(s, t), 1); } typedef boost::icl::interval_map<int, int>::value_type value_type; auto it = max_element(sum.begin(), sum.end(), [](const value_type &v1, const value_type &v2) { return v1.second < v2.second || (v1.second == v2.second && v1.first.upper() - v1.first.lower() < v2.first.upper() - v2.first.lower()) || (v1.second == v2.second && v1.first.upper() - v1.first.lower() == v2.first.upper() - v2.first.lower() && v1.first.lower() < v2.first.lower()); }); std::cout << it->first.lower() << ' ' << it->first.upper() << ' ' << it->second << std::endl; return 0; }
解答例全文 using ICL #include <iostream> #include <algorithm> ヘッダのインクルード #include <utility> #include <boost/icl/interval_map.hpp> int main(void) { boost::icl::interval_map<int, int> sum; int n; std::cin >> n; for(int i = 0; i < n; ++i) { int s, t; 入力と登録 std::cin >> s >> t; sum += std::make_pair(boost::icl::interval<int>::right_open(s, t), 1); } typedef boost::icl::interval_map<int, int>::value_type value_type; 最大値取得 auto it = max_element(sum.begin(), sum.end(), [](const value_type &v1, const value_type &v2) { return v1.second < v2.second || (v1.second == v2.second && v1.first.upper() - v1.first.lower() < v2.first.upper() - v2.first.lower()) || (v1.second == v2.second && v1.first.upper() - v1.first.lower() == v2.first.upper() - v2.first.lower() && v1.first.lower() < v2.first.lower()); }); std::cout << it->first.lower() << ' ' << it->first.upper() << ' ' << it->second << std::endl; return 0; 出力 }
解答例 入力と登録 boost::icl::interval_map<int, int> sum; int n; std::cin >> n; for(int i = 0; i < n; ++i) { 今回は数だが集合も可能 int s, t; std::cin >> s >> t; 右開区間 [s, t) sum += std::make_pair(boost::icl::interval<int>::right_open(s, t), 1); } 1 1 + + 1 1 split_interval_map interval_map 1 2 1 1 1 1
解答例 最大値取得 typedef boost::icl::interval_map<int, int>::value_type value_type; auto it = max_element(sum.begin(), sum.end(), [](const value_type &v1, const value_type &v2) { return v1.second < v2.second || // 集計値は second (v1.second == v2.second && // 区間は first (upper(), lower() で境界値) v1.first.upper() - v1.first.lower() < v2.first.upper() - v2.first.lower()) || (v1.second == v2.second && v1.first.upper() - v1.first.lower() == v2.first.upper() - v2.first.lower() && v1.first.lower() < v2.first.lower()); }); 集計された区間の結果を iteration 可能なので普通に max_element で最大値取得
Interval Container Library ? 1.46 で導入 ? 開区間、閉区間等全部取り扱い可能 ? 区間に対する集合演算、「集計」が可能 ? interval_set, interval_map interval_set a interval_set b interval_set a - b ? 区間の統合方法として join, separate, split を選択可能 ? ストリーム出力有り（例：{(1,3][4.6](7,8]}） ? Traits 用意すれば自前の interval を突っ込むことも可能 ? 数値に限定されないので例えば cotinuous_interval<std::string> w(“a”, “c”) // right_open とか書くと a, b で始まる文字列全部を表すことになる。 ? Example がいっぱいなのでそれ見ればOK

More Related Content

Brief introduction of Boost.ICL [PDF]

  • 1. 绍介 詳解 ICL (Interval Container Library) 2011/2/26 Boost 勉強会 #4 未発表 @yak_ex / 新 康孝
  • 2. 自己绍介 ? 氏名： 新 康孝 (あたらし やすたか) ? Twitter ID: yak_ex ? Web: http://yak3.myhome.cx:8080/junks ? C++ / Perl が主戦場 ? 現在、仕事でコードに触れていないので 競技プログラミング（TopCoder、Codeforces）で 潤い補充 ? 闇の軍団に憧れるただの C++ 好き – 今回は ICL のさわりだけ、というかさわりしか分からない
  • 3. ぼくのかんがえた「ぶーすと」のぶんるい アプリより 小規模 大規模 実装より
  • 4. ぼくのかんがえた「ぶーすと」のぶんるい アプリより ～1.25 test graph progress_display た んはココ thread 小規模 大規模 crc pool regex tokenizer lexical_cast random function array timer rational iteratorstype_traits any operators tuple 実装より
  • 5. ぼくのかんがえた「ぶーすと」のぶんるい 異次元 アプリより ～1.30 preprocessor test spirit date_time graph filesystem progress_display た んはココ thread 小規模 format 大規模 crc pool regex tokenizer lexical_cast random function array lambda timer rational multi_array iteratorstype_traits any optional mpl tuple 実装より
  • 6. ぼくのかんがえた「ぶーすと」のぶんるい 異次元 アプリより ～1.35 preprocessor test asio wave gil spirit date_time graph filesystem progress_display た statechart thread んはココ serialization 小規模 format program_options interprocess 大規模 crc pool regex tokenizer xpressive lexical_cast random bimap function multi_index array parameter lambda intrusive variant ptr_container range fusion timer rational foreach multi_array iteratorstype_traits any optional typeof mpl tuple 実装より
  • 7. ぼくのかんがえた「ぶーすと」のぶんるい 異次元 アプリより ～1.40 preprocessor test asio wave accmulators gil spirit date_time graph filesystem progress_display た statechart thread んはココ serialization 小規模 format program_options proto interprocess 大規模 crc pool regex tokenizer xpressive lexical_cast random scope_exit bimap function unordered multi_index array parameter lambda flyweight intrusive variant ptr_container range fusion timer rational foreach multi_array iteratorstype_traits any optional typeof mpl tuple 実装より
  • 8. ぼくのかんがえた「ぶーすと」のぶんるい 異次元 アプリより ～1.45 preprocessor test asio wave accmulators gil spirit date_time graph filesystem property_tree polygon progress_display た msm statechart thread んはココ serialization 小規模 uuid format program_options proto interprocess 大規模 crc pool regex tokenizer xpressive lexical_cast random scope_exit bimap function unordered multi_index array parameter lambda flyweight intrusive variant ptr_container range fusion timer rational foreach multi_array iteratorstype_traits any optional typeof mpl tuple 実装より
  • 9. ぼくのかんがえた「ぶーすと」のぶんるい 異次元 アプリより ～1.46 preprocessor test asio wave accmulators gil spirit date_time graph filesystem property_tree ICL polygon progress_display た msm statechart thread んはココ serialization 小規模 uuid format program_options proto interprocess 大規模 crc pool regex tokenizer xpressive lexical_cast random scope_exit bimap function unordered multi_index array parameter lambda flyweight intrusive variant ptr_container range fusion timer rational foreach multi_array iteratorstype_traits any optional typeof mpl tuple 実装より
  • 10. ここで競技コーディングのお時間です ? akira さん（仮名）はパーティーを開くことになりました。N 人 のお客さんが参加する予定ですが参加時間帯[si, ti)が皆ば らばらです。場所の予約のために参加人数の最も多い時間 帯を知りたいのでプログラムを作って akira さんを助けてあ げましょう。 – 1 ≦ N ≦ 1000 – -109 ≦ si < ti ≦ 109, si, ti は整数 (i=1,2,…,N) – 参加人数が同じ時間帯が隣接している場合、参加者が異なっていて も一つの時間帯と見なす – 同一参加人数の時間帯が複数ある場合は最長の時間帯を、同じ長 さの時間帯が複数ある場合は開始時刻がもっとも早い時間帯を返す – 入力： N<改行>s1<空白>t1<改行>…sN<空白>tN<改行> – 出力：開始時刻<空白>終了時刻<空白>人数<改行>
  • 11. 解答例全文 using ICL #include <iostream> #include <algorithm> #include <utility> #include 含めて 25 行 #include <boost/icl/interval_map.hpp> int main(void) { boost::icl::interval_map<int, int> sum; int n; std::cin >> n; for(int i = 0; i < n; ++i) { int s, t; std::cin >> s >> t; sum += std::make_pair(boost::icl::interval<int>::right_open(s, t), 1); } typedef boost::icl::interval_map<int, int>::value_type value_type; auto it = max_element(sum.begin(), sum.end(), [](const value_type &v1, const value_type &v2) { return v1.second < v2.second || (v1.second == v2.second && v1.first.upper() - v1.first.lower() < v2.first.upper() - v2.first.lower()) || (v1.second == v2.second && v1.first.upper() - v1.first.lower() == v2.first.upper() - v2.first.lower() && v1.first.lower() < v2.first.lower()); }); std::cout << it->first.lower() << ' ' << it->first.upper() << ' ' << it->second << std::endl; return 0; }
  • 12. 解答例全文 using ICL #include <iostream> #include <algorithm> ヘッダのインクルード #include <utility> #include <boost/icl/interval_map.hpp> int main(void) { boost::icl::interval_map<int, int> sum; int n; std::cin >> n; for(int i = 0; i < n; ++i) { int s, t; 入力と登録 std::cin >> s >> t; sum += std::make_pair(boost::icl::interval<int>::right_open(s, t), 1); } typedef boost::icl::interval_map<int, int>::value_type value_type; 最大値取得 auto it = max_element(sum.begin(), sum.end(), [](const value_type &v1, const value_type &v2) { return v1.second < v2.second || (v1.second == v2.second && v1.first.upper() - v1.first.lower() < v2.first.upper() - v2.first.lower()) || (v1.second == v2.second && v1.first.upper() - v1.first.lower() == v2.first.upper() - v2.first.lower() && v1.first.lower() < v2.first.lower()); }); std::cout << it->first.lower() << ' ' << it->first.upper() << ' ' << it->second << std::endl; return 0; 出力 }
  • 13. 解答例 入力と登録 boost::icl::interval_map<int, int> sum; int n; std::cin >> n; for(int i = 0; i < n; ++i) { 今回は数だが集合も可能 int s, t; std::cin >> s >> t; 右開区間 [s, t) sum += std::make_pair(boost::icl::interval<int>::right_open(s, t), 1); } 1 1 + + 1 1 split_interval_map interval_map 1 2 1 1 1 1
  • 14. 解答例 最大値取得 typedef boost::icl::interval_map<int, int>::value_type value_type; auto it = max_element(sum.begin(), sum.end(), [](const value_type &v1, const value_type &v2) { return v1.second < v2.second || // 集計値は second (v1.second == v2.second && // 区間は first (upper(), lower() で境界値) v1.first.upper() - v1.first.lower() < v2.first.upper() - v2.first.lower()) || (v1.second == v2.second && v1.first.upper() - v1.first.lower() == v2.first.upper() - v2.first.lower() && v1.first.lower() < v2.first.lower()); }); 集計された区間の結果を iteration 可能なので普通に max_element で最大値取得
  • 15. Interval Container Library ? 1.46 で導入 ? 開区間、閉区間等全部取り扱い可能 ? 区間に対する集合演算、「集計」が可能 ? interval_set, interval_map interval_set a interval_set b interval_set a - b ? 区間の統合方法として join, separate, split を選択可能 ? ストリーム出力有り（例：{(1,3][4.6](7,8]}） ? Traits 用意すれば自前の interval を突っ込むことも可能 ? 数値に限定されないので例えば cotinuous_interval<std::string> w(“a”, “c”) // right_open とか書くと a, b で始まる文字列全部を表すことになる。 ? Example がいっぱいなのでそれ見ればOK