Code Snippet

/* Template Begin */
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <time.h>
#include <cmath>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <functional>
#include <iterator>
#include <tuple>
#include <complex>
#include <limits.h>
#include <stack>
#include <sstream>
using namespace std;
/* Template End */

ctype.h

limits.h

math.h

Trigonometric Functions

註：這些 三角函數 輸入均為 浮點數，默認使用 弧度作為單位。

Hyperbolic Functions

Exponential and Logarithmic Functions

Power Functions

Rounding and Remainder Functions

Other Functions

Classification Macro/Functions

Comparison Macro/Functions

stdio.h

Formatted Input/Output

Macros

stdlib.h

String Conversion

Pseudo-Random Sequence Generation

Dynamic Memory Management

Searching and Sorting

string.h

Copying

Concatenation

Comparison

Searching

Other

time.h

Time Manipulation

Conversion

Containers

vector

queue

deque

stack

list

set

map

unordered_map

unordered_set

Other Libraries

Code Snippets

Initialize the Array with Fixed-Element

• 定義時 使用 列表初始化

  int arr[10] = {1,2,3};

1 2 3 0 0 0 0 0 0 0

列表初始化 會 列表的元素填充到 數組的前幾個元素，數組的剩余元素一律 填0

• 使用 memset進行 內存字符填充

  int arr[10];
  memset(arr, 0, sizeof(array));

0 0 0 0 0 0 0 0 0 0

註意：該種方法只能用於填充 0和 -1

• 利用 全局變量自動 初始化填0的特性

int arr[10];
int main() {
  for (int i = 0; i < 10; ++i) {
    printf("%d ", arr[i]);
  }
  return 0;
}

0 0 0 0 0 0 0 0 0 0

• 使用 fill() 填充函數

  int arr[10];
  fill(arr, arr + 10, 2022);

2022 2022 2022 2022 2022 2022 2022 2022 2022 2022

fill_n() 只用 指定值 填充 前n個元素

int arr[10];
fill_n(arr, 3, 2020);

2020 2020 2020 0 8 0 75 0 16875376 0

Initialize the Array with Generated-Element

• 使用 generate() 生成函數

  int arr[10];
  generate(arr, arr + 10, []() { return rand() % 5; });

1 2 4 0 4 4 3 3 2 4

如果需要讓 generate() 保存 狀態，則可以利用 靜態局部變量來實現。

用 全局變量也可以，但 靜態局部變量使得 代碼結構更加 緊湊

  int arr[10];
  generate(arr, arr + 10, []() {
      static int i = 1;
      return i *= 2;
  });

2 4 8 16 32 64 128 256 512 1024

Generate Lexicographical-Permutation

• 使用 next_permutation()

  string words = "abc";
  do {
    cout << words << endl;
  } while (next_permutation(words.begin(), words.end()));

abc
acb
bac
bca
cab
cba

同理，prev_permutation()則是 生成上一個排列

相關輔助函數：is_permutation()

Hash Function

• 使用 hash結構體模板

  hash<string> string_hash;
  string first_words = "abc";
  string second_words = "cba";

  printf("hash(first_words) = %lld", string_hash(first_words));
  printf("\n");
  printf("hash(second_words) = %lld", string_hash(second_words));

hash(first_words) = 3663726644998027833
hash(second_words) = -4830583261295167161

Find the Index of A Specific Element

• 使用 find()

  int arr[] = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90};
  int index = find(arr, arr + 10, 70) - arr;
  printf("index = %d", index);

index = 7

• 使用 find_if()

  int arr[] = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90};
  int index = find_if(arr, arr + 10, [](const auto &obj) {
      return obj != 0 && obj % 15 == 0;
  }) - arr;
  printf("index = %d", index);

index = 3

Find the Index of A Subsequence

• 使用 find_first()

  int arr[] = {0, 30, 40, 50, 10, 20, 30, 40, 50, 60, 70, 80, 90};
  int needle[] = {30, 40, 50};
  int index = find_first_of(arr, arr + 13, needle, needle + 3) - arr;
  printf("index = %d", index);

index = 1

find_first_of() ：返回 第一個相等的子序列的 首元素下標

find_end()：返回 最後一個相等的子序列的 首元素下標

• 使用 search()

  int arr[] = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90};
  int needle[] = {30, 40, 50};
  int index = search(arr, arr + 10, needle, needle + 3) - arr;
  printf("index = %d", index);

index = 3

search返回的是 第一個滿足條件的元素

默認的 search()使用的是 相等謂詞，我們也可以自定義 二元相等謂詞

int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int needle[] = {9, 16, 25};
int index = search(arr, arr + 10, needle, needle + 3, [](const auto &o1, const auto &o2) {
 return o1  * o1 == o2;
}) - arr;
printf("index = %d", index);

index = 3

此外，如果我們的 子序列是 相同元素組成的指定長度的子序列，則可以直接使用 search_n()

int arr[] = {0, 1, 2, 9, 9, 5, 6, 7, 8, 9, 10};
int index = search_n(arr, arr + 10, 2, 9) - arr;
printf("index = %d", index);

index = 3

Find in Two-Consecutive Elements

• 使用 find_adjacent()

  int arr[] = {0, 10, 20, 20, 40, 50, 60, 70, 80, 90};
  int index = adjacent_find(arr, arr + 10, [](const auto &o1, const auto &o2){
    return o1 == o2;
  }) - arr;
  printf("index = %d", index);

index = 2

Count the number of elements for which predicate is true

• 使用 count_if()

  int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  int cnt = count_if(arr, arr + 10, [](const auto &o1) {
      return o1 % 2 == 0;
  });
  printf("cnt = %d", cnt);

cnt = 5

Return the First Position where Two Ranges differs

  int arr[] = {0, 1, 2, 30, 4, 5, 6, 7, 8, 9};
  int needle[] = {0, 1, 2};
  pair<int *, int *> ret = mismatch(arr, arr + 10, needle);
  printf("ret->first = %d", ret.first - arr);
  printf("\n");
  printf("ret->second = %d", ret.second - needle);

ret->first = 3
ret->second = 3

mismatch() 默認使用的 二元相等謂詞 就是 operator=。

如果需要，可以自定義 二元相等謂詞

equal() 與 mismatch()類似，但它只返回 是否相等

Test For-All and Exist

• 使用 all_of()

  int arr[] = {0, 2, 4, 6, 8, 10};
  bool flag = all_of(arr, arr + 6, [](const auto&o1){
    return o1 % 2 == 0;
  });
  cout << flag;

1

