Rokiのチラ裏

学生による学習のログ

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

C++ reading

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

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

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

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

  • 4.13
    定数反復子と可変反復子の特徴について述べている。
  • 4.14
    set,multisetコンテナの基本データ構造コンセプトから成る違反的代入操作やmap,multimapを用いた違反的代入操作を特筆している。
    STLコンテナが提供する反復子のカテゴリ表が記載されている。
  • 5.1
    5章では汎用アルゴリズムについてが述べられる。
    基本的なアルゴリズム構成について述べられている。
  • 5.1.1
    置換操作をするアルゴリズムとコピー操作をするアルゴリズムがある事を述べている。 
    #include<algorithm>
#include<iostream>
#include<cassert>
#include<array>
#include<numeric>
#include<random>

int main()
{
    using thousand_ar=std::array<int,1000>;

    thousand_ar ar,ar1;
    thousand_ar result,result1;

    std::iota(std::begin(ar),std::end(ar),0);
    std::shuffle(std::begin(ar),std::end(ar),std::mt19937());
    std::iota(std::begin(ar1),std::end(ar1),0);

    std::copy(std::begin(ar),std::end(ar),std::begin(result));
    std::sort(std::begin(result),std::end(result)); // in-place
    assert(std::count_if(std::begin(result),std::end(result),
                [](const auto& x){
                    static int i=0;
                    return x==i++?true:false;
                })==result.size());

    std::reverse_copy(std::begin(ar1),std::end(ar1),std::begin(result1)); // copy
    assert(std::count_if(std::cbegin(result1),std::cend(result1),
                [b=*std::cbegin(result1)](const auto& x){
                    static int i=b;
                    return x==i--?true:false;
                    })==result1.size());
}
    このコードは以下の文章を意識して書かれた。
    STLにある、アルゴリズムのコピーバージョンを含めるかどうかの決定は、時間計算量を考慮して行われる。例えば、sort_copyは提供されていないが、それはソートという操作にかかるコストがコピーのコストよりはるかに大きいので、ユーザーがcopyを行った後にsortした方が良いと考えられるからだ。他方、reverse_copyが提供されているのは、コピーしてから逆転する方が、一度に行うよりコストが約2倍になるからである。
    書かれている通り、ユーザーがその意味を理解して適切に処理を記述しなければならない。この文章だけから汲み取るのであれば以下のようなものを定義しておいても良い気がする。*2 
    #include<algorithm>
#include<iostream>
#include<cassert>
#include<array>
#include<numeric>
#include<random>
#include<vector>
#include<miko/iterator/emplace_back_insert_iterator.hpp>
#include<experimental/type_traits>

template<class BidirIt,class OutputIt>
constexpr void copy_sort(BidirIt first,BidirIt last,OutputIt d_first,OutputIt d_last)
{
    std::copy(first,last,d_first);
    std::sort(d_first,d_last);
}

template<class BidirIt,class OutptIt,class Inserter>
constexpr void copy_sort(BidirIt first,BidirIt last,OutptIt d_first,OutptIt d_last,
        const Inserter& inserter)
{
    std::copy(first,last,inserter);
    std::sort(d_first,d_last);
}

int main()
{
    using thousand_ar=std::array<int,1000>;

    thousand_ar ar,result;
    std::vector<std::remove_reference_t<decltype(ar[0])>> v;

    std::iota(std::begin(ar),std::end(ar),0);
    std::shuffle(std::begin(ar),std::end(ar),std::mt19937());

    copy_sort(std::begin(ar),std::end(ar),std::begin(result),std::end(result));
    copy_sort(std::begin(ar),std::end(ar),std::begin(result),std::end(result),
            miko::emplace_back_inserter(v));

    assert(std::count_if(std::cbegin(result),std::cend(result),
                [](const auto& x){
                    static int i=0;
                    return x==i++?true:false;
                })==result.size());
}
    しかし、この実装は以下の仕様に反する。
    STLでalgorithmのコピーバージョンが提供されている場合、algorithm_copyというように名前を付ける。replaceのコピーバージョンであれば、replace_copyとなるわけだ。
    このような仕様になった経緯はどこにも説明されていないので分からないが、経緯を無視して考案すると、単純にcopy_algorithmというような方式もなくもないんじゃないかと思うが、こういった関数はユーザーが定義すれば良いというのも、一理ある。
  • 5.1.2
    関数パラメータのあるアルゴリズムの一例としてstd::greater::operator()について述べている。 
    #include<algorithm>
#include<functional>
#include<cassert>
#include<random>
#include<numeric>
#include<array>

int main()
{
    std::array<int,10> ar;
    std::iota(std::begin(ar),std::end(ar),0);
    std::shuffle(std::begin(ar),std::end(ar),std::mt19937());
    std::sort(std::begin(ar),std::end(ar),std::greater<decltype(ar[0])>());
    assert(std::count_if(std::crbegin(ar),std::crend(ar),
                [](const auto& x){
                    static int i=0;
                    return x==i++?true:false;
                })==ar.size());
}
  • 5.2.1 , 5.2.2
    find、adjacent_findアルゴリズムについて述べられている。 
    #include<algorithm>
