Rokiのチラ裏

学生による学習のログ

STL Tutorial and Reference Guide,Second Edition C++ Programming with the Standard Template Library　#4

C++ reading

前回から続く。このエントリーは以下の書籍を参照している。

STL―標準テンプレートライブラリによるC++プログラミング 第2版

STL―標準テンプレートライブラリによるC++プログラミング 第2版

  • 作者: ディビッド・R.マッサー,アトゥルサイニ,ギルマー・J.ダージ,David R. Musser,Atul Saini,Gillmer J. Derge,滝沢徹,牧野祐子
  • 出版社/メーカー: ピアソンエデュケーション
  • 発売日: 2001/12
  • メディア: 単行本
  • 購入: 5人 クリック: 74回
  • この商品を含むブログ (18件) を見る
尚、引用部分を除く各章ごとのサンプルコードは、本書で述べられている内容を基準に私が記述したコードである。またサンプルコードの中では、私が独自的に定義したコード*1を用いている部分がある。コードを確認するには、脚注を参照とのこと。

  • 5.3.12
    transformについて述べられている。 
    #include<algorithm>
#include<experimental/array>
#include<srook/iterator/emplace_back_insert_iterator.hpp>
#include<vector>
#include<numeric>
#include<string>
#include<cassert>
#include<srook/string/make_elements_string.hpp>

int main()
{
    auto ar=std::experimental::make_array(std::vector<int>(10),
            std::vector<int>(10),
            std::vector<int>(10));
    std::vector<std::string> result,result1;

    int i=1;
    std::for_each(std::begin(ar),std::end(ar),[&i](auto& x){
            std::iota(std::begin(x),std::end(x),i);
            i*=10;
            });
    
    std::transform(std::begin(ar.at(0)),std::end(ar.at(0)),srook::emplace_back_inserter(result),
            [](const int x){return std::to_string(x*2);});
    std::transform(std::begin(ar.at(1)),std::end(ar.at(1)),std::begin(ar.at(2)),
            srook::emplace_back_inserter(result1),
            [](const int x,const int y){return std::to_string(x+y);});

    using srook::make_elements_string;
    assert(make_elements_string(result)==make_elements_string(2,4,6,8,10,12,14,16,18,20) &&
            make_elements_string(result1)==make_elements_string(110,112,114,116,118,120,122,124,126,128));
}
  • 5.3.13
    uniqueについて述べられている。 
    #include<vector>
#include<algorithm>
#include<iostream>
#include<cassert>
#include<boost/range/algorithm.hpp>
#include<boost/range/algorithm_ext/iota.hpp>
#include<srook/iterator/emplace_back_insert_iterator.hpp>
#include<srook/string/make_elements_string.hpp>

int main()
{
    std::vector<int> v(3);
    boost::iota(v,0);
    for(std::size_t i=0; i<3; ++i)boost::copy(v,srook::emplace_back_inserter(v));
    boost::sort(v);

    v.erase(std::unique(std::begin(v),std::end(v)),std::end(v));
    assert(srook::make_elements_string(v)==srook::make_elements_string(0,1,2));
}
  • 5.4.1、5.4.2
    ソートに関連した話題を総合的に述べている。5.4.1では、比較関係に対してそれぞれ命名しておりその定義を補足している。
    最初に、実際に必要とされるものより少々厳しい要件について考えてみよう。Rを集合Sに関する二項関係とし、以下の二つの規則に従う場合、RはSに関して厳密な全順序付けであるという。
    • [推移律] Sのx,y,zそれぞれについて、xRyかつyRzであるならば、xRzである。
    • [3分律] Sのx,yそれぞれについて、厳密にxRy、yRx、またはx=yのどれか一つが真(true)である。
    厳密な全順序付けになっている比較関係は、STLソート関連アルゴリズムと一緒に使用することができる。
    述べられているように、厳密な全順序付けの条件はソートされた状態を表す極一般的な内容であると言える。
    しかしSTLは所謂厳密な弱い順序付けと呼ばれる設計をしているとのこと。 
    struct Person{ string last_name,first_name; };
    ここでは、last nameに従ってソートすることだけが必要で、同姓だが名前は違うという人の順序は考慮しないようしよう。その場合、処理を行うには、まずの次のように定義することができる。 
    struct LastNameLess{
bool operator()(const Person& p,const Person& q)const
{
  return p.last_name<q.last_name;
}
};
    それから、例えば次のようにしてdequedeque1のソートを行う。 
    sort(deque1.begin(),deque1.end(),LastNameLess());
    これでうまくいくのは、先ほどの説明から導けたわけではなく、LastNameLess()の定義している関数Rが、厳密な全順序付けではないからである。ある人々（同姓の）に関しては、順序を強制できないのである。
    要件が全ての要素の順序を決定できるほど強くは無いという意味合いとして厳密な弱い順序付けと命名されており、それはoperator()をオーバーロードしたその実装に依存するということである。
  • 5.4.3
    三つのソートアルゴリズム、sort、stable_sort、partial_sortの設計思想やコンセプトが述べられている。 
    #include<srook/string/make_elements_string.hpp>