any_of()同理，它可以測試是否有 任何一個元素滿足 條件。

none_of() 可以用 all_of() 取反來實現。

Apply function to range

• 使用 for_each()

  int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  for_each(arr, arr + 10, [](const auto & o1){
    cout << o1 * o1 << " ";
  });

0 1 4 9 16 25 36 49 64 81

Remove Duplicates

• 使用 sort() 配合 unique()

  int arr[] = {10, 10, 20, 30, 40, 50, 10, 60, 70, 80};
  unique(arr, arr + 10);
  for (int i = 0; i < 10; ++i) {
    printf("%d ", arr[i]);
  }

10 20 30 40 50 10 60 70 80 80

n.b. unique() 的 語義並不是 去除序列的重復元素，而是 去除序列的連續的重復元素 (只保留一個相同元素)。

上述例子中只有 連續的10被去除。

如果確實要去除 序列中所有的重復元素，則應當先 sort()使得 所有的相同元素是 連續排列的，再使用 unique()

該函數也有 可復製到指定輸出流的版本 unique_copy()

Print Range

• 使用 for_each()

  int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  for_each(arr, arr + 10, [](const auto &item) {
      cout << item << " ";
  });

• 使用 copy()

  copy(arr, arr + 10, ostream_iterator<int>(cout, " "));

Copy range of elements

• 使用 copy()

  int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  int dest[10];
  copy(arr, arr + 10, dest);

可以使用 帶謂詞的版本 copy_if()

如果需要 反向遍歷，可以使用 copy_backward()

Move range of elements

• 使用 move()

  int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  move(arr, arr + 2, arr + 3);

0 1 2 0 1 5 6 7 8 9

move()方法允許 目標內存區域和 來源內存區域發生 重疊。

但是，move()不保證 來源內存區域的 內容仍 保持原樣

Transform Range

• 使用 transform()

  int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  transform(arr, arr + 10, arr, [](const auto & o1){
    return o1 * o1;
  });
  copy(arr, arr + 10, ostream_iterator<int>(cout, " "));

0 1 4 9 16 25 36 49 64 81

transform()可以指定 輸出目標流，並且允許 輸出目標流和 輸入流發生 重疊。

有點類似 for_each()，但 for_each()經常用於 非修改性操作，而 transform() 用於 修改性操作

Replace Values in Range

• 使用 replace()

  int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  replace(arr, arr + 10, 3, 3000);

0 1 2 3000 4 5 6 7 8 9

可以使用 帶謂詞版本的 replace_if()來替代 replace()：只有當 謂詞 測試通過時，才會用 新值 替換 當前元素

• 使用 replace_copy()

  int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  int dest[10];
  replace_copy(arr, arr + 10, dest, 3, 3000);
  copy(arr, arr + 10, ostream_iterator<int>(cout, " "));
  printf("\n");
  copy(dest, dest + 10, ostream_iterator<int>(cout, " "));

0 1 2 3000 4 5 6 7 8 9

相比於 replace()而言，replace_copy()可以指定 修改結果的輸出流。

特別地，replace_copy()可以重新將 輸出流指定為 輸入流

在這個情況下，replace_copy()等價於 replace()

此外，還有一個 帶謂詞版本的 repalce_copy_if()

我們稱它是萬能的替換函數，因為它可以取代：repalce()，replace_if()，replace_copy()

Reverse Range

• 使用 reverse()

  int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  reverse(arr, arr + 10);

9 8 7 6 5 4 3 2 1 0

可復製到指定輸出流的版本 reverse_copy()

Rotate left the elements in range

• 使用 rotate()

  int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  rotate(arr, arr + 3, arr + 10);

3 4 5 6 7 8 9 0 1 2

Rearrange elements in range

• 使用 random_shuffle() 隨機生成函數

  int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  random_shuffle(arr, arr + 10);

8 1 9 2 0 5 7 3 4 6

該方法可用於 洗牌算法

Merge (Operating on Sorted Ranges)

• 使用 set_intersection()

  vector<int> A = {1, 2, 3};
  vector<int> B = {3, 4, 5, 6};
  sort(A.begin(), A.end());
  sort(B.begin(), B.end());
  vector<int> result(10);
  auto it = set_intersection(A.begin(), A.end(), B.begin(), B.end(), result.begin());
  copy(result.begin(), it, ostream_iterator<int>(cout, " "));

3

• 集合交 -> set_union()
• 集合差 -> set_difference()
• 集合對稱差 -> set_symmetric_difference()
• 歸並 -> merge()：歸並操作

相比於 set_union()而言，merge()會 保留多個相同的元素

• 原址性歸並 -> inplace_merge()：原址性的歸並操作

    vector<int> arr = {1, 1, 2, 3, 4, 2, 3, 4, 5, 6, 7};
    inplace_merge(arr.begin(), arr.begin() + 5, arr.end());

     1 1 2 2 3 3 4 4 5 6 7

• 測試包含關系 -> includes()

• vector<int> A = {0,1,2,3,4,5,6,7,8,9};
  vector<int> B = {3,4,5,6};
  cout << includes(A.begin(), A.end(), B.begin(), B.end());
  printf("\n");
  cout << includes(B.begin(), B.end(), A.begin(), A.end());
  

  1
  0
  

n.b. 上述的 所有的歸並操作在使用之前，都需要用 sort() 對 集合A 和 集合B 進行 預處理。

否則將導致輸出結果的錯誤。

Min/Max

• 最小元素/最大元素 -> min_element() 和 max_element()

     vector<int> v = {3, 5, 2, 7, 1, 9, 4};
     int index = min_element(v.begin(), v.end()) - v.begin();
     printf("%d ", index);
  

     4
  

  minmax_element()返回一個 (最小值叠代器，最大值叠代器)的 二元組

Heap

堆操作函數將一個 數組維護 堆結構，但除此之外，我們還需要一個 表示堆大小的整數。

n.b. 數組的大小 不一定等於 堆的大小，我們有可能 只使用數組中的一部分連續區域 來構成 堆

n.b. 使用 數組時需要 額外維護一個表示堆大小的整數。但如果使用的是 vector，則可以 在每次堆操作後手動地 維護vector，使得 vector的大小始終與 heap的大小 相等。

與 Java的是，C++的 Heap默認是 最大堆，同理，基於Heap的PriorityQueue也默認是 最大優先隊列

• make_heap()

      vector<int> v = {5, 6, 8, 2, 3, 9, 1, 7, 0, 4};
      make_heap(v.begin(), v.end());
      copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
  

    9 7 8 6 4 5 1 2 0 3
  

