Rokiのチラ裏

学生による学習のログ

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

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

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

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

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


  • 3.1
    3章では、主にSTLとその他のライブラリの相違や優れた点を述べている。3.1ではその内の拡張性についてを特筆している。
    従来のライブラリでは、アルゴリズムが特定のクラスと関連付けてられていて、ライブラリクラスから新しいクラスを派生させることで、アルゴリズムの追加ができるようになっている。この方法にはいくつか欠点がある。
    • うまくいくのは、そのクラスのもともとのデザイナがこうした拡張が行われることを予期して、それに対応するフックを慎重に提供している場合(例えば、特定のデータメンバをプライベート(private,非公開)ではなくプロテクト(protected,限定公開)にしている、あるいは特定の関数を非仮想関数ではなく仮想関数にしている場合など)に限る
    これは、
    ライブラリクラスから新しいクラスを派生させることで、アルゴリズムの追加ができるようになっている。
    というような形式のライブラリであれば、実現されていて当然の条件だと、私は思うのだが。
    継承させる事によって利便性を期待できるライブラリを目指すのであれば、元々継承される事を想定としている基底クラス、ライブラリでなければ、それはライブラリとして、全くの無意味である。
  • 3.2
    コンポーネントの互換性がイテレータによって、有効的な措置が成されている様子を述べている。
  • 3.3
    全てのアルゴリズムが全てのコンテナに適用される事によって、アルゴリズム本体が非効率的になる面を考慮して、特異的にメンバ関数を定義しているというような処置の例を述べている。個人的には、メンバ関数の定義に加えて、sort非メンバ関数を以下のように定義しても良かったのではないかとも思う。
    #include<experimental/array>
    #include<list>
    #include<algorithm>
    #include<iostream>
    #include<cassert>
    
    template<class _Tp,class Allocator=std::allocator<_Tp>>
    constexpr void sort(std::list<_Tp,Allocator>& li){li.sort();}
    
    template<class RandomIt>
    constexpr void sort(const RandomIt& b,const RandomIt& e){std::sort(b,e);}
    
    int main()
    {
        auto ar=std::experimental::make_array(9,1,8,2,7,3,6,4,5);
        std::list<int> li(ar.size());
        std::copy(std::begin(ar),std::end(ar),std::begin(li));
    
        sort(std::begin(ar),std::end(ar));
        sort(li);
    
        assert(std::is_sorted(std::cbegin(ar),std::cend(ar)));
        assert(std::equal(std::cbegin(ar),std::cend(ar),std::cbegin(li)));
    }
    
    適用範囲は、コンテナ全体しか有りえないので、コンテナオブジェクトを渡してしまっても良い気がしないでもない。
  • 4.1
    4章では、イテレータについて述べられている。冒頭ではイテレータがコンテナとそれに対応できる的確なアルゴリズムとの仲介としての役割を担っていると述べられている。また、全汎用アルゴリズムを全コンテナで使用できるわけではない事を再度述べ、どのようなコンテナでどのようなアルゴリズムが使用できるかを知る術は、入力、出力、前方向、双方向、ランダムアクセスの五つのカテゴリにイテレータを分類する事としている。また、前提知識として反復子値域について補足している。
    4.1では入力反復子の基本的要件とistream反復子について述べている。
    #include<algorithm>
    #include<iterator>
    #include<iostream>
    
    int main()
    {
        std::find(std::istream_iterator<char>(std::cin),std::istream_iterator<char>(),'x');
    }
    
  • 4.2
    出力反復子の基本的要件とostream反復子について述べている。
    #include<algorithm>
    #include<iterator>
    #include<iostream>
    #include<experimental/array>
    
    int main()
    {
        auto ar=std::experimental::make_array(1,2,3,4,5,6,7,8,9);
        std::copy(std::begin(ar),std::end(ar),
                std::ostream_iterator<decltype(ar[0])>(std::cout," "));
    }
    
  • 4.3
    前方向反復子の基本的要件とその例を述べている。
    #include<algorithm>
    #include<array>
    #include<cassert>
    
    int main()
    {
        std::array<int,5> ar;
        ar.fill(10);
        std::replace(std::begin(ar),std::end(ar),10,42);
        assert(std::count(std::begin(ar),std::end(ar),42)==ar.size());
    }
    
  • 4.4
    双方向反復子の基本的要件とその例を述べている。
    #include<algorithm>
    #include<array>
    #include<numeric>
    #include<cassert>
    #include<iostream>
    
    int main()
    {
        std::array<int,5> ar;
        std::iota(std::begin(ar),std::end(ar),0);
        std::reverse(std::begin(ar),std::end(ar));
        assert(std::count_if(std::begin(ar),std::end(ar),
                [last=std::crend(ar)](const auto& x){
                    static auto i=*(last-1);
                    return x==i--?true:false;
                })==ar.size());
    }
    
  • ランダムアクセス反復子の基本的要件とその例を述べている。
    #include<array>
    #include<algorithm>
    #include<cassert>
    #include<numeric>
    
    int main()
    {
        std::array<int,5> s;
        std::iota(std::begin(s),std::end(s),0);
        assert(std::binary_search(std::begin(s),std::end(s),4));
    }
    
  • 4.6
    それぞれの反復子の関係性を述べている。
    • 前方向反復子は、入力および出力反復子でもある。
    • 双方向反復子は、前方向反復子でもあり、したがって入力および出力反復子でもある
    • ランダムアクセス反復子は、双方向反復子でもあり、したがって前方向反復しかつ入力および出力反復子でもある
    • 入力または出力反復子のみを必要とするアルゴリズムは、前方向、双方向あるいはランダムアクセス反復子とも使用できる
    • 前方向反復子供を必要とするアルゴリズムは、双方向、ランダムアクセス反復子とも使用できる
    • 双方向反復子を必要とするアルゴリズムは、ランダムアクセス反復子とも使用できる

    したがってコンテナとアルゴリズムに関する次のような仕様の中で、反復子カテゴリは使用される。

    • コンテナクラスの記述には、そのコンテナクラスの提供する反復子タイプのカテゴリを含める
    • 汎用アルゴリズムの記述には、そのアルゴリズムが処理に使用する反復子カテゴリを含める。
    とても解りやすい。
    反復子階層は、STLデザインの背景にある基本的な考え方で特に重要なものである。つまり、「STLのコンテナとアルゴリズムのインタフェースは、効率的な組み合わせを推進しながら、非効率的な組み合わせを抑制するようにデザインされている」。推進の源泉は、エラーなしでコンパイルできる効率的な組み合わせである。非効率的な組み合わせには、コンパイルできるものもあるが、ほとんどの場合、コンパイル時エラーを引き起こし、労力が多くなる。
    コンテナが数種類存在する理由は、コンテナごとのデータ構造や理念があり、効率的な処理というのは全て元から紐付いている。そうであれば、非効率的な処理を受け入れるのではなく、元からコンパイル時エラーにして弾いてしまうのが、良い設計と言えるだろう。
  • 4.7
    挿入反復子について述べている。
    #include<vector>
    #include<cassert>
    #include<algorithm>
    #include<miko/iterator/emplace_back_insert_iterator.hpp>
    
    int main()
    {
        std::vector<int> v;
        // back_insert_iteratorのemplace_back版イテレータ
        miko::emplace_back_insert_iterator<decltype(v)> it(v);
        
        for(std::size_t i=0; i<5; ++i,*it=i);
        assert(std::count_if(std::begin(v),std::end(v),
                [first=v[0]](const auto& x){
                    static std::size_t i=first;
                    return x==i++?true:false;
                    })==v.size());
    
        std::vector<int> v1;
        std::copy(std::begin(v),std::end(v),miko::emplace_back_inserter(v1));
    }
    
    挿入反復子では、operator=をオーバーロードして、組み込みのセマンティックとは異なる、挿入という動作をする。前々から思っていたが、これはあまり解りやすい定義ではないと個人的には思う。
    (miko::emplace_back_inserter*2でも、STLに合わせて、operator=で挿入できるような定義にはしている。 )
  • 4.8
    istream_iteratorとostream_iteratorの補足が述べられている。
  • 4.9
    arguments nameによって、argumentsに差し込むイテレータのタイプが判別できる、といった内容が述べられている。
  • 4.10
    汎用アルゴリズムをデザインするにおいて、std::findを例題に、インプリメンテーションが必要最低限である事による汎用性からその有用性を示している。単純に、std::listはリストデータ構造であるので、operator <は使えるべきではないので、当然の所為に感じる。
  • 4.11
    何度本書が今までこの話題に触れてきたかもうわからないぐらい取り上げられている気がするが、listコンテナが何故非メンバ関数sortで扱えないかについて述べている。
    繰り返しになるが、単純に、listコンテナはその名の通り、リストデータ構造を実現しなければならないコンテナであって、データに対するアクセス方法として双方向アクセスのプロセスを実現しなければらないからである。
    本書がstd::listコンテナで非メンバ関数sortに差し込めない話題を特出して述べている時の大体は、ユーザーが自分で、非メンバ関数sortのインプリメンテーションで用いられる演算全てを独自的に定義し実行すればそれは確かにコンパイルは通るし、動作自体はするが、その動作は線形アクセスとなるので、std::list::sort()と比較すると非効率的である上にただ労力がかかるだけであるといった内容である。
  • 4.12
    非効率的なコンテナとアルゴリズムの組み合わせで実行できてしまう例を述べている。
    set<int> set1;
    // ...set1にいくつかの値を入れるコードが入る
    set<int>::iterator where;
    where=find(set1.begin(),set1.end(),7);
    
    このコードは実行可能といっても線形時間である。次のように書いた方が対数時間で実行できるから格段に良い。
    where=set1.find(7);
    
    適切な処理を記述するべきである。

続く。