#include<vector>
#include<cassert>
#include<random>
#include<boost/range/algorithm_ext/iota.hpp>
#include<srook/algorithm/emplace_backer.hpp>

int main()
{
    using namespace std::string_literals;

    std::vector<int> v(10);
    boost::iota(v,0);
    std::shuffle(std::begin(v),std::end(v),std::mt19937());
    srook::emplace_backer(v,1,1,1);
    
    std::stable_sort(std::begin(v),std::end(v));
    assert(srook::make_elements_string(v)==
            srook::make_elements_string(0,1,1,1)+" "s+srook::make_elements_string(srook::mkelm_str_iota(1,10)));
    
    v.erase(std::unique(std::begin(v),std::end(v)),std::end(v));
    std::shuffle(std::begin(v),std::end(v),std::mt19937());
    std::partial_sort(std::begin(v),std::next(std::begin(v),4),std::end(v));
    assert(srook::make_elements_string(0,1,2,3)==srook::make_elements_string(std::begin(v),std::next(std::begin(v),4)));
}
  • 5.4.4
    nth_elementについて述べられている。 
    #include<cassert>
#include<algorithm>
#include<functional>
#include<array>
#include<random>
#include<boost/range/algorithm_ext/iota.hpp>

int main()
{
    std::array<int,10> ar;
    boost::iota(ar,0);
    constexpr int set_value=4;

    std::shuffle(std::begin(ar),std::end(ar),std::mt19937());
    const auto num=*std::next(std::begin(ar),set_value);
    
    std::nth_element(std::begin(ar),std::next(std::begin(ar),set_value+1),std::end(ar));

    std::for_each(std::begin(ar),
            std::next(std::begin(ar),
                    std::count_if(std::begin(ar),std::end(ar),std::bind(std::less<decltype(ar)::value_type>(),std::placeholders::_1,num))),
                [&num](const decltype(ar)::value_type& x){assert(num>x);});
}
  • 5.4.5
    binary_search、lower_bound、upper_bound、equal_rangeについて述べられている。 
    #include<algorithm>
#include<vector>
#include<boost/range/algorithm_ext/iota.hpp>
#include<boost/range/algorithm/partition.hpp>
#include<boost/range/algorithm/count_if.hpp>
#include<boost/range/algorithm/sort.hpp>
#include<random>
#include<functional>
#include<type_traits>
#include<cassert>

template<class Container,class _Tp>
constexpr void range_partition_less(Container& v,_Tp&& search_value)
{
    boost::partition(v,std::bind(std::less<_Tp>(),std::placeholders::_1,std::forward<_Tp>(search_value)));
}

int main()
{
    std::vector<int> v(10);
    boost::iota(v,0);
    constexpr int search_value=4;
    
    std::shuffle(std::begin(v),std::end(v),std::mt19937());
    // search_valueより小さい値、等しい値、大きい値がその順に並んでいれば、
    // 必ずしもソートされている必要はない。
    range_partition_less(v,search_value);
    assert(std::binary_search(std::begin(v),std::end(v),search_value));

    std::shuffle(std::begin(v),std::end(v),std::mt19937());
    // 上に同じ
    range_partition_less(v,search_value);
    decltype(v)::const_iterator it=std::lower_bound(std::begin(v),std::end(v),search_value);
    assert(*it==search_value && *std::next(std::cbegin(v),std::distance(std::cbegin(v),it))==search_value);
    decltype(v)::const_iterator it1=std::upper_bound(std::begin(v),std::end(v),search_value);
    assert(search_value==boost::count_if(v,std::bind(std::less<decltype(v)::value_type>(),std::placeholders::_1,search_value)));

    boost::sort(v);
    auto result=std::equal_range(std::cbegin(v),std::cend(v),search_value);
    assert(*result.first==search_value && *result.second==search_value+1);
}
  • 5.4.6
    mergeについて述べられている。 
    #include<boost/range/algorithm_ext/iota.hpp>
#include<boost/range/algorithm/sort.hpp>
#include<srook/iterator/emplace_back_insert_iterator.hpp>
#include<algorithm>
#include<experimental/array>
#include<vector>
#include<cassert>
#include<srook/string/make_elements_string.hpp>

int main()
{
    auto ar=std::experimental::make_array(std::vector<int>(5),std::vector<int>(5));
    for(auto&& x:ar)boost::iota(x,0);
    for(auto i=*std::next(std::cend(ar.at(0)),-1)+1; i<*std::next(std::cend(ar.at(0)),-1)+7; ++i)
        ar.at(1).emplace_back(i);
    
    // ar.at(0) & ar.at(1) were sorted.
    
    std::remove_reference_t<decltype(ar.at(0))> result;
    std::merge(std::cbegin(ar.at(0)),std::cend(ar.at(0)),std::cbegin(ar.at(1)),std::cend(ar.at(1)),
            srook::emplace_back_inserter(result));
    assert(srook::make_elements_string(result)==srook::make_elements_string(0,0,1,1,2,2,3,3,4,4,5,6,7,8,9,10));
}
  • 5.4.7
    "ソートされた構造に対する集合演算"が述べられている。 
    #include<array>
