C++ は C よりも学ぶのが難しいが、具体的にどこが難しいのか？
C++ の美しさを感覚的に理解する？
コース内容#
質問：なぜC++ 11標準を学習の重点にするのか？
回答：C++ 03 から 11 への変化は大きく、11 から 14、17 への変化は小さい。20 標準は非常に新しく、まだ普及していないため、C++ 11 標準から始めるのは非常に良い選択です。
C++ の言語特性#
主な特性#
- ヘッダーファイル：130 個（C 言語：29 個）
- STL
- クラスとオブジェクト
- テンプレート
- ラムダ（C++ 11）
- 例外処理（C++ 11）
解説#
- ヘッダーファイルが非常に多く、ヘッダーファイルを噛むことを学習方法としてはいけない
- STL
- 本来は標準ヘッダーファイルに属さないもので、HP 研究所の大物たちが開発したもので、C++ は後にこれを取り入れた
- オブジェクト指向（クラスとオブジェクト）
- ジェネリックプログラミング（テンプレート）：1 つの関数を開発することは、100 個の関数を開発することに相当する
- 関数型プログラミング（ラムダ）
- C 言語の手続き型プログラミングパラダイムに比べ、C++ は 3 つのプログラミングパラダイムを追加した。エンジニアリングプロジェクトでは、一般的に 1～2 種類のプログラミングパラダイムを同時に使用し、手続き型とオブジェクト指向が比較的よく使われる
- 新しいプログラミングパラダイムの本質的な役割：開発効率の向上
- 異なるプログラミングパラダイムは異なる開発効率に対応し、開発効率はコードを書く時間 + テスト + メンテナンスの時間を考慮する
- 時間が経つにつれて、開発効率は高くなる可能性があるが、コードを書く難易度も高くなる
- 新しいプログラミングパラダイムを使用する主なシナリオ：開発効率を向上させることができる
- PS：C でもオブジェクト指向パラダイムを実現できる。Microsoft のCOM in plain Cを参照
- 例外メカニズム
- 特定のランタイムエラーに対処し、プログラムのクラッシュを回避するためのメカニズム
- 設計哲学：プログラムの論理エラーはまずコンパイルエラーとして現れ、その後ランタイムエラーとして現れる
PS：
- C++ を学んだ後、もし Java を学ぶ必要がある場合は、プログラミングパラダイムに基づいて分類して学ぶことができる
- C++ は C 言語の大部分の特性（文法規則）を継承している
- C++ は C のいくつかの特性を削除したが、重要ではない
入出力のプログラム比較 [C、C++]#
-
-
- cin、cout
- 型（フォーマットプレースホルダー）を指定する必要がない
- 左シフト、右シフト演算子 [<<、>>]：演算子のオーバーロードに関わる
- printf
- "% lf"：デフォルトで 6 桁の小数を保持
- "% g"：すべての有効数字の桁数を出力し、cout が使用するルール
- scanf、printf は関数であり、cin、cout は関数ではなくオブジェクトである
- [PS] endl：改行 + バッファをクリア
STL：組み込みデータ構造#
queue、stack、string、unordered_map、map...C 言語で自分で実装するよりも、ここでは任意の型の要素を非常に便利にサポートできる。詳細は《面接筆試算法上》——5 STL “コンテナ” の使用と練習を参照
deque#
- 両端キュー
- 単調キューを実現できるが、queue を使用することはできない。単調性を維持するためには、尾部から出隊する必要がある。詳細は《面接筆试算法下》——3 単調キューと単調スタックを参照
string#
- C の strcmp と C++ の ==
- C の strcat と C++ の +=
- C の strlen と C++ の length ()
- 実装原理は少し異なる
- strlen：毎回文字配列の先頭から末尾までスキャンし、'\0' に出会うまで --> O (N)
- .length ()：メンバー属性 --> O (1)
- substr (pos, n)：pos から n 文字を取得
map 関連#
- ハッシュテーブルに基づく [無秩序]
- ストレージ、検索の平均時間計算量：O (1)
- [C++ 11] unordered_map
- [C++ 11 以前、非標準] hash_map
- 赤黒木に基づく [秩序]
- map
PS：
- 外見は配列に似ているが、機能はより強力である
- find (key)：見つからない場合、end () を返す [ハッシュテーブルの終了位置]
コードデモ#
strlen と length () の比較#
-
- 時間にわずかな差があるが、大きな差ではない。元の環境は strlen に最適化があった可能性がある
- c_str()—cppplus
map と unordered_map の比較#
-
- イテレータの使用をまず感じてみて、型定義を明確に示し、後で auto キーワードを代わりに使用できる❗
- 順序性は要素を遍歴する際に現れる
- unordered_map は key と value が無秩序であり、元の順序も乱れる
- map はソートツールとして使用できる
-
- auto キーワードの使用
- 前の完全なイテレータ型定義と比較して、まず感じてみて
- 非常に強力で、cin と scanf の違いのように、iter の型を自動的に判断できる
- ソート結果
-
- 見た目はカウントソートのようだが、そうではない
- 時間計算量は底層の赤黒木に関わる：O (NlogN)
-
-
sort#
-
-
- C++ の 4 つのプログラミングパラダイムを示している
- CMP () は呼び出し可能なオブジェクトである
- ラムダ式は C++11 で新たに導入された
- ここで struct と class の違いは、深く理解する：struct と class の違いを参照 —— ブログ
授業中の練習#
HZOJ-245：倉庫の立地選定#
サンプル入力
5
1 3 5 6 10
サンプル出力
12
- 思考
- 注意：入力は乱序の可能性がある
- 問題の変換
- ランダムに点 p を選択し、現在の距離の合計を s1 とする
- 点 p が小さな距離 Δ だけ移動すると、距離の合計 s2 = s1 + (n1 - n2) * Δ
- n1：点 p の左側の店舗数；n2：点 p の右側の店舗数
- 【目標】s2 < s1
- n1 - n2 <0 のとき、Δ> 0 --> s2 < s1：右側の店舗が多いとき、点 p を右に移動するとより良い解が得られる
- n1 - n2 > 0 のとき、Δ <0 --> s2 < s1：左側の店舗が多いとき、点 p を左に移動するとより良い解が得られる
- 【最終目標】n1 = n2 であるため、n / 2 番目の要素の座標を探す
- n は店舗の総数で、インデックスは 0 から始まる
- コード
- 解法 1：sort メソッド
-
- 主な時間は入力と合計にかかる
- sort の使用については《面接筆試算法上》——2 二分专题 —— 附加知识点を参照。終了位置は最後の要素の次の位置
-
- 解法 2：nth_element メソッド
-
- nth_element
- クイックセレクションアルゴリズムに基づく —— 知乎、クイックソートの Partition プロセスを参考にしているが、全体のシーケンスをソートすることはない
- 実行後、【k 番目の要素が小さい順に k 番目の要素が配置される】❗
- 小課題：nth_element の使用方法とテクニックについてはリンクを参照
-
- 方法の比較
- 解法 1：完全なソート
- 解法 2：不完全なソートで、直接 k 番目を得る
- 解法 1：sort メソッド
HZOJ-166：文字列操作 1#
サンプル入力
AAAAAA
2
xxx
サンプル出力
6
AxxxAAAAA
6
- 思考
- 文字列操作と一般的な方法を考察する
- 文字列 B を文字列 A に挿入する
- コード
-
- string クラス
- size()、length()は同じである
- insert
- rfind
- 右から検索を開始するが、返されるのはそのインデックス（正方向）
- このシーンでは、find_last_ofメソッドを使用することもでき、文字列中の任意の 1 文字の一致に注目する。参考にしてstring の find と find_first_of の違い—— ギークシェア
- 小課題：string のさらなる使用法についてはリンクを参照
-
HZOJ-216：名前を取得してソート#
サンプル入力
5
Mr.DMY
Mr.ZY
Mr.LYH
Ms.Grace
Mr.Bill
サンプル出力
Bill
DMY
Grace
LYH
ZY
- 思考
- sort を使用することができる
- map 構造を使用することもでき、底層は赤黒木で、デフォルトで key でソートされる
- コード
-
- map を使用
- イテレータ iter の使用を理解し、->first は key、->second は value を表す
- 注意
- 名前を最初に切り取る必要がある
- value 値はカウントに使用され、名前が重複する可能性がある
-
HZOJ-287：果物を合併する#
サンプル入力
3
1 2 9
サンプル出力
15
- 思考
- 最初は小さくすることが重要なので、最小ヒープを使用することができる
- 小課題：果物の合併とハフマン符号化の関係について議論する。詳細はリンクを参照
- コード
- priority_queue
- これはテンプレートで、<> 内にはすべての型が入る。デフォルトでは最大ヒープ
- 最小ヒープに変更するには、まずコンテナ型を定義する必要がある：vector；その後、
- 方法 1：CMP クラスを定義し、() 演算子をオーバーロードして、呼び出し可能なオブジェクト（すなわち、関数オブジェクト）として使用できるようにする
- 方法 2、方法 3：テンプレートクラスを使用し、後で学ぶ
HZOJ-256：王様のゲーム#
サンプル入力
3
1 1
2 3
7 4
4 6
サンプル出力
2
- 思考
- 目標：最小の最大値を求める
- アルゴリズムは考える：微小擾乱
- すべての人の左手の数字の列を $a_0,a_1,a_2,...,a_i,...,a_n$ とし、
- すべての人の右手の数字の列を $b_0,b_1,b_2,...,b_i,...,b_n$ とし、
- その大臣の前にいるすべての人の左手の数の積を $A_{i-1}=a_0*...*a_{i-1}$ とする。
- すると
- 各大臣が得る金貨の数は $G_i=A_{i-1}/b_i$
- ある配置 1があると仮定すると
- $G_1,G_2,...,[G_{i-1},G_i],...,G_n$、ここで $G_i$ が最大である
- このとき、隣接する 2 人の大臣の位置を交換すると、配置 2が生成される
- $G_1,G_2,...,[G_{i}^{'},G_{i-1}^{'}],...,G_n$
- ❗ 配置 1 と配置 2 のどちらが目標に近いか？変化する金貨の数 $G_{i}^{'},G_{i-1}^{'}$ と最大の金貨数 $G_i$ の関係に注目する。もし両方とも小さい場合、配置 2 が目標に近い
- 分析
- 交換された 2 人の大臣の金貨数だけが変化する
- 既知：$G_i=A_{i-1}/b_i$
- 交換後：$G_{i}^{'}=A_{i-2}/b_i$、$G_{i-1}^{'}=A_{i-2}*a_i/b_{i-1}$
- 明らかに $G_{i}^{'}<G_{i}$、
- もし $G_{i-1}^{'}<G_i$ も成立すれば、配置 2 が目標に近い。すなわち
- $G_{i-1}^{'}<G_i$
- ↓
- $A_{i-2}*a_i/b_{i-1}<A_{i-1}/b_{i}$
- ↓
- $A_{i-2}*a_i/b_{i-1}<A_{i-2}*a_{i-1}/b_{i}$
- ↓
- $a_i*b_{i}<a_{i-1}*b_{i-1}$
- 交換された 2 人の大臣の金貨数だけが変化する
- 👉大臣の位置を交換する条件：
- $a_i*b_{i}<a_{i-1}*b_{i-1}$
- コード
- アルゴリズム：微小擾乱の考えに基づいて、ソートルールを設計するだけである
- pair 型を使用して左手と右手の数字を整理するのが便利
- 王様は常に最前にいて、ソートには参加しない
- ⭐データ構造：大きな整数
- 繰り上がりを処理するメソッドを個別にカプセル化し、乗算と除算のプロセスの最後に 1 回ずつ使用する
- ❓ コンストラクタ内で直接push_back () を使用できる。後で学ぶことに注目
- 除算の設計は主に余りを利用し、前導 0 が発生する可能性があるため、処理が必要
- ❓ 小なり記号をオーバーロードするには、メソッドの末尾にconstを追加する必要がある。そうしないと効果がない。vector の小なり比較が優先される可能性がある。具体的な理由は後で学ぶ
- PS：ここでデータ構造とアルゴリズムを本当に分けた。これがオブジェクト指向が手続き型に比べて優れている点でもある
ヒント#
- ただ知っているだけでなく、その理由も知り、さらにその理由の 4、5、6 個を知ることが重要である
- C++ の学習には標準的な答えはなく、互いに議論することが重要である
- cppreferenceを確認することを学ぶ
- 推奨
- 書籍：C++ Primer、Effective C++、深く探求する C++ オブジェクトモデル...
- 動画：侯捷先生
- 侯捷から C++ を学び、スキルを全方位で向上させる ——C++ 開発エンジニア（2016）
- リンク：https://pan.baidu.com/s/1G7v0w4nH64SVH1FpE5czzQ
- 提取コード：y8tu