• pop_heap()

      vector<int> v = {5, 6, 8, 2, 3, 9, 1, 7, 0, 4};
      make_heap(v.begin(), v.end());
      copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
      printf("\n");
  
      pop_heap(v.begin(), v.end());
      v.pop_back();
      copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
  

    9 7 8 6 4 5 1 2 0 3
    8 7 5 6 4 3 1 2 0
  

• push_heap()

      vector<int> v = {5, 6, 8, 2, 3, 9, 1, 7, 0, 4};
      make_heap(v.begin(), v.end());
      copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
      printf("\n");
  
      v.push_back(10);
      push_heap(v.begin(), v.end());
      copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
  

    9 7 8 6 4 5 1 2 0 3
    10 9 8 6 7 5 1 2 0 3 4
  

除此之外，還有一些 輔助操作。

• sort_heap()

      vector<int> v = {5, 6, 8, 2, 3, 9, 1, 7, 0, 4};
      make_heap(v.begin(), v.end());
      copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
      printf("\n");
  
      sort_heap(v.begin(), v.end());
      copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
  

    9 7 8 6 4 5 1 2 0 3
    0 1 2 3 4 5 6 7 8 9
  

• is_heap()

      vector<int> v = {5, 6, 8, 2, 3, 9, 1, 7, 0, 4};
      make_heap(v.begin(), v.end());
      copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
      printf("\n");
  
      cout << is_heap(v.begin(), v.end());
  

    9 7 8 6 4 5 1 2 0 3
    1
  

大部分情況下，如果需要使用 優先隊列可以首先考慮 priority_queue。

但如果需要一些更底層的操作，可以使用 heap functions

Binary Search

• 下界函數/上界函數

  vector<int> v = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  int ret1 = lower_bound(v.begin(), v.end(), 3) - v.begin();
  int ret2 = upper_bound(v.begin(), v.end(), 3) - v.begin();
  printf("lower_bound = %d ", ret1);
  printf("\n");
  printf("upper_bound = %d ", ret2);

lower_bound = 3
upper_bound = 4

n.b. lower_bound()和 upper_bound()的 語義 可能直觀上和 名稱不同。

但實際上， lower_bound()指的是 not less than

而 upper_bound() 指的是 greater than

• binary_search()

  vector<int> v = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  bool found = binary_search(v.begin(), v.end(), 3);
  printf("found = %d", found);

found = 1

如果 已知序列是有序的，則可以用 binary search代替 linear search來獲得更高的效率。

但是，如果需要獲取 下標，則需要使用 lower_bound()來進行 二分查找

盡管C標準庫確實有一個 bsearch()函數，但該函數原型對於C++的很多數據結構來說，並不適合。

• equal_range()

      vector<int> v = {0, 1, 2, 3, 3, 5, 6, 7, 8, 9};
      auto ret = equal_range(v.begin(), v.end(), 3);
      printf("first = %d\n", ret.first - v.begin());
      printf("second = %d\n", ret.second - v.begin());
  

    first = 3
    second = 5
  

  需要在 有序序列中查找 一段連續的相同的元素的 下標範圍，則可以使用 equal_range()

Sorting

• sort()：快速排序，非穩定性的

• stable_sort()：穩定性的排序

• partial_sort()：劃分排序，可以按照 基準元素將 序列 進行 劃分為 兩個部分

• is_sorted()：判斷 序列是否所有元素滿足 偏序關系

  通常情況下，我們定義的 偏序關系也就是 operator <。

  在這個意義上，is_sorted() 默認是 判斷序列是否升序，

  如果希望判斷 序列是否是降序的，可以利用 反向叠代器來實現。

     vector<int> increase = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
     vector<int> decrease = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
     cout << is_sorted(increase.begin(), increase.end()) << endl;
     cout << is_sorted(decrease.begin(), decrease.end()) << endl;
     cout << is_sorted(decrease.rbegin(), decrease.rend());
  

     1
     0
     1
  

• nth_element()

      vector<int> v = {4, 7, 6, 8, 9, 2, 1, 3, 5};
      nth_element(v.begin(), v.begin() + 1, v.end());
      copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
  

    1 2 4 3 5 6 7 9 8
  

  nth_element()可以使得 序列中指定位置的值為 排序該序列後該位置放置的元素。

  但除了讓 指定位置為排序後的序列應放置的元素之外， 其他位置的元素可能會受到 位置改變的副作用

Partitions

• partition()

      vector<int> v = {5, 3, 7, 4, 2, 9, 0, 8, 1};
      int ret = partition(v.begin(), v.end(), [](const auto&o1){
        return o1 < 4;
      }) - v.begin();
      copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
      printf("\nthe index of the first element in the second group: %d", ret);
  

    1 3 0 2 4 9 7 8 5
    the index of the first element in the second group: 4
  

  partition() 劃分函數 將 序列按照 一元謂詞劃分為 2個部分：

  • 第1部分：滿足謂詞的元素
  • 第2部分：不滿足謂詞的元素

  它的返回值是 第2部分的第一個元素的下標

  n.b. 我們可以發現，STL中很多關於 2劃分 所返回的下標，均遵循 the index of the first element in the second group的原則。

  同樣地，類似的規律有 取頭不取尾的區間表示方法 [begin, end)

  變種版本：partition_copy()，stable_partition()

• is_partitioned()

• partition_point()

     vector<int> v = {5, 3, 7, 4, 2, 9, 0, 8, 1};
     int ret = partition(v.begin(), v.end(), [](const auto &o1) {
        return o1 < 4;
     }) - v.begin();
     copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
     printf("\nthe index of the first element in the second group: %d", ret);
     // partition_point()
     auto point = partition_point(v.begin(), v.end(), [](const auto &o1) {
        return o1 < 4;
     });
     printf("\n");
     for (auto iter = v.begin(); iter != point; iter++) {
      printf("%d ", *iter);
     }
  

     1 3 0 2 4 9 7 8 5
     the index of the first element in the second group: 4
     1 3 0 2
  

  可用於 反求 劃分的分割點的叠代器

Bitset

位圖 (bitset) 是C++ 容器庫之外的一個數據結構，它用 1個二進製位表示 1個邏輯型變量。

相比於 char (8-bit)而言，更 節約空間。

更重要的是，bitset提供了一些方便的 數據操作函數和 數據查詢函數，以及對 字符串輸出的支持。

• 數據操作函數

  • 置位 (set)：將 指定下標的位設置為 1
  • 復位 (reset)：將 指定下標的位設置為 0
  • 翻轉 (flip)：將 指定下標的位進行 翻轉

