Effective STL 読書ノート

三大 C++ Effective 本の一つ。記者が初めて購入した C++ 関連書籍なので、とっくの昔に読書ノートがない。改めて作成する。

著者:

Scott Meyers

訳者:

細谷昭

出版社:

ピアソン・エデュケーション

発行年:

2002 年

ISBN:

978-4-89471-410-6

はじめに

  • 本書の対象を <STL の使い方は知っているが、 「効果的に」使用しているかどうか確信が持てない> (p. 1) 読者としている。

  • 本書では、STL (Standard Template Library) の定義を次のように独自に規定している。 <反復子を利用する C++ の標準ライブラリの部分> (p. 2) この定義を与えることで、本書のカバー領域をも明確に宣言している。

  • STL を扱う際には、コンパイラとライブラリの両方を区別できることが重要とある。原著を執筆していた当時は、コンパイラもライブラリも標準に準拠し切れていないものが多かったはず。著者の苦労が窺い知れる。

  • 用語

    • シーケンスコンテナと連想コンテナのおさらい。

    • 反復子の 5 カテゴリのおさらい。

    • <関数呼び出し演算子 operator() をオーバーロードするクラスは「ファンクタクラス」と呼ばれている> (p. 5)

    • アルゴリズム等のコストを「定数時間」「対数時間」「線形時間」の三つにザックリ分類している。そういえば本書は \(O(1)\) とか \(O(\log N)\) とかの記法は用いていないようだ。

  • コード例

    • 著者は typename 派。

    • 著者は operator== などの二項演算子の関数パラメータに lhs と rhs という名前を付ける習慣がある。習慣化しておくと、関数を定義するときに変数名をつけるのに悩む時間をゼロにできて素晴らしい。

コンテナ

第 1 項

  • デフォルトで使用すべきシーケンス型は vector だ。

  • 「連続メモリコンテナ」と「ノードベースコンテナ」という分類の方法がある。

第 2 項

  • <たとえば vector を使っているが、コンテナを使用するコードを変更せずに、後で deque や list などに置き換えられるようにしようとする。つまり、「コンテナに依存しないコード」を書こうとするのである。ほとんどの場合、よかれと思ってなされるこの種の汎用化は間違っている> (p. 15)

    例えば異なるシーケンスコンテナに適用する反復子を無効化する規則が異なる。異なるコンテナは「異なる」のであって、互いを交換するようには設計されていない。といった議論を展開している。かなり丁寧に（誰かを）説得している。

  • コーディングテクニックとして、typedef の効用を説いている。

第 3 項

  • この項目はタイトルが全て。コンテナにオブジェクトを追加するときは、必ずそのオブジェクトのコピーが入る。取得も基本的にはコピーを出す。

第 4 項

  • <empty はすべての標準コンテナに対して定数時間処理だが、size の場合、一部の list の実装には線形時間がかかる> (p. 22)

    • list 実装者が size を定数時間処理にしようとすると、今度は splice が線形時間処理にならざるを得ない。

  • コンテナに要素があるか否かをテストするには、常に empty を呼びだす。

第 5 項

この本を買って、一番最初に感動を覚えた項目。

  • 「vector v1 と v2 があり、 v1 を v2 の後半部分と同じ内容にする」という処理を実装するのに、for などのループを使わずに書ければ及第点。

  • 「範囲メンバ関数」という用語を導入し、その効用を説明している。

    • コーティングの作業量が少ない。

    • 簡単でわかりやすい傾向がある。

  • <開発者は、どのエディタが「最高のエディタ」かについての議論を好むように（Emacs であることに疑問の余地はないのだが）> (p. 26)

    これは本気かギャグか判断つきかねる。

  • 範囲メンバ関数として、次のものをとりあえず意識しておく。

    • コンストラクタ

    • insert

    • erase （後述の項目で remove アルゴリズムとのコンボ技を紹介している）

    • assign

第 6 項

「関数宣言として解析できるものは関数宣言とみなす」ルールによって、コンストラクタから iterator を生成するコードがコンパイルエラーになることがある。

第 7 項

  • new によるポインタを抱えるコンテナを取り扱うことの難しさを説明している。

  • <仮想デストラクタなしにクラスから公開で継承することは、 C++ でやってはいけないことの 1 つである> (p. 36)

第 8 項

そういえば auto_ptr に auto_ptr を代入すると、右辺側は null になるのだった。 auto_ptr にコピーコンストラクタとコピー代入演算子があるのは、どういう理由からだったろうか。

第 9 項

コンテナから要素を消去する方法について。

  • remove_if 方式で条件を満たす要素を連想コンテナから削除する場合が少しややこしいか。

  • 削除しながら、何か別のことをする処理を書くには、やはり手でループするしかない。

