[STL] Simple Use of STL

Code Snippet

Standard C Libraries

Template Header Files

/* 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

FunctionNote
 
 
 
 
 
C标准库 只为 \tspace 返回 非0值
FunctionNote
 
 

limits.h

Marco ConstantNote
 
 
 
 
 
 
 
 
 
 

math.h

Trigonometric Functions

FunctionNote
 
 
返回 给定坐标角度

注:这些 三角函数 输入均为 浮点数,默认使用 弧度作为单位。

Hyperbolic Functions

FunctionNote
 
 

Exponential and Logarithmic Functions

FunctionNote
返回 自然常数的指定 指数值
返回以 自然常数为底的 对数
返回以 10 为底的 对数
返回以 2为底的 对数

Power Functions

FunctionNote
该函数底层通过 浮点数 进行计算,
存在 精度损失问题,若确实需要使用,请配合 round()
返回 平方根
返回 立方根
返回 直角三角形的斜边

Rounding and Remainder Functions

FunctionNote
向下取整
向上取整

Other Functions

FunctionNote
用于 求整数的绝对值
对于 浮点数存在 精度问题
用于 求浮点数的绝对值

Classification Macro/Functions

Macro/FunctionsNote
判断 浮点数是否 无穷大
判断 浮点数是否为 实数

注:除0错误是针对 整数而言的。如果对 浮点数进行 除0操作,将得到一个 特殊的浮点数值

它用于表示 无穷大。同理,也有 另一个特殊的浮点数值用于表示 非数字 (Not-A-Number)

Comparison Macro/Functions

Macro/FunctionNote
 
 

stdio.h

Formatted Input/Output

FunctionNote
格式化输入
格式化输出
格式化输入到 字符串
格式化输出到 字符串
该方法 不会跳过 空白字符 (回车,换行,空格)
输入1行 (以\n作为分隔符)字符串
输出 1行字符串
注:该方法会在末尾自动加 \n

Macros

MacroNote
EOF值为-1的整数,作为 文件流的末尾标识字符
注:EOF并不属于 文件内容的一部分。它只是一个 流状态标识符
NULL整数值为0的字符,作为 字符串的末尾标识字符
注:NULL字符确实属于 C语言风格式的字符串一部分
无符号类型整数

stdlib.h

String Conversion

FunctionNote
转换 stringintdoublelonglonglong
转换 string (解释为以 base为基)到 long longlong unsigned long unsign long long,所 返回的整数计量用的权重

Pseudo-Random Sequence Generation

FunctionNote
初始化 随机数种子
生成 下一个随机数

Dynamic Memory Management

FunctionNote
 
该方法会自动进行 填0初始化
 
释放动态申请的内存

Searching and Sorting

FunctionNote
快速排序
二分查找

string.h

Copying

FunctionNote
 
 
 

Concatenation

FunctionNote
 

Comparison

FunctionNote
 
 

Searching

FunctionNote
 
 
 
 
 
 
 
 

Other

FunctionNote
该方法本质是 填充字符串,如果要填充 整数
则下列 整数是可行的: 0-1
该方法 不计入 字符串末尾的结束字符

time.h

Time Manipulation

FunctionNote
 
 
 
 

Conversion

FunctionNote
 
 
 
 
 

 

Containers

vector

queue

deque

stack

list

set

map

unordered_map

unordered_set

Other Libraries

LibraryNote
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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 functioncomparison 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

greaterless经常用于 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

not1not2 可以对 现有的谓词进行 取反

但他们仅支持 函数对象,并不适用于 lambda表达式

not1not2 实质上是 基于结构体模板的,而 lambda本质上属于 函数而不是 结构体

在用 not1not2进行 取反时还必须要求定义 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. insertposition语义是:欲插入元素 将插入在 该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中的 listdoubly_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传统特性:允许 下标越界

array<int, 10> arr;

for (int i = -10; i < 20; ++i) {
 cout << arr[i] << " ";
}
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的 dequedoubly linked list

此外,STL的 stackqueue 均是基于 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

    vector<int> a = {1, 5, 2, 8, 3, 6, 4};
    struct comp {
       bool operator()(const int &o1, const int &o2) {
         return o1 > o2;
       }
    };
    priority_queue<int, vector<int>, comp> PQ(a.begin(), a.end());
    
    while (!PQ.empty()) {
     cout << PQ.top() << " ";
     PQ.pop();
    }
    
    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,否则无法通过编译。

    如下面的例子,将 编译失败

    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;
    }
    
    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
FunctionNote
  • Hash Policy Functions
FunctionNode

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_tsize_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()

mktime()

对于 struct tm实例,我们不是直接构造,而是通过获取 当前时间戳,然后转化得到 当前时间戳所对应的tm,再修改 tm的属性字段,最后通过 mktime()来获得 修改后的tm对应的时间戳

tm_wdaytm_yday字段被 忽略

year1900开始,month0开始

  • difftime()

Conversion

  • asctime()
  • ctime()
  • gmtime()
  • localtime()
  • strftime()

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

 

 

Leave a Reply

Your email address will not be published.