• 數據查詢函數

  • 測試 (test)：返回 指定下標的位

  • 計數 (count)：返回 被置位的位數

    • 全部已置位 (all)：是否 所有的位都被 置位
    • 任何已置位 (any)：是否 任何一個位被 置位
    • 沒有已置位 (none)：是否 沒有任何一個位被 置位

  bitset<32> bits;
  bits.set(0,true);
  cout << bits;

00000000000000000000000000000001

在 空間緊張的情況下，bitset<size>可能會優於 vector<bool>。

事實上，這並不一定。因為 vector<bool>和 普通的泛化vector不同，

它是 vector模板的特例化，具體庫實現很有可能針對 vector<bool>做出特別的優化。

但不同於 vector的 動態伸縮， bitset的大小是通過 模板固定的，在編譯期確立和內存空間。

Complex

STL庫提供的 復數實現，同時重載了 運算符。

  complex<int> a = {1,2};
  complex<int> b = {3,4};
  cout << a + b;

(4,6)

Ratio

由C++提供的 比例 (Ratio)庫。可以直接作為 分數庫使用。

  typedef ratio<1, 2> one_half;
  typedef ratio<2, 3> two_thirds;
  ratio_add<one_half, two_thirds> sum;
  printf("fraction: %d/%d", sum.num, sum.den);

fraction: 7/6

他們本質上是 宏，只能在 編譯期確定數值。

Tuple

當需要表示 多種數據類型的有序序列，則可以使用 元組 (Tuple)。

比如如果需要返回 2個返回值時，比起 structure來說，tuple會更加方便

實際上，有另一個東西叫 make_pair()

• Construct Tuple and Get Elements

  tuple<string, int> t1("hello", 100);
  cout << "get<0> = " << get<0>(t1) << endl;
  cout << "get<1> = " << get<1>(t1);

get<0> = hello
get<1> = 100

實際上，比起 構造器而言， 我們更經常使用 make_tuple() 來構造元組。

 auto t2 = make_tuple("hello", "world", 100);

• Use tie() to Unpack Tuple

  auto tuple = make_tuple("hello", "world", 100);

  string str1;
  string str2;
  int num;
  tie(str1, str2, num) = tuple;

  cout << str1 << endl;
  cout << str2 << endl;
  cout << num << endl;

hello
world
100

如果只需要 unpack其中 某些元素，則可以使用 std::ignore來進行 占位

 auto tuple = make_tuple("hello", "world", 100);

 string str1;
 int num;
 tie(str1, std::ignore, num) = tuple;

 cout << str1 << endl;
 cout << num << endl;

Utility

• swap()
• make_pair()
  如果只需要 2元組的情況下，用 make_pair()會比 make_tuple()方便非常多。後者的 accessor用起來比較麻煩。

Accumulate values in range

• 使用 accumulate()

  vector<int> v = {0,1,2,3,4,5,6,7,8,9};
  int sum = accumulate(v.begin(), v.end(), 0);
  cout << sum;

45

accumulate() 不僅僅是用於 累加，它還支持 帶有二元謂詞的版本。

可以利用 二元謂詞來實現 累減，累乘，累除等

 vector<int> v = {1, 2, 3, 4};
 int sum = accumulate(v.begin(), v.end(), 1, [](const auto &o1, const auto &o2) {
    return o1 * o2;
 });
 cout << sum;

 24

Compute adjacent difference of range

• 使用 adjacent_difference()

  vector<int> v = {1,4,6,10};
  adjacent_difference(v.begin(), v.end(), v.begin());
  copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));

1 3 2 4

adjacent_difference() 不但可以用於 差分，還可以進行 和分，積分，商分

 vector<int> v = {1, 4, 6, 10};
 adjacent_difference(v.begin(), v.end(), v.begin(), [](const auto &o1, const auto &o2) {
 return o1 * o2;
 });
 copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));

 1 4 24 60

Compute cumulative inner product of range

• 使用 inner_product()

  int init = 100;
  vector<int> a = {10, 20, 30};
  vector<int> b = {1, 2, 3};
  int ret = inner_product(a.begin(), a.end(), b.begin(), init);
  cout << ret;

240

n.b. 使用 inner_product() 時需要保證 矢量a和 矢量b的 長度相等。

在 兩個矢量的長度不等的情況下，STL仍然會取 較長的矢量進行運算， 而較短的矢量的 越界值將是 不可預測的

可以使用 帶謂詞版本的 inner_product()來模擬 inner_product()

 int init = 100;
 vector<int> a = {10, 20, 30};
 vector<int> b = {1, 2, 3};
 int ret = inner_product(a.begin(), a.end(), b.begin(), init, [](const auto &o1, const auto &o2) {
  return o1 + o2;
 }, [](const auto &o1, const auto &o2) {
    return o1 * o2;
 });

 240

Compute partial sums of range

• 使用 partial_sum()

  vector<int> a = {1, 2, 3, 4, 5};
  partial_sum(a.begin(), a.end(), a.begin());
  copy(a.begin(), a.end(), ostream_iterator<int>(cout, " "));

1 3 6 10 15

同理，使用帶二元謂詞的版本，我們可以實現：部分差，部分乘，部分商

Store increasing sequence

• 使用 iota()

  vector<int> v(10);
  iota(v.begin(), v.end(), 3);
  copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));

3 4 5 6 7 8 9 10 11 12

iota()底層使用 operator++ 運算符來實現 遞增

Function Object

Base Classes

函數對象即利用 結構體/對象的 operator()運算符重載，完成類似 普通函數的 函數調用。

• unary_function()

struct IsOdd {
    bool operator() (int number) {
      return number % 2 != 0;
    }
};

int main() {
  IsOdd function_object;
  cout << function_object(3) << endl;
  cout << function_object(2);
  return 0;
}

1
0

本質上來說，函數對象就是一個 結構體。

 struct IsOdd {
    bool operator() (int number) {
      return number % 2 != 0;
    }
 } function_object;

• binary_function()

int main() {
  struct Add {
      int operator() (int o1, int o2) {
        return o1 + o2;
      }
  } function_object;
  cout << function_object(1, 2) << endl;
  return 0;
}

3

函數對象一般用於 predicate function和 comparison function。

在大部分的場景下，可以用 lambda表達式 代替 函數對象 作為 callable。

Operator Classes

Arithmetic Operation

• plus

    int main() {
      plus<int> function_object;
      cout << function_object(1,2);
      return 0;
    }
  

    3
  

• minus
• multiplies
• divides
• modulus
• negate