第 10 項

アロケータに関する話題。

第 11 項

カスタムアロケータに関する話題。

第 12 項

コンテナのスレッドセーフティ（安全性）について。あまりうれしいことは書いていない。

  • <クラスを使ってリソースの有効期限を管理する考え方は、一般的に「リソース取得は初期化である」として知られており、 C++ の総合的な教科書では、必ず説明を読むことができる。 Stroustrup がこの慣用句を有名にした> (p. 59) こういうクラスを利用する方法は、<例外に対して堅牢である。C++ では、例外が発生すると、ローカルオブジェクトは破棄されることが保証されている> (p. 60) 取得してあるリソースが、確実に呼び出されるデストラクタが解放するからだ。

vector と string

第 13 項

  • 動的に割り当てる配列よりは、vector や string を使う。

  • string の実装が参照カウンタ方式かを調べるには、コピーコンストラクタを見ればよい。

第 14 項

  • vector::reserve に関する話題。でもこの例のコードならば、resize して operator[] で要素を代入したほうがパフォーマンスがいいのではないか。

第 15 項

  • <申し訳ないが、そこまでソースコードを読み込んでいなかった> (p.70) がウケた。

第 16 項

  • 配列を受け取る関数に vector v を渡すには &v[0] を使う。

  • const char* を受け取る関数に string s を渡すには s.c_str() を使う。

    • const の付かない char* を受け取る関数に対しては、s を vector<char> v に一旦作り直してから、その関数に &v[0] を渡す。

第 17 項

この本を買って、二番目に感動した項目。スワップはやはりいい。

  • vector/string で erase を呼んだ後でも、容量 (capacity) は通常そのまま保たれる。それを強制的に削るため、swap をトリッキーな呼び出し方をして、vector/string から余分な容量を削除することができる。著者はこの技法を “shrink to fit” 方法と呼んでいる。

    string s;
// ...
string(s).swap(s);

    あるいは

    string().swap(s);

第 18 項

vector<bool> はいらない。状況に応じて次のいずれかで対応する。

  1. deque<bool>

  2. bitset

連想コンテナ

再読して気付いたことがある。この章が最も記憶に定着していなかった項目が多い。

第 19 項

  • 長いが重要なので引用する。 <find アルゴリズムと set の insert メンバ関数は、 2 つの値が同じかどうかを調べる多くの関数を代表している。しかし、find と insert が行う方法は異なっている。find の「同一」の定義は「等値」(equality) であり、 operator== に基づいている。set::insert の「同一」の定義は「等価」 (equivalence) であり、通常は operator< に基づいている。 2 つの定義は異なるため、一方の定義では 2 つのオブジェクトの値が同一とし、他方の定義では同一としないことがある。したがって、STL を効果的に利用するには、等値と等価の違いを理解しなければならない> (p. 82)

  • ここは読み落としていた。 <すべての標準連想コンテナでは、key_comp メンバ関数によって、ソート述語を利用できる> (p. 83)

第 20 項

ポインタを格納した連想コンテナは、デフォルトではアドレス順にソートされる。これが困る場合だけ、本項のアドバイスに従えばいいだろう。

第 21 項

  • set の比較関数として less_equal を使うと、その set はあっさり壊れる。

  • <読者による面白さの定義は著者とは違うかもしれない> (p. 91)

  • 連想コンテナの比較関数の要件とは、その比較関数が strict weak ordering を定義すること。比較関数が同じ値を比較すると、false を返す必要があることを憶えておく。

第 22 項

  • map/multimap のキーは変更できない。const だから。

  • set/multiset のキーは変更できる。しかしコンテナを破壊する可能性大ゆえ変更してはならない。

    • ただし「キー以外の部分」については変更することに問題はない。

      EmpIDSet::iterator i = se.find(selectedID);
if(i != se.end()){
    const_cast<Employee&>(*i).setTitle("Corpolate Deity");
}

      安全で移植性のある形で書きたければ、erase と insert を使う。

第 23 項

ソート済み vector のパフォーマンスを知らしめる内容。この項は実務の上でも重要。

  • 多くの場合、対数時間探索かかる標準連想コンテナよりは、定数時間探索が期待できるハッシュコンテナのほうがよい。

  • <直感に反して、標準連想コンテナのパフォーマンスは低速の vector に劣ることは珍しくない> (p. 99)

  • 二分探索木を二分探索するより、ソート済み vector を二分探索するほうがパフォーマンスが優れている理由を議論している。

    1. サイズ。vector が優れていることは明白。

    2. 参照の局所性。ノードベースのコンテナでは、コンテナ内の順序では近くにあるコンテナ要素同士が、物理メモリ的にも近くにあるとは限らない。

    総合的に考えて、ソート済み vector の二分探索に軍配を上げているだけ。

