C++高性能編程

本書共分為14 章，包括C++概述，C++必b備技能，分析和度量性能，數據結構，算法，範圍和視圖，記憶體管理，編譯時編程，Utilities 基礎，代理物件和惰性求值，併發，協程和惰性生成器，用協程進行非同步編程和平行算法。

本書期望你具備基本的C++和計算機體系結構知識，並對提升自身專業技能真正感興趣。希望閱讀本書後，能對如何在性能和語法上改進自己的C++代碼有更深入的認識。

序
前言

第1章 C++概述 1
1.1 為什麼是C++ 1
1.1.1 零成本抽象 · 1
1.1.2 可攜性 · 4
1.2 與其他語言對比 4
1.2.1 競爭語言和性能 · 5
1.2.2 與性能無關的C++語言特性 · 7
1.2.3 C++的局限性 12
1.3 本書使用的庫和編譯器 13
1.4 總結 13

第2章 C++必備技能 · 14
2.1 用auto 關鍵字進行自動類型推斷 14
2.1.1 在函數簽名中使用auto 14
2.1.2 對變數使用auto 16
2.1.3 指針的常量傳播 18
2.2 移動語義 19
2.2.1 拷貝構造函數，交換與移動 20
2.2.2 資源獲取與五法則 22
2.2.3 具名變數和右值 25
2.2.4 默認移動語義和零法則 27
2.2.5 將&&修飾符應用于類成員函數 ·32
2.2.6 當拷貝被省略時，無論如何都不要移動 32
2.2.7 適時使用值傳遞 33
2.3 設計帶有錯誤處理的介面 35
2.3.1 契約 36
2.3.2 錯誤處理 39
2.4 函數對象和lambda 運算式 46
2.4.1 C++lambda 的基本語法 46
2.4.2 捕獲子句 47
2.4.3 為lambda 運算式分配C 函數指針 · 53
2.4.4 Lambda 類型 · 54
2.4.5 lambda 運算式和std::function · 54
2.4.6 泛型lambda 58
2.5 總結 60

第3章 分析和度量性能 · 61
3.1 漸進複雜度和大O 符號 61
3.1.1 增長率 66
3.1.2 均攤時間複雜度 67
3.2 度量什麼？該如何度量？ 69
3.2.1 性能特徵 71
3.2.2 執行時間的提升 71
3.2.3 性能計數器 72
3.2.4 最佳實踐：性能測試 73
3.3 瞭解代碼和熱點 74
3.3.1 插樁型剖析器 75
3.3.2 採樣型剖析器 77
3.4 微基準測試 79
3.4.1 阿姆達爾定律 80
3.4.2 微基準測試的隱患 81
3.4.3 微基準測試實例 81
3.5 總結 87

第4章 數據結構 · 88
4.1 電腦記憶體的特性 88
4.2 標準庫容器 92
4.2.1 序列式容器 92
4.2.2 關聯式容器 96
4.2.3 容器適配器 ·100
4.3 使用視圖 103
4.4 性能方面的考量 106
4.4.1 在複雜度與開銷間尋求平衡 · 106
4.4.2 瞭解並使用適當的API 函數 107
4.5 並行數組 108
4.6 總結 115

第5章 算法 116
5.1 標準庫算法概述 116
5.1.1 標準庫算法的演進 · 116
5.1.2 解決日常問題 · 117
5.2 反覆運算器與範圍 124
5.2.1 反覆運算器 · 124
5.2.2 哨兵值與past-the-end 反覆運算器 125
5.2.3 範圍 · 126
5.2.4 反覆運算器類別 · 127
5.3 標準算法的特點 129
5.4 算法不會改變容器大小 129
5.4.1 有輸出的算法需要自己分配數據 · 130
5.4.2 算法預設使用operator==()和operator<() 131
5.4.3 使用projection 的約束算法 132
5.4.4 算法要求move 不能拋出異常 133
5.4.5 算法具有複雜度保證 · 133
5.4.6 算法的性能與C 語言庫中的等價函數一樣好 134
5.5 編寫和使用泛型算法 135
5.5.1 非泛型算法 · 135
5.5.2 泛型算法 · 136
5.5.3 可被泛型算法使用的數據結構 · 137
5.6 最佳實踐 139
5.6.1 使用約束算法 · 139
5.6.2 只對需要檢索的數據進行排序 · 139
5.6.3 使用標準算法而非原始for 迴圈 142
5.6.4 避免容器拷貝 · 148
5.7 總結 149

第6章 範圍和視圖 150
6.1 Ranges 庫的動機 · 150
6.2 理解Ranges 庫中的視圖 · 153
6.2.1 視圖是可組合的 ·154
6.2.2 範圍視圖帶有範圍適配器 ·155
6.2.3 視圖是具有複雜度保證的非具權範圍 ·156
6.2.4 視圖不改變底層容器 ·157
6.2.5 視圖可以被具體化為容器 ·157
6.2.6 視圖是惰性求值的 ·158
6.3 標準庫中的視圖 160
6.3.1 範圍視圖 ·160
6.3.2 生成視圖 ·160
6.3.3 轉換視圖 ·160
6.3.4 再談std::string_view 與std::span 162
6.4 Ranges 庫的未來 · 164
6.5 總結 164

第7章 記憶體管理 165
7.1 電腦記憶體 165
7.1.1 虛擬位址空間 ·165
7.1.2 記憶體頁 ·166
7.1.3 抖動 ·167
7.2 進程記憶體 167
7.2.1 棧記憶體 ·168
7.2.2 堆記憶體 ·171
7.3 記憶體中的物件 172
7.3.1 創建與銷毀對象 ·172
7.3.2 記憶體對齊 ·176
7.3.3 記憶體補齊 ·179
7.4 記憶體所有權 182
7.4.1 隱式處理資源 ·183
7.4.2 容器 ·185
7.4.3 智能指針 ·185
7.5 小對象優化 188
7.6 自訂記憶體管理 191
7.6.1 創建arena 192
7.6.2 自訂記憶體分配器 · 196
7.6.3 使用多態記憶體分配器 · 201
7.6.4 實現自訂記憶體資源 · 205
7.7 總結 207

第8章 編譯時編程 208
8.1 範本元編程介紹 208
8.2 創建範本 209
8.3 使用整數作為範本參數 211
8.4 提供範本的特化 212
8.5 編譯器如何處理範本函數 212
8.6 縮寫函數範本 213
8.7 使用decltype 接收變數類型 214
8.8 類型萃取 215
8.8.1 類型萃取的類別 · 215
8.8.2 類型萃取的使用 · 216
8.9 常量運算式的使用 217
8.9.1 運行時環境中的constexpr 函數 218
8.9.2 使用consteval 聲明即時函數 219
8.9.3 編譯時多態與運行時多態 · 222
8.9.4 示例：使用if constexpr 的泛型取模函數 223
8.10 編譯時檢查程式錯誤 224
8.10.1 利用assert 在運行時觸發錯誤 224
8.10.2 利用static_assert 在編譯時觸發錯誤 · 225
8.11 約束與概念 226
8.11.1 Point2D 範本，無約束版 · 226
8.11.2 泛型介面與不友好的報錯資訊 227
8.11.3 約束和概念的語法 229
8.11.4 標準庫中的概念 234
8.12 元編程實例 235
8.12.1 示例1：創建通用的安全強制轉換函數 235
8.12.2 示例2：在編譯時對字串進行雜湊處理 238
8.13 總結 · 245

第9章 Utilities 基礎 · 246
9.1 用std::optional 表示可選值· 246
9.1.1 可選的返回值 ·247
9.1.2 可選的成員變數 ·248
9.1.3 避免在枚舉中使用空狀態 ·248
9.1.4 std::optional 的排序與比較 249
9.2 固定大小的異質集合 250
9.2.1 std::pair 250
9.2.2 std::tuple 251
9.2.3 訪問元組中的成員 ·252
9.2.4 遍歷std::tuple 的元素 ·253
9.2.5 元組展開 ·254
9.2.6 為元組實現其他算法 ·255
9.2.7 元組元素訪問 ·256
9.2.8 結構化綁定 ·257
9.3 可變參數範本 258
9.4 可動態調整大小的異質集合 261
9.4.1 std::variant 262
9.4.2 std::variant 的異常安全性 264
9.4.3 訪問variant ·265
9.5 使用了variant 的異質集合 · 266
9.5.1 訪問variant 容器中的值 267
9.5.2 全域函數std::get() 268
9.6 實際案例 269
9.6.1 示例1：投影與比較運算子 269
9.6.2 示例2：反射 270
9.7 總結 273