上述 算術操作函數對象可以非常方便地用於 transform()

Comparison Operation

• equal_to
• not_equal_to
• greater
• less
• greater_equal
• less_equal

greater和 less經常用於 UDT的 優先隊列定義。

比較器函數的 基本用法可以依據 傳入參數來進行 測試。

但我們也可以 綁定某個 參數為 常數。

 vector<int> v = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
 int cnt = count_if(v.begin(), v.end(), bind2nd(greater<int>(), 3));
 cout << cnt;

 6

Logical Operations

• logical_and
• logical_or
• logical_not

Adaptor and Conversion Functions

Negators

• not1

    struct IsOdd {
        bool operator()(const int &x) const { return x % 2 != 0; }
        typedef int argument_type;
    };
  
    int main() {
      vector<int> v = {0, 2, 4, 6, 5};
      int cnt = count_if(v.begin(), v.end(), not1(IsOdd()));
      cout << cnt;
      return 0;
    }
  

    4
  

• not2

not1 和 not2 可以對 現有的謂詞進行 取反。

但他們僅支持 函數對象，並不適用於 lambda表達式

not1 和 not2 實質上是 基於結構體模板的，而 lambda本質上屬於 函數而不是 結構體

在用 not1和 not2進行 取反時還必須要求定義 typedef int argument_type，而且對於 運算符函數必須用 const作修飾。

使用並不方便。

Parameter Binders

• bind1st()
• bind2nd()

bind1st() 和 bind2nd() 適用於 操作類的函數對象。

一般與 Comparison Functions搭配使用。

Conversors

• ptr_fun()：

• mem_fun()：

      vector <string*> numbers;
      numbers.push_back ( new string ("one") );
      numbers.push_back ( new string ("two") );
      numbers.push_back ( new string ("three") );
      numbers.push_back ( new string ("four") );
      numbers.push_back ( new string ("five") );
  
      vector <int> lengths ( numbers.size() );
      transform (numbers.begin(), numbers.end(), lengths.begin(), mem_fun(&string::length));
  
      for (int i=0; i<5; i++) {
        cout << *numbers[i] << " has " << lengths[i] << " letters.\n";
      }
  

  one has 3 letters.
  two has 3 letters.
  three has 5 letters.
  four has 4 letters.
  five has 4 letters.
  

• mem_fun_ref()：

     vector<string> numbers;
     numbers.push_back("one");
     numbers.push_back("two");
     numbers.push_back("three");
     numbers.push_back("four");
     numbers.push_back("five");
  
     vector<int> lengths(numbers.size());
     transform(numbers.begin(), numbers.end(), lengths.begin(), mem_fun_ref(&string::length));
  
     for (int i = 0; i < 5; i++) {
       cout << numbers[i] << " has " << lengths[i] << " letters.\n";
     }
  

  one has 3 letters.
  two has 3 letters.
  three has 5 letters.
  four has 4 letters.
  five has 4 letters.
  

mem_fun() 和 mem_fun_ref() 可以在 流操作時將 成員函數 轉化為 函數對象，可以用於 調用對象的getter函數。
mem_fun()：適用於 指針版本，如 容器的元素 是 指針類型
mem_fun_ref()：適用於 引用版本，如 容器的元素 是 引用類型

Instrumental Types

• unary_negate() 和 binary_negate()：和 not1() 和 not2() 一樣 雞肋

• binder1st()和 binder2nd()：有點像 編譯版的bind1st()和 編譯版的bind2nd()

      binder1st<greater<int>> greater_than_10(greater<int>(), 10);
  

• pointer_to_unary_function() 和 pointer_to_binary_function()

• mem_fun_t() ， mem_fun1_t()，const_mem_fun_t()，const_mem_fun1_t()，mem_fun_ref_t()，mem_fun1_ref_t()，const_mem_fun_ref_t()，const_mem_fun1_ref_t()

Initializer List

initializer_list 是一種 數據類型，存儲 某種類型的元素的 列表。

  auto a = {10,20,30};
  copy(a.begin(),a.end(),ostream_iterator<int>(cout, " "));

10 20 30

Vector

數據結構 矢量，提供和 數組等效的功能。

Constructor & Destructor

Constructor

• empty container constructor
• initializer list constructor
• fill constructor: k elements with specific value

  vector<int> v(10, 3);
  copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));

3 3 3 3 3 3 3 3 3 3

• range constructor copy from ierator

  vector<int> src = {0,1,2,3};
  vector<int> v(src.begin() + 1, src.end());
  copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));

1 2 3

• copy constructor (and copying with allocator): copy from another vector

  vector<int> src = {0,1,2,3};
  vector<int> v(src);
  copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));

0 1 2 3

以下兩種寫法都是調用 拷貝構造函數。

operator= 賦值運算符 等價於 copy constructor

 vector<int> a;
 vector<int> b(a);
 vector<int> b = a;

• move constructor (and moving with allocator)

  vector<int> a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  vector<int> b(a, a.get_allocator());

  cout << "a: ";
  copy(a.begin(), a.end(), ostream_iterator<int>(cout, " "));
  cout << endl;
  cout << "b: ";
  copy(b.begin(), b.end(), ostream_iterator<int>(cout, " "));

a: 0 1 2 3 4 5 6 7 8 9
b: 0 1 2 3 4 5 6 7 8 9

Destructor

vector會 自動地 釋放 元素所使用的內存

Iterators

• begin() and end()
• rbegin() and rend()
• cbegin() and cend()
• crbegin() and crend()

Capacity

• size()

  size信息是作為 vector的屬性而存在的。
  可在 常數時間內獲取到。

  但 strlen()不是，對於 大字符串，不要頻繁地調用 strlen()

• resize()

      vector<int> v = {0,1,2};
      v.resize(5);
      copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
  

    0 1 2 0 0
  

• empty()

• capacity()：獲取 vector的底層數組的 大小

• reserve()

      vector<int> v = {0,1,2};
      printf("before reserve: capacity = %d\n", v.capacity());
      v.reserve(10);
      printf("after reserve: capacity = %d\n", v.capacity());
      copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
  

    before reserve: 3
    after reserve: 10
    0 1 2
  

  如果 事先知道需要添加的 元素的數量，則可以先用 reserve()來 一次性完成 預分配。

  reserve(int n) 只 保證 vector的底層數組的 大小足夠滿足 n元素，如果 vector的底層數組已經大於n，則該語句會被簡單地忽略。

  如果沒有使用 reserve()，則在插入 大量元素時，vector的底層數組可能會經歷 多次的動態擴容，浪費不必要的資源。