第 24 項

map::operator[] vs map::insert

insert:

map に要素を追加するとき（名前どおりだ）。効率の観点からもよい。

operator[]:

map に既に存在する要素を更新するとき。効率的かつ美的。

第 25 項

再読して気付いたが、本書はハッシュを猛烈にプッシュしている気がする。

  • 標準 C++ ライブラリにはハッシュテーブルはない。

  • STLport には hash_set, hash_map のようなものがある。

反復子

第 26 項

  • const_iterator から iterator へ変換する方法がない。

  • const_reverse_iterator から reverse_iterator へ変換する方法がない。

  • <const の正確さという観点からすれば（確かに価値ある観点であるのだが）、実際に欠陥があるかもしれないというだけで（解決方法はあるのだから）、 const_iterator を使わないことは不当に思えるかもしれない。しかし、コンテナの一部のメンバ関数では iterator が選別されている状況を考え合わせると、実際上、const_iterator は iterator ほど役に立たないだけでなく、あえて使う理由がないという結論に達せざるを得ない> (pp. 116-117)

第 27 項

const_iterator を iterator に変換する技法として、advance と distance を組み合わせて利用する方法を紹介している。しかし、どう考えてもこの方法は時間的コストがかかる。本項の結論もそう認めているので、この項は前項のガイドラインを補強するために書かれたのかな。

第 28 項

reverse_iterator::base について。

  • find 等のアルゴリズムに reverse_iterator を与えると、その戻り値の型もまた reverse_iterator になる。

    vector<int> v;
// ...
vector<int>::reverse_iterator ri = find(v.begin(), v.end(), 3);
v.erase((++ri).base());

第 29 項

  • istream_iterator は operator>> に依存する。これは書式付き入力を行うため、遅いのを承知の上で利用すること。

  • 書式などどうでもよい場合、入力ストリームから次の文字を取得したいだけならば、 istreambuf_iterator の利用を検討する。入力と同様に、出力ストリームの処理でも ostreambuf_iterator の方がよい場合がある。

アルゴリズム

第 30 項

  • transform 等、出力反復子を指定するアルゴリズムには、出力先範囲が適切に確保されている、または確保してくれる反復子を渡す。

    • back_inserter, front_inserter, inserter ならば、出力先サイズを自動的に拡張してくれる。

    • 出力先のサイズがわかっている場合は、対象コンテナに対して reserve や resize を先に使うと効率がよい。inserter 系を用いる場合は resize ではなく reserve を使う。

第 31 項

この本を読んで、4 番目に感動した項目はこれだった。

  • まずはこの鉄則を頭に叩き込む。<確かに sort はすばらしいアルゴリズムだが、不必要なところで使う理由はない。場合によっては、一部をソートするだけで済む> (p. 130)

  • ベスト N が欲しい場合は partial_sort で十分。

  • ベスト N が「順序に関係なく」欲しい場合は nth_element で十分。

  • partial_sort も nth_element も stable ではない。特に問題はないだろう。

  • 全体を二種類に分類するような目的ならば partition が利用できる。

  • ソート系アルゴリズムは <ランダムアクセス反復子を必要とする> (p. 133)。

    • 問題は list をソートしたい場合だ。状況によって、内容を vector に移植してから所望のソート、分類をすることになるかもしれない。

    • partition 系は list::iterator を受け付ける。

  • <ソートアルゴリズムを選ぶ際には、パフォーマンスを基準にするのではなく、目的に適しているかどうかに基づいて選択することをお勧めする。必要な処理しかしないアルゴリズムを選べば、必要な処理がはっきり表現されるだけでなく、 STL を使って最も効率的な方法で目的を達成できる> (p. 135)

第 32 項

  • remove アルゴリズムの誤解を解くところから始めている。指定範囲の末尾付近にゴミが溜まるだけ。

  • <コンテナのメンバ関数だけがコンテナの要素を削除できる。そこに本項の要点がある。つまり、本当に削除する場合は、remove の後に erase を実行しなければならない> (pp. 138-139)

    vector<int> v;
// ...
v.erase(remove(v.begin(), v.end(), 99), v.end());

    <範囲形式の erase の第 1 引数に remove の戻り値を渡すことが多く、一種の慣用句になっている> (p. 139)

  • unique も remove のように末尾付近にゴミを寄せるアルゴリズムだ。 erase と組み合わせて利用する。

  • list に関しては、アルゴリズムではなくメンバ関数の remove, unique により、本当に削除できる。

