0 從C到C++

C++ 比 C 難學，究竟難在哪裡？
感性認識一下 C++ 的美？

課程內容#

問：為什麼以C++ 11標準作為學習重點？

答：C++ 03 到 11 變化很大，而 11 到 14、17 變化很小，20 標準很新，還不普遍，所以從 C++ 11 標準入手是非常好的選擇。

C++ 的語言特性#

主要特性#

頭文件：130 個（C 語言：29 個）
STL
類和對象
模板
Lambda（C++ 11）
異常處理（C++ 11）

解讀#

頭文件非常多，不能以啃頭文件作為學習方式
STL

本來不屬於標準頭文件，惠普實驗室的大佬們開發的，C++ 後來將其納入

面向對象（類和對象）
泛型編程（模板）：開發一個函數，相當於開發一百個函數
函數式編程（Lambda）

相比 C 語言的面向過程編程範式，C++ 增加了 3 種編程範式，工程項目中，一般同時使用 1～2 種編程範式，面向過程和面向對象較常用
新編程範式的本質作用：提高開發效率
- 不同的編程範式對應不同的開發效率，開發效率考慮寫代碼 + 測試 + 維護的時間
- 越往後，開發效率可能更高，但寫代碼難度也更高
- 使用新編程範式的主要情景：可以提高開發效率
PS：C 也可以實現面向對象範式，參考微軟的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

基於紅黑樹 [有序]

PS：

外在表現類似數組，但功能更強大
find (key)：如果找不到，返回 end () [哈希表的結束位置]

代碼演示#

strlen 與 length () 的比較#

耗時有略微差異，但差異不大，原來環境可能對 strlen 有優化
- 參考for (i=0; i<strlen (s); i++) 會每次都執行一遍 strlen 嗎？—— 知乎
c_str()—cppplus

map 和 unordered_map 的比較#

迭代器的使用先感受下，類型定義明確標明，後面可用 auto 關鍵字代替❗
有序性體現在遍歷元素時
- unordered_map 對於 key 和 value 都無序，而且還會打亂原始順序
- map 可當成排序工具
  - auto 關鍵字的使用
    - 對比前面完整的迭代器類型定義，先感受下
    - 很強大，有點像 cin 和 scanf 的區別，可以自動判斷 iter 的類型
  - 排序結果
    - 雖然看著有點像計數排序，但不是
    - 時間複雜度涉及底層紅黑樹：O (NlogN)

sort#

展示了 C++ 的 4 種編程範式
CMP () 為可調用對象
lamda 表達式為 C++11 新推出的
這裡 struct 和 class 有什麼區別，參考深度理解：struct 和 class 的區別—— 博客

隨堂練習#

HZOJ-245：貨倉選址#

範例輸入

5
1 3 5 6 10

範例輸出

思路
- 注意：輸入可能是亂序
- 問題轉換
  - 隨機選擇一個點 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 位

HZOJ-166：字符串操作 1#

範例輸入

AAAAAA
2
xxx

範例輸出

6
AxxxAAAAA
6

思路
- 考察字符串操作和常用方法
- 將字符串 B 插入到字符串 A 裡面
代碼
- string 類
  - size()、length()是一樣的
  - insert
  - rfind
    - 從右邊開始查找，但返回的是其下標（正向的）
    - 在這個場景裡，也可以使用find_last_of方法，關注字符串中任意一個字符的匹配，參考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

範例輸出

思路
- 一開始越小越好，所以可以使用最小堆
- 小作業：討論合併果子和哈夫曼編碼之間的關係，見鏈接
代碼
- priority_queue
  - 它是一個模板，<> 裡放的都是類型，默認為最大堆
  - 若要改為最小堆，需要先定義容器類型：vector；然後，
    - 方式一：定義 CMP 類，重載 () 運算符，使其可以被當成可調用對象（即仿函數、函數對象）
    - 方式二、方式三：使用模板類，後續再學

HZOJ-256：國王遊戲#

範例輸入

範例輸出

思路
- 目標：求最小的最大值
- 算法是想：微擾
  - 令
    - 所有人左手上的數字序列為 $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$ 最大
  - 此時若調換相鄰的兩位大臣的位置，即 $(a_{i-1},b_{i-1})$ 和 $(a_i,b_i)$，會產生新的排列 2
    - $G_1,G_2,...,[G_{i}^{'}，G_{i-1}^{'}],...,G_n$
    - ❗ 排列 1 和排列 2 哪個更接近目標呢？只需要關注發生改變的金幣數 $G_{i}^{'},G_{i-1}^{'}$ 和最大的金幣數 $G_i$ 的關係。如果均為小於關係，則排列 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}$
  - 👉大臣交換位置的條件：
    - $a_i*b_{i}<a_{i-1}*b_{i-1}$
代碼
- 算法：基於微擾的思想，設計出排序規則即可
  - 使用 pair 對類型方便組織左、右手上的數字
  - 國王一直在最前，不參與排序
- ⭐數據結構：大整數
  - 單獨封裝一個處理進位的方法，乘法和除法過程結尾都使用一次
  - ❓ 構造函數裡可以直接使用 push_back ()，後續學習關注
  - 除法的設計，主要利用餘數，可能產生前導 0，要處理
  - ❓ 重載小於號需要在方法末尾添加const，否則不生效，可能會優先使用 vector 的小於比較，具體原因後續學習
- PS：這裡真正將數據結構和算法分開了，這也是面向對象相比面向過程的優勢

Tips#

不僅要知其然，還要知其所以然，更要知其四五六個所以然
C++ 的學習沒有標準答案，多互相討論
學會查看cppreference
推薦
- 書籍：C++ Primer、Effective C++、深度探索 C++ 對象模型...
- 視頻：侯捷老師
  - 跟侯捷學 C++ 全方位提升技能素養 ——C++ 開發工程師（2016）
  - 鏈接：https://pan.baidu.com/s/1G7v0w4nH64SVH1FpE5czzQ
  - 提取碼：y8tu