#include<algorithm>
#include<boost/range/algorithm_ext/iota.hpp>
#include<cassert>
#include<vector>
#include<srook/iterator/emplace_back_insert_iterator.hpp>
#include<srook/string/make_elements_string.hpp>

int main()
{
    std::array<int,10> ar;
    std::array<int,4> a{2,4,5,6},b{2,4,10};
    boost::iota(ar,0);

    assert(std::includes(std::cbegin(ar),std::cend(ar),std::cbegin(a),std::cend(a)));
    assert(!std::includes(std::cbegin(ar),std::cend(ar),std::cbegin(b),std::cend(b)));

    std::vector<decltype(ar)::value_type> v;
    std::set_union(std::cbegin(a),std::cend(b),std::cbegin(b),std::cend(b),srook::emplace_back_inserter(v));
    assert(srook::make_elements_string(2,4,5,6,10)==srook::make_elements_string(v));

    v.clear();
    v.shrink_to_fit();
    std::set_intersection(std::cbegin(a),std::cend(a),std::cbegin(b),std::cend(b),std::back_inserter(v));
    assert(srook::make_elements_string(2,4)==srook::make_elements_string(v));
}
  • 5.4.8
    値域[first,last)がヒープを表していると定義される二つの要件が述べられている。
    • firstによって指される値が、その値域の最大値である
    • firstによって指される値は、対数時間で、ポップ操作で削除されるかあるいはプッシュ操作で追加された新しい要素である。ポップ操作もプッシュ操作も、有効なヒープを戻す
    以上のヒープ要件を満たすため、また満たされたものを操作するための機能を述べている。
  • 5.4.9
    rangeに対する最大値と最小値の評価法とその機能の利用法が述べられている。
  • 5.4.10
    lexicographical_compareについて述べられている。 
    #include<algorithm>
#include<string>
#include<experimental/array>
#include<cassert>

int main()
{
    using namespace std::string_literals;
    auto ar=std::experimental::make_array("hoge"s,"hage"s);

    assert(std::lexicographical_compare(std::cbegin(ar.at(0)),std::cend(ar.at(0)),
                std::cbegin(ar.at(1)),std::cend(ar.at(1)),
                std::greater<char>()));
}
  • 5.4.11
    next_permutation、prev_permutationについて述べられている。 
    #include<array>
#include<boost/range/algorithm_ext/iota.hpp>
#include<boost/range/algorithm/copy.hpp>
#include<boost/range/algorithm/sort.hpp>
#include<iostream>
#include<functional>
#include<experimental/iterator>

template<class Container,class Function>
inline void permutation(Container&& c,Function&& func)
{
    do{
        boost::copy(std::forward<Container>(c),std::experimental::make_ostream_joiner(std::cout," "));
        std::cout<<std::endl;
    }while(func());
}

int main()
{
    std::array<int,3> ar;
    boost::iota(ar,0);
    using stl_permutation_type=bool(*)(decltype(ar)::iterator,decltype(ar)::iterator);

    permutation(ar,std::bind(static_cast<stl_permutation_type>(std::next_permutation),std::begin(ar),std::end(ar)));
    
    boost::sort(ar,std::greater<decltype(ar)::value_type>());
    permutation(ar,std::bind(static_cast<stl_permutation_type>(std::prev_permutation),std::begin(ar),std::end(ar)));
}
  • 5.5.1
    accumulateについて述べられている。 
    #include<numeric>
#include<boost/range/algorithm_ext/iota.hpp>
#include<string>
#include<experimental/array>
#include<cassert>

int main()
{
    using namespace std::string_literals;
    std::array<int,5> ar;
    const auto sar=std::experimental::make_array("hoge"s,"var"s);
    boost::iota(ar,1);
    
    assert(15==std::accumulate(std::cbegin(ar),std::cend(ar),0));
    assert("hogevar"s==std::accumulate(std::cbegin(sar),std::cend(sar),std::string()));
}
  • 5.5.2,5.5.3,5.5.4
    部分和のpartial_sum,差集合のadjacent_difference,内積値のinner_productについて述べられている。
  • 6.1,6.2,6.3
    vector,deque,listコンテナそれぞれについての詳細が述べられている。
  • 7.1,7.2
    set,multiset,map,multimapについての詳細が述べられている。
  • 8章
    関数オブジェクトについて述べられている。標準関数オブジェクトが特筆されている。
  • 9章
    コンテナアダプタについて述べられている。
  • 10,11章
    イテレータアダプタについて述べられている。

*1:https://github.com/falgon/SrookCppLibraries