第 33 項

生のポインタを格納したコンテナに対する remove 風アルゴリズムの適用は危険。

第 34 項

  • ソート済み範囲を入力要件とするアルゴリズムがあるので、注意すること。

    二分探索系

    binary_search, lower_bound, upper_bound, equal_range

    重複要素検索系

    set_union, set_intersection, set_difference, set_symmetric_difference, merge, inplace_merge, includes

  • <Unix 開発者なら、STL の unique とUnix の uniq が驚くほど似ていることに気付くだろう。筆者が思うに、この類似は決して偶然の一致ではない> (p. 145)

  • 次のタイプのコードは、業務時に見落とす可能性が大なのでノートをとっておく。望ましくない理由と望ましいコードを、読み返したときに思い出せ。

    vector<int> v;
// ...
sort(v.begin(), v.end(), greater<int>());
// ...
bool a5exists = binary_search(v.begin(), v.end(), 5);

第 35 項

  • mismatch アルゴリズムを利用する事前条件として、違う長さの範囲を与える場合は、短い範囲のほうを先に与えることになっている。

  • 次の事実により lexicographical_compare は strcmp の汎用版だと言える。

    1. strcmp は文字配列にしか適用できないが、lexicographical_compare は任意の型の値の範囲に適用できる。

    2. strcmp は比較手段が一定である。一方、lexicographical_compare は任意の述語を与えられる。

  • <速度が重要である場合、STL の標準アルゴリズムの代わりに標準以外の C 関数を使っても問題ないだろう> (p. 150)

第 36 項

copy_if ネタ。

第 37 項

  • <numeric> ヘッダに置かれているアルゴリズムにも注目してやろう。

  • for_each と accumulate に渡す関数パラメータ（述語）について、余分な作用が一方では認められていて、他方では認められていないことが、本書著者は気に食わないようだ。

ファンクタ、ファンクタクラス、関数など

  • 関数風オブジェクト＝ファンクタ

第 38 項

ファンクタは値渡しが鉄則。

  • <第一に、関数オブジェクトは小さくする必要がある。さもないと、コピーの負担が大きくなりすぎる。第二に、関数オブジェクトは単相（非多相）でなければならない。つまり、仮想関数を使ってはいけない。基本クラス型のパラメータに派生クラスオブジェクトを値で渡すと、スライシングの問題が発生するためである。つまり、コピー中に派生部分が削除されてしまう> (p. 161)

第 39 項

述語の戻り値は、関数の実引数からだけで決めるようにというガイド。本項では、そのようなものを純粋関数と呼んでいる。

第 40 項

  • ファンクタクラスを自分で書く場合、それを unary_function または binary_function からの派生型として定義しようという話。このように定義しておいて初めて標準関数アダプタ (not1, not2, bind1st, bind2nd) に咬ませることができる。

  • STL では各ファンクタクラスには一つの operator() しかないと暗黙の内に仮定している。

第 41 項

  • <STL コンポーネントにメンバ関数を渡すときは常に mem_fun と mem_fun_ref を使わなければならない> (p. 174)

第 42 項

  • 「最小意外性の原則」は守ること。less に operator< を呼び出す以外の処理をさせぬこと。

  • 特定の状況における比較を行うには、less でないファンクタクラスを作成して、それを利用すること。

STL を使ったプログラミング

第 43 項

  • アルゴリズムのおかげで、プログラマーが独自にループを書く作業が減る。さらに、効率、正確さ、保守性も得られる。

  • <反復子はアルゴリズムに渡し、反復子の複雑な操作は「アルゴリズム」に任せよう> (p. 184)

  • 自作ループは、それをパッと見てすぐに何をしているものなのかがわからない。一方、アルゴリズムの呼び出しは、関数名を見れば少なくとも処理の意図はわかる。

  • 場合によっては、アルゴリズムに渡すファンクタを定義するコードのほうが、自作ループを書くよりもコード量がかさむことがある。

  • <for, while, do などの低水準の語を insert, find, for_each などの高水準の語に置き換える> (p. 187)

第 44 項

同名のアルゴリズムとメンバ関数が存在する場合は、当然メンバ関数を優先する。特に連想コンテナの find 系の処理について説明している。