#include<cassert>
#include<iostream>
#include<vector>

int main()
{
    std::vector<int> v;
    for(std::size_t i=0; i<13; ++i)v.emplace_back(i*i);

    v.insert(std::find_if(std::begin(v),std::end(v),[](const auto& x){return x>50;}),64);
    const decltype(v)::const_iterator it=std::adjacent_find(std::begin(v),std::end(v));
    assert(*it==64&&*(it+1)==64);
}
  • 5.2.3 , 5.2.4
    count、for_eachアルゴリズムについて述べられている。 
    #include<cassert>
#include<functional>
#include<algorithm>
#include<vector>
#include<numeric>
#include<type_traits>

int main()
{
    std::vector<int> v(3);
    std::iota(std::begin(v),std::end(v),0);
    const std::size_t s=std::size(v);

    for(std::size_t i=0; i<s; ++i)
        for(std::size_t j=0; j<2; ++j)v.insert(std::find(std::begin(v),std::end(v),i),i);

    std::for_each(std::begin(v),std::end(v),[](auto& x){x*=10;});

    assert(std::count(std::cbegin(v),std::cend(v),10)==3);
    assert(std::count_if(std::cbegin(v),std::cend(v),
                std::bind(std::not_equal_to<std::remove_reference_t<decltype(v[0])>>(),std::placeholders::_1,10))==6);
}
  • 5.2.5
    mismatchとequalアルゴリズムについて述べられている。 
    #include<cassert>
#include<algorithm>
#include<string>
#include<list>
#include<deque>
#include<vector>
#include<miko/iterator/emplace_back_insert_iterator.hpp>

int main()
{
    std::list<std::string> list{"Clark","Rindt","Senna"};
    
    std::vector<std::string> vec;
    std::copy(std::begin(list),std::end(list),miko::emplace_back_inserter(vec));
    vec.emplace_back("Berger");

    std::deque<std::string> deq;
    deq.emplace_back(*std::cbegin(vec));
    deq.emplace_back(*(std::cend(vec)-1));

    assert(std::equal(std::cbegin(list),std::cend(list),std::cbegin(vec)));
    assert(!std::equal(std::cbegin(deq),std::cend(deq),std::cbegin(list)));
    
    const auto p=std::mismatch(std::cbegin(deq),std::cend(deq),std::cbegin(list));
    if(p.first!=std::cend(deq))assert(*(p.first)=="Berger"&&*(p.second)=="Rindt");
}
  • 5.2.6
    searchアルゴリズムについて述べられている。 
    #include<cassert>
#include<algorithm>
#include<vector>
#include<deque>
#include<numeric>

int main()
{
    std::vector<int> v(20);
    std::deque<int> deq(5);
    std::iota(std::begin(v),std::end(v),0);
    std::iota(std::begin(deq),std::end(deq),5);
    
    decltype(v)::const_iterator it=std::search(std::cbegin(v),std::cend(v),std::cbegin(deq),std::cend(deq));
    for(std::size_t i=0; i<std::size(deq); ++i)assert(*(it+i)==i+std::size(deq));
}
  • 5.3.1
    copyとcopy_backwardについて述べられている。 
    #include<algorithm>
#include<array>
#include"srook/srook/make_elements_string.hpp"
#include<iostream>
#include<numeric>
#include<cassert>

int main()
{
    std::array<int,10> ar,ar1;
    std::iota(std::begin(ar),std::end(ar),0);
    std::iota(std::begin(ar1),std::end(ar1),0);

    std::copy(std::next(std::begin(ar),1),std::end(ar),std::begin(ar));
    std::copy_backward(std::begin(ar1),std::next(std::end(ar1),-1),std::end(ar1));

    assert(srook::make_elements_string(1,2,3,4,5,6,7,8,9,9)==srook::make_elements_string(ar));
    assert(srook::make_elements_string(0,0,1,2,3,4,5,6,7,8)==srook::make_elements_string(ar1));
}
  • 5.3.2
    fillについて述べられている。 
    #include<cassert>
#include<algorithm>
#include<array>
#include<string>

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

    std::string s="hoge"s;s+=s;
    const char replace[]="XXXX";

    std::fill(std::begin(s),std::next(std::begin(s),4),*std::data(replace));
    assert("XXXXhoge"s==s);

    std::fill_n(std::next(s.begin(),s.find_last_of(replace)+1),
            s.find_last_of(replace)-s.find_first_of(replace)+1,'Y');
    assert("XXXXYYYY"s==s);
}
  • 5.3.3
    generateについて述べられている。 
    #include<cassert>
#include<algorithm>
#include<array>
#include"srook/srook/make_elements_string.hpp"