第10章 代理物件和惰性求值 · 274
10.1 惰性求值和代理物件簡介· 274
10.1.1 惰性求值與急切計值 274
10.1.2 代理物件 275
10.2 避免使用代理物件構建物件 276
10.2.1 使用代理比較連接的字串 276
10.2.2 實現代理 277
10.2.3 右值修飾符 278
10.2.4 存儲拼接好的代理物件 279
10.2.5 性能評估 279
10.3 延遲sqrt 計算 280
10.3.1 一個簡單的二維向量類 280
10.3.2 示例背後的數學概念 281
10.3.3 實現LengthProxy · 283
10.3.4 用LengthProxy 比較長度 285
10.3.5 用LengthProxy 計算長度 286
10.3.6 性能評估 287
10.4 探索運算子重載和代理物件 289
10.5 總結 291

第11章 併發 · 292
11.1 瞭解併發的基本概念 292
11.2 是什麼讓併發編程變得困難？ 293
11.3 併發和並行 293
11.3.1 時間切片 294
11.3.2 共用記憶體 295
11.3.3 數據競爭 296
11.3.4 互斥鎖 298
11.3.5 鎖死 299
11.3.6 同步任務與非同步任務 299
11.4 C++中的併發編程 · 300
11.4.1 執行緒支援函式庫 301
11.4.2 C++20 中其他的同步原語 315
11.4.3 C++中的原子操作 326
11.4.4 C++記憶體模型 335
11.5 無鎖編程 339
11.6 性能指南 341
11.6.1 避免競爭 341
11.6.2 避免阻塞操作 342
11.6.3 執行緒/CPU 核數 ·342
11.6.4 執行緒優先順序 343
11.6.5 執行緒親和性 343
11.6.6 偽共用 344
11.7 總結 · 345

第12章 協程和惰性生成器 · 346
12.1 幾個引人入勝的例子 · 347
12.2 協程抽象 · 348
12.2.1 子常式和協程 349
12.2.2 在CPU 上運行子常式和協程 350
12.2.3 無棧協程和有棧協程 358
12.2.4 目前為止所學的內容 360
12.3 C++中的協程 · 360
12.3.1 標準C++中協程的涵蓋內容 361
12.3.2 C++函數成為協程的關鍵是什麼？ ·361
12.3.3 一個最簡但完整的示例 363
12.3.4 分配協程狀態 368
12.3.5 避免懸空引用 370
12.3.6 錯誤處理 375
12.3.7 自訂點 375
12.4 生成器 · 376
12.4.1 實現生成器 376
12.4.2 使用Generator 類 ·380
12.4.3 在實際工作中使用生成器 387
12.5 性能 · 395
12.6 總結 · 395

第13章 用協程進行非同步編程 · 396
13.1 再談可等待類型 · 396
13.2 實現一個基本任務類型 · 398
13.2.1 處理返回值和異常 401
13.2.2 恢復等待中的協程 402
13.2.3 支持void Task 404
13.2.4 同步等待任務完成 406
13.2.5 使用sync_wait()測試非同步任務 411
13.3 封裝基於回檔的API · 412
13.4 使用Boost.Asio 實現的併發伺服器 416
13.4.1 實現伺服器 416
13.4.2 運行並連接伺服器 418
13.4.3 在伺服器示例中實現的（以及未實現的）功能 419
13.5 總結 420

第14章 平行算法 · 421
14.1 並行的重要性 421
14.2 平行算法 421
14.2.1 度量平行算法 422
14.2.2 回顧阿姆達爾定律 423
14.2.3 實現並行std::transform() · 424
14.2.4 並行化std::count_if() 434
14.2.5 並行化std::copy_if() 435
14.3 標準庫中的平行算法 441
14.3.1 執行策略 442
14.3.2 異常處理 446
14.3.3 平行算法的新增和修改 447
14.3.4 並行化基於索引的for 迴圈 449
14.4 在GPU 上執行算法 450
14.5 總結 451
14.6 分享經驗 452