第 45 項

  • あるコンテナについて、特定の値を持つかどうかを調べるには、 find アルゴリズムを用いる。そして、戻り値とコンテナの end が違うかどうかをテストする。

    • ただし、ソート済み範囲では binary_search のほうが効率がよい（ただし、存在する位置はわからない）。

    • ソート済み範囲で、どの位置にまであるか調べたいときには equal_range を用いる（ただし等値ではなく等価に基づいている）。 equal_range の戻り値ペアが違う位置を指していれば（一つ以上）存在する。

  • ソート済み範囲で「ある値より小さくない最初の要素」を探索するには lower_bound を用いる。

  • 連想コンテナの場合、以上のルールに基づいてメンバ関数版を利用する。

  • set, map に関しては、特定の値を持つかどうかを調べるのに find ではなく count を使っても（効率が落ちないので）構わない。

  • <multi コンテナでは、特定の値を持つ要素が複数存在する場合、find がコンテナの中で特定の値を持つ「最初の」要素を識別することは保証されない> (p. 197)

第 46 項

  • <高水準言語を使ったプログラミングに関する不満の一つは、抽象の度合いが高まるにつれ、生成されるコードの効率が低くなることである> (p. 198)

  • インライン展開可能性の関係で、アルゴリズムには関数（＝ポインタ）を渡すよりも、関数オブジェクトを渡したほうが、コンパイラが効率のよいコードを生成する。<関数ポインタパラメータはインライン化されない。そのため、経験豊富な多くのC プログラマにとって信じがたいことだが、ほとんどの場合、C++ の sort の方が C の qsort より高速になる> (p. 200)

第 47 項

  • 冒頭で次のコードを提示しておき、

    v.erase(
  remove_if(find_if(v.rbegin(), v.rend(),
                    bind_2nd(greater_equal<int>(), y)).base(),
            v.end(),
            bind_2nd(less<int>(), x)),
  v.end());

    これはやり過ぎだと断りつつ、<しかし、Scheme などの関数型言語に慣れたプログラマが感じることは違っているだろう> (p. 203) と言ってのけるのには参った。

  • アルゴリズムを多用すると、どうしても先のコードのようにネスト・バインダ・アダプタが増える。

  • <理解できないソフトウェアは保守できない> (p. 205) は「理解できないものは所持できない」だ。

第 48 項

インクルードのコツをまとめている。

第 49 項

コンパイルエラー時に現れる <猫がキーボードの上を歩いて入力された> (p. 207) ようなメッセージの解読方法のコツ。

第 50 項

参考文献

ノートをとらない。

ロケールと大文字小文字を区別しない文字列比較

  • <x と y が std::string 型であれば、式 x < y は次の式と等価である。

    std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());

    この式で、lexicographical_compare は operator< を使って個々の文字を比較する> (p. 227)

  • <toupper は一つの引数を取る単純な関数のようだが、グローバル変数にも依存する> (p. 229)

  • <C++ 標準ライブラリのロケールは、ライブラリの実装の中に深く埋め込まれたグローバルデータではなく、 std::locale 型のオブジェクトである> (p. 229)

  • <ロケールの名前は標準化されていない> (p. 230)

  • <C++ のロケールは「ファセット」に分割される。各ファセットは国際化の異なる面を処理する。関数 std::use_facet は、ロケールオブジェクトから特定のファセットを抽出する。ファセット ctype は、大文字小文字の変換を含め、文字の分類を処理する> (p. 230)

    // L をロケールとして
const std::ctype<char>& ct = std::use_facet<std::ctype<char> >(L);
bool result = ct.toupper(c1) < ct.toupper(c2);

  • <use_facet を呼び出すには負担が大きいことがあるため、use_facet の呼び出し回数は少なくした方がよい> (p. 230)

Microsoft の STL プラットフォームについて

仕事で経験があるのでよく承知しているが、名前に .NET の付かない VC 環境では一部コンテナのメンバ関数がおかしい。この付録ではその回避策、代替案を紹介している。

STL のメンバ関数テンプレート、特に型の違うコンテナから insert や assign する場合、

vector<Widget> vw;
list<Widget> lw;
set<Widget> sw;

// ...

vw.insert(vw.end(), lw.begin(), lw.end());
vw.insert(vw.end(), sw.begin(), sw.end());

最後に書いた insert の行が MSVC6 以前ではコンパイルできない。その対応策として、

  1. copy と back_inserter, inserter を組み合わせる（ただし効率が悪い）

  2. STL を入れ替える（ただしコンパイラがメンバ関数テンプレートに耐えられる MSVC6 のみ可能）

ことを挙げている。

<MSVC6 に付属する STL の実装以外は使用できない場合でも、 Dinkumware Web サイトは利用する価値があるだろう。このサイトには、MSVC6 ライブラリ実装で知られているバグのリストが掲載されており、使用しているライブラリを変更して不具合を減らす方法が説明されている> (p. 240) 変更云々は仕事ではできないが、バグリストは見る価値がありそうだ。