int main()
{
    std::array<int,10> ar;

    int n=1;
    std::generate(std::begin(ar),std::end(ar),[&n]{auto t=n;n*=2;return t;});
    assert(srook::make_elements_string(1,2,4,8,16,32,64,128,256,512)==
            srook::make_elements_string(ar));
}
  • 5.3.4
    partition、stable_partitionについて述べられている。 
    #include<cassert>
#include<array>
#include<algorithm>
#include<numeric>
#include"srook/srook/make_elements_string.hpp"

int main()
{
    std::array<int,5> ar,ar1;
    std::iota(std::begin(ar),std::end(ar),1);
    std::copy(std::begin(ar),std::end(ar),std::begin(ar1));
    auto f=[](const auto& x){return x%2==0;};

    decltype(ar)::iterator pos=std::partition(std::begin(ar),std::end(ar),f);
    std::sort(std::begin(ar),pos);
    std::sort(pos,std::end(ar));

    std::stable_partition(std::begin(ar1),std::end(ar1),f);

    assert(srook::from_string::make_elements_string(2,4)==srook::make_elements_string(std::begin(ar),pos));
    assert(srook::make_elements_string(1,3,5)==srook::make_elements_string(pos,std::end(ar)));
    assert(ar==ar1);
}
  • 5.3.5
    random_shuffleについて述べられているが、この機能はC++1zで廃止される。代替として実装されるshuffleを使うべきである。*3
  • 5.3.6
    removeについて述べられている。
    #include<algorithm>
#include<vector>
#include<cassert>
#include<miko/iterator/emplace_back_insert_iterator.hpp>
#include"srook/srook/make_elements_string.hpp"

int main()
{
    std::vector<int> v{1,2,3};
    std::copy(std::begin(v),std::end(v),miko::emplace_back_inserter(v));
    v.erase(std::remove(std::begin(v),std::end(v),2),std::end(v));
    assert(srook::make_elements_string(v)==srook::make_elements_string(1,3,1,3));
}
  • 5.3.7
    replaceについて述べられている。 
    #include<algorithm>
#include<vector>
#include<cassert>
#include<miko/iterator/emplace_back_insert_iterator.hpp>
#include"srook/srook/make_elements_string.hpp"

int main()
{
    std::vector<int> v{1,2,3};
    std::copy(std::begin(v),std::end(v),miko::emplace_back_inserter(v));
    std::replace(std::begin(v),std::end(v),2,42);
    assert(srook::make_elements_string(v)==srook::make_elements_string(1,42,3,1,42,3));
}
  • 5.3.8
    reverseについて述べられている。 
    #include<algorithm>
#include<vector>
#include<cassert>
#include<miko/iterator/emplace_back_insert_iterator.hpp>
#include"srook/srook/make_elements_string.hpp"

int main()
{
    std::vector<int> v{1,2,3};
    std::copy(std::begin(v),std::end(v),miko::emplace_back_inserter(v));
    std::reverse(std::begin(v),std::end(v));
    assert(srook::make_elements_string(v)==srook::make_elements_string(3,2,1,3,2,1));
}
  • 5.3.9
    rotateについて述べられている。 
    #include<algorithm>
#include<string>
#include<cassert>

int main()
{
    using namespace std::string_literals;
    std::string str="hoge";
    std::rotate(std::begin(str),std::next(std::begin(str),2),std::end(str));
    assert(str=="geho"s);
}
  • 5.3.10、5.3.11
    swap、swap_rangesについて述べられている。本書ではswapをalgorithmヘッダファイルを読み込む事で使っているが、C++11でutilityヘッダに移された。また内部実装が意味合いとして大きな変更が行なわれているので注意が必要である。備考としてiter_swapに関しても記述した。 
    #include<cassert>
#include<utility>
#include<algorithm>
#include<miko/iterator/emplace_back_insert_iterator.hpp>
#include<vector>
#include"srook/srook/make_elements_string.hpp"
#include<numeric>

template<class Container,class... Args>
constexpr void as(const Container& container,const Args&... args)
{
    assert(srook::make_elements_string(container)==srook::make_elements_string(args...));
}

int main()
{
    std::vector<int> v(5),v1;
    std::iota(std::begin(v),std::end(v),1);
    std::copy(std::begin(v),std::end(v),miko::emplace_back_inserter(v1));
    std::reverse(std::begin(v1),std::end(v1));

    std::swap(v,v1);
    as(v,5,4,3,2,1);
    as(v1,1,2,3,4,5);

    std::iter_swap(std::next(std::begin(v),1),std::next(std::begin(v1),2));
    as(v,5,3,3,2,1);
    as(v1,1,2,4,4,5);

    std::swap_ranges(std::begin(v),std::next(std::begin(v),3),std::begin(v1));
    as(v,1,2,4,2,1);
    as(v1,5,3,3,4,5);
}

続く。

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

*2:https://github.com/falgon/mikoCppLibraries/blob/master/miko/iterator/emplace_back_insert_iterator.hpp

*3:http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4190