• shrink_to_fit()：動態縮容使得 capacity = size

Element Access

• Return reference

  • operator []，at()

  • front() ，back()

    盡管這些 access function返回的確實是 引用，

    但還需要註意 隱含的值拷貝。

    如果真的希望 取到vector的元素的引用，並且讓 數據修改反映到 vector內部的元素中，需要設置 refenence LHS以避免 值拷貝

    • value copy

     vector<int> v = {0,1,2};
     int num = v[0];
     num = 43;
     copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
    

    0 1 2
    

    • reference copy

     vector<int> v = {0,1,2};
     int & num = v[0];
     num = 43;
     copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
    

    43 1 2
    

• Return reference

      vector<int> v = {0, 1, 2};
      int *num = v.data();
      copy(num, num + 3, ostream_iterator<int>(cout, " "));
  

    0 1 2
  

  data()返回的是 vector的底層數組

Modifiers

• assign：assign n elements with specific values

  vector<int> v(10);
  v.assign(3, 5);
  copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));

5 5 5

n.b. assign 相當於 重新初始化vector，vector中舊的數據會被 刪除！

• push_back() and pop_back()

• insert() and erase()

  • insert()

    vector<int> v = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    v.insert(v.begin() + 1, 3, 9999);
    copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
    

    0 9999 9999 9999 1 2 3 4 5 6 7 8 9
    

    n.b. insert的 position的 語義是：欲插入元素 將插入在 該position的元素之前。

    或者等價地說：欲插入元素在 插入後 應該 位於position的位置

  • erase()

        vector<int> v = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        v.erase(v.begin() + 1);
        copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
    

      0 2 3 4 5 6 7 8 9
    

• clear()

• swap()

      vector<int> a(3, 100);
      vector<int> b(5, 200);
  
      a.swap(b);
      int & the_value_from_a = a[0];
      the_value_from_a = 9999;
  
      copy(a.begin(), a.end(), ostream_iterator<int>(cout, " "));
      cout << endl;
      copy(b.begin(), b.end(), ostream_iterator<int>(cout, " "));
  

    9999 200 200 200 200
    100 100 100
  

  swap()原理是直接 交換 兩個 vector的底層數組的指針

• emplace()

      vector<int> v = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
      v.emplace(v.begin() + 1, 9999);
      copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
  

    0 9999 1 2 3 4 5 6 7 8 9
  

  相比於 insert()，push_front() 和 push_back() 將 構造好的元素 傳遞給 Modifier。

  emplace()並不傳遞 已經構造好的元素，而是傳遞 用於構造這個元素的參數列表：這樣做有利於 減少不必要的元素值拷貝，而 直接在vector的底層數組上 構造元素。

  emplace_back() 同理。

     vector<int> v = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
     v.emplace_back(9999);
     copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
  

     0 1 2 3 4 5 6 7 8 9 9999
  

vector<bool>

• vector<bool> 是 vector的 模板特例化，它和 generic vector template相比，有以下特點：
• vector<bool>的 底層存儲並不一定是用 bool[]的。library可能選擇 其他底層存儲方式，並且盡可能地保證 僅使用1位來表示真值
• 不同於 常規的vector使用 allocator 分配對象， vector<bool>的 位數據可以被 直接地設置在 內部存儲
• 多出一個 flip() 翻轉函數
• vector<bool> 的 accesstor返回的是 用於指向單個為的 reference類型 而不是 bool類型

也就是說，使用 vector<bool> 並不會比 bitset<> 占用 更多空間或 更多時間。
在正常情況下，無法創建 真正的泛化的 vector<bool>，而取而代之的是 特例化的 vector<bool>

list

STL中的 list 是 doubly_linked_list

如果需要 singly_linked_list 則需要使用 forward_list。

n.b. forward_list的 性能 幾乎和 Handwritten C-style singly-linked-list沒有差別！

forward_list為了 性能甚至沒有 size()。

Operations

• splice()

      list<int> list1 = {0, 1, 2};
      list<int> list2 = {100, 200, 300};
      list1.splice(list1.begin(), list2);
  
      cout << "list1: ";
      copy(list1.begin(), list1.end(), ostream_iterator<int>(cout, " "));
      cout << endl << "list2: ";
      copy(list2.begin(), list2.end(), ostream_iterator<int>(cout, " "));
  

    list1: 100 200 300 0 1 2
    list2:
  

  splice() 可以 非常方便地對 2個鏈表進行 銜接操作。

• remove()

      list<int> list1 = {0, 1, 2, 3, 4, 2, 2, 2};
      list1.remove(2);
      copy(list1.begin(), list1.end(), ostream_iterator<int>(cout, " "));
  

    0 1 3 4
  

  n.b. remove()的 語義是 移除所有的符合條件的相等元素，而不是 移除第一個符合條件的相等元素

  帶謂詞的版本 remove_if()

• unique() and merge()

  n.b. unique()的 語義 和之前所提到的 std::unique()是相同的，都是指 remove consecutive equivalent elements，如果需要確保 移除整個容器中的相等元素，需要進行預處理 sort()

Array

STL的array數據結構僅僅是 ordinary array 的 包裝類。

  array<int, 10> num = {0,1,2,3};
  copy(num.begin(), num.end(), ostream_iterator<int>(cout, " "));

0 1 2 3 0 0 0 0 0 0

array提供了比 ordinal array更加方便的 輔助函數，但又沒有 vector的 復雜性。

如果你期望保持 ordinal array的眾多 特性，同時不期望使用 auto extendend/extracted

 array<int, 10> num = {0, 1, 2, 3};
 num.fill(100);
 printf("size = %d\n", num.size());
 copy(num.begin(), num.end(), ostream_iterator<int>(cout, " "));

 size = 10
 100 100 100 100 100 100 100 100 100 100

• size()

  傳統的C-Style數組在 參數傳遞時比較麻煩，但使用 array可以避免這個問題。

• iterator

  array可以使用 iterator對象，與其他STL函數的配合編碼更加方便。

  另外，array繼承了 ordinary的 傳統特性：允許 下標越界。
  ```cpp
  array arr;

  for (int i = -10; i < 20; ++i) {
  cout << arr[i] << “ “;
  }

  
  ```cpp
  4199804 0 6422000 0 -6 -1 0 0 0 0 8 0 4199705 0 8 0 75 0 8224624 0 16 11 8224592 0 4199367 0 0 0 75 0
  

• fill()

  array在 完全兼容 ordinal array的所有 初始化方法之外，

  還提供了一個非常有用的函數：fill()

  對於 ordinal array，我們可以使用 memset()。

  但遺憾的是，該函數只適用於填充 0和 -1

  array<array<int, 10>, 3> num;
  num.fill(array<int, 10>{100,200,300});
  for (int i = 0; i < num.size(); ++i) {
    for (int j = 0; j < num[i].size(); ++j) {
      cout << num[i][j] << " ";
    }
    cout << endl;
  }
  

  100 200 300 0 0 0 0 0 0 0
  100 200 300 0 0 0 0 0 0 0
  100 200 300 0 0 0 0 0 0 0
  

deque

STL的 deque 即 doubly linked list。

此外，STL的 stack和 queue 均是基於 deque實現的

priority_queue

不同於Java的 PriorityQueue，C++的STL的 priority_queue默認是 大頂堆。

template <class T, class Container = vector<T>,
  class Compare = less<typename Container::value_type> > class priority_queue;

priority_queue 底層使用的是 heap functions。

data source可以來自 多種類型的容器，只需要通過 range constructor來構造 priority_queue即可。

• max-imum heap

      vector<int> a = {1, 5, 2, 8, 3, 6, 4};
      priority_queue<int> PQ(a.begin(), a.end());
  
      while (!PQ.empty()) {
        cout << PQ.top() << " ";
        PQ.pop();
      }
  

    8 6 5 4 3 2 1
  

• min-imum heap

      vector<int> a = {1, 5, 2, 8, 3, 6, 4};
      priority_queue<int, vector<int>, greater<int>> PQ(a.begin(), a.end());
  
      while (!PQ.empty()) {
        cout << PQ.top() << " ";
        PQ.pop();
      }
  

    1 2 3 4 5 6 8
  

  同理，也可以使用 custom comparison function
  ```cpp
  vector a = {1, 5, 2, 8, 3, 6, 4};
  struct comp {

   bool operator()(const int &o1, const int &o2) {
     return o1 > o2;
   }
  

  };
  priority_queue, comp> PQ(a.begin(), a.end());

  while (!PQ.empty()) {
  cout << PQ.top() << “ “;
  PQ.pop();
  }

  
    ```cpp
    1 2 3 4 5 6 8
  

Map

map中的 條目 (entry)類型為

typedef pair<const Key, T> value_type;

map

STL中的 map底層數據結構是基於 Red-Black Tree 的，通過 operator <來完成 比較。

而且，可以直接對 map進行 叠代來得出 已排序的key序列

• operator[]

  • 如果key已存在，則返回 map[key]

  • 如果key不存在，則等價於：(*((this->insert(make_pair(k,mapped_type()))).first)).second

    如果使用 at()，則會在 key不存在時，拋出 異常

    map<int, string> m;
    m[1] = "first";
    m[2] = "second";
    m[3] = "third";
    m[4] = "four";
    printf("size = %d\n", m.size());
    m[5];
    printf("size = %d, value = %s\n", m.size(), m[5].c_str());
    m[100000000];
    printf("size = %d, value = %s\n", m.size(), m[100000000].c_str());
    

    size = 4
    size = 5, value =
    size = 6, value =
    

    n.b. 無論何時，對 map使用 operator[] 至多只會使得 size 增1

    n.b. 當 訪問map中不存在的key時，會自動 創建並插入pair (按默認值創建value)

    如果 value的類型是 UDT，則需要提供 no parameter constructor，否則無法通過編譯。
    如下面的例子，將 編譯失敗：

    ```cpp
    class Person {
    public:
    string name;

    public:
    Person(const string &name) : name(name) {}
    };

int main() {

map<int, Person> m;
m[0];
printf("size = %d, value = %s\n", m.size(), m[0].name.c_str());

return 0;
}
```

```cpp
main.cpp:42:7: note: candidate: 'Person::Person(Person&&)'
main.cpp:42:7: note:   candidate expects 1 argument, 0 provided
```

• iterator

  map<int, string> m;
  m[2] = "second";
  m[1] = "first";
  m[3] = "third";
  m[4] = "four";

  for (auto iter = m.begin(); iter != m.end(); iter++) {
    cout << iter->first << ", " << iter->second << endl;
  }
  return 0;

1, first
2, second
3, third
4, four

由於 map底層使用的是 red black tree，所以可以利用 map來進行 排序

• insert()：通常來說可以使用 operator[] 代替
• erase()

  map<int, string> m;
  m[2] = "second";
  m[1] = "first";
  m[3] = "third";
  m[4] = "four";

  m.erase(2);
  m.erase(5);

  for (auto iter = m.begin(); iter != m.end(); iter++) {
    cout << iter->first << ", " << iter->second << endl;
  }

1, first
3, third
4, four

n.b. 如果 欲刪除的key不存在，則 無事發生

• find()：get iterator to element

  map<int, string> m;
  m[2] = "second";
  m[1] = "first";
  m[3] = "third";
  m[4] = "four";

  auto iter = m.find(5);
  printf(iter == m.end() ? "not found" : "found");
  printf("\nsize = %d", m.size());

not found
size = 4

相比於 operator[]在 未找到元素時會 自動插入默認對而言，使用 find()來 判斷元素是否存在可以避免 浪費空間。

而且更重要的，find()是 冪等的

• count()：count elements with a specific key

  n.b. 如果僅僅是為了判斷 是否存在某個key，那麽相比於 find()寫法的麻煩，我們可以用 count() == 0來代替 find()

miltimap

與 map 的區別在於， miltimap支持 不同pair有重復的key。

• erase()

  對於 傳值的erase()，將 刪除所有符合條件的元素。

Set

set

STL的 set 是基於 red-black tree的，此外，它的 元素必須是 const的，只能 插入元素或 刪除元素，而不能 修改元素。

  set<int> S;
  S.insert(1);
  S.insert(2);
  S.insert(2);
  S.insert(3);
  S.insert(4);

  printf("size = %d\n", S.size());
  printf("count(2) = %d\n", S.count(2));

size = 4
count(2) = 1

n.b. 對於 set來說，如果 欲插入的元素已存在，則會忽略後續的插入（而不是 覆蓋插入）。

multiset

unordered_map

unordered_map

unordered_map 基於 bucket而非 red-black tree，通過 hash function來 索引 指定的 key。

因此，unordered_map 中的 key 是 無序的

因此，通常比 map 更快

• Bucket Functions

• Hash Policy Functions

unordered_multimap

unordered_set

unordered_set

與 unordered_map類似，均是基於 bucket的。

unordered_multiset

Compute Remainder and Quotient

• remainder()

Branch

• setjmp() and longjmp()

  jmp_buf  env;
  printf("before set jump\n");
  int val = setjmp(env);
  printf("after set jump\n");

  printf("val = %d\n", val);

  printf("before longjmp()\n");
  if (!val) longjmp(env, 1);
  printf("after longjmp()\n");

before set jump
after set jump
val = 0
before longjmp()
after set jump
val = 1
before longjmp()
after longjmp()

goto只支持 函數內跳轉，但 setjmp() and longjmp()可以支持 跨函數跳轉

使用 setjmp()保存 過程調用環境，然後用 longjmp()進行 jump。

一個跨函數的例子。

 int foo();
 int bar();
 jmp_buf env;
 int val;

 int foo() {
   printf("enter foo()\n");

   val = setjmp(env);

   printf("before call bar()\n");
   bar();
   printf("after call bar()\n");

   printf("leave foo()\n");
   return 100;
 }

 int bar() {
   printf("enter bar()\n");


   printf("before longjmp()\n");
   if (val != 1) longjmp(env, 1);
   printf("before longjmp()\n");

   printf("leave bar()\n");
   return 200;
 }


 int main() {
   foo();
   return 0;
 }

 enter foo()
 before call bar()
 enter bar()
 before longjmp()
 before call bar()
 enter bar()
 before longjmp()
 before longjmp()
 leave bar()
 after call bar()
 leave foo()

• goto

int main() {

  for (int i = 0; i < 100; ++i) {
    for (int j = 0; j < 100; ++j) {

      if (i == 10 && j == 20) {
        goto ok;
      }

    }
  }

  ok: 0xdead;

  printf("bye\n");
  return 0;
}

bye

關於 跳出外層循環，更推薦的寫法是給 外層循環加 控製標記

 int main() {

   bool flag = true;
   for (int i = 0; flag && i < 100; ++i) {
     for (int j = 0; j < 100; ++j) {

       // break the outer loop
       if (i == 10 && j == 20) {
         flag = false;
         break;
       }

     }
   }

   printf("bye\n");
   return 0;
 }

The incremental of size_t and size_type

  char c_str[] = "china";
  string cpp_str = "china";

  printf("strlen(c_str) = %d\n", strlen(c_str));
  printf("cpp_str.size() = %d\n", cpp_str.size());

  //
  int c_str_size = strlen(c_str) + 1;
  printf("c_str_size = %d\n", c_str_size);

  int cpp_str_size = cpp_str.size() + 1;
  printf("cpp_str_size = %d\n", cpp_str_size);

strlen(c_str) = 5
cpp_str.size() = 5
c_str_size = 6
cpp_str_size = 6

size_t和 size_type 本質上是 unsigned long long

在 強製轉化 為 int 時屬於 narrowing conversion。

對他們執行 遞增操作時應使用 遞增操作符 而不是直接 +1。

直接 +1的含義為 將unsigned long long 窄化為int，然後加上int型的1。該操作是 未定義的，取決於具體實現。

 Clang-Tidy: Narrowing conversion from 'unsigned long long' to signed type 'int' is implementation-defined

Exit the program

• Terminate
  • abort()：abnormal termination, raises the SIGABRT signal, do not cleanup
  • exit()：normal termination, do cleanup
  • quick_exit()：normal termination, do not cleanup
  • _Exit()

• Terminate

  • atexit()

        auto post = [](){
          printf("bye\n");
        };
        atexit(post);
    
        printf("before return\n");
    

      before return
      bye
    

- `at_quick_exit()`

• Get system environment

  • getenv()

        char * java_home = getenv("JAVA_HOME");
        printf("%s", java_home);
    

      D:\Program Files (x86)\Java\jdk1.8.0_291
    

• Execute commands

  • system()

Time

Time Manipulation

• clock()

int main() {

  for (int i = 0; i < 1000000; ++i) {}

  clock_t t = clock();
  printf("clock ticks since the program launched = %d", t);

  return 0;
}

clock ticks since the program launched = 10

clock() 計數的是 從程序啟動以來所經歷的時間刻。

   typedef long clock_t;

如果需要獲取 秒數則要除以 CLOCKS_PER_SECOND

• time()

int main() {

  time_t timer;
  time(&timer);

  printf("timer = %d\n", timer);
  return 0;
}

timer = 1650518640

 __MINGW_EXTENSION typedef __int64 __time64_t;
 typedef __time64_t time_t;

time_t本質上是 __int64。

直接使用 __int64 或者 long long也可以被接受。

• mktime()

int main() {

  /* Get current timestamp & use localtime() to get related struct tm */
  time_t raw_time;
  time(&raw_time);
  struct tm * timeinfo = localtime(&raw_time);

  /* Modify the struct tm & use mktime() to get related timestamp */
  timeinfo->tm_year = 2022 - 1900;
  timeinfo->tm_mon = 4 - 1;
  timeinfo->tm_mday = 21;

  time_t timestamp = mktime(timeinfo);
  printf("timestamp = %d\n", timestamp);
  return 0;
}

timestamp = 1650519507

localtime()：timestamp -> tm
mktime() ：tm -> timestamp

對於 struct tm實例，我們不是直接構造，而是通過獲取 當前時間戳，然後轉化得到 當前時間戳所對應的tm，再修改 tm的屬性字段，最後通過 mktime()來獲得 修改後的tm對應的時間戳

tm_wday 和 tm_yday字段被 忽略

year從 1900開始，month從 0開始

• difftime()

Conversion

• asctime()：tm -> string
• ctime()：timestamp -> string
• gmtime()：timestamp -> tm(UTC)
• localtime()：timestamp tm(local)
• strftime()：format tm -> string

strftime()雖然提供了 格式化tm結構的功能，但 struct tm本身已經包含了足夠的信息，可以非常方便地 自定義格式化函數

Code Pointer

除了常規的類型指針外，傳統C語言還有一種指針稱作 代碼指針。

通過對 代碼片段運用 地址運算符可以得到 該代碼片段的地址。

int main() {

  s1:
  printf("hi\n");

  printf("address of s1 = %d\n", && s1);

  void (*foo) (void) = reinterpret_cast<void (*)(void)>(4199857);
  foo();

  return 0;
}

hi
address of s1 = 4199857
hi
address of s1 = 4199857
hi
address of s1 = 4199857
hi
address of s1 = 4199857
hi
address of s1 = 4199857
hi
......

Remove Const-Qualified

const_cast<>()

  string str = "abc";
  char *str_data = const_cast<char *>(str.data());
  str_data[0] = 'A';
  cout << str;

Abc