仓库源文站点原文


title: play on stl date: 2022-04-18 22:44:00 tags:


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

Function Note
isalpha()
isdigit()
islower()
isupper()
ispunct()
isblank() C标准库只为\t和space返回非0值
tolower()
toupper()

limits.h

Macro Constant
INT_MIN
LONG_MIN
LLONG_MIN
UINT_MIN
ULLONG_MIN

math.h

Trigonometric Functions

Function Note
sin(), cos(), tan(), asin(), acos(), atan()
atan2() 返回给定坐标的角度

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

Hyperbolic Functions

Function
sinh(), cosh(), tanh(), asinh(), acosh(), atanh()

Exponential and Logarithmic Functions

Function Note
exp() 返回自然常数的指定指数值
log() 返回以自然常数为底的对数
log10() 返回以10为底的对数
log2() 返回以2为底的对数

Power Functions

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

Rounding and Remainder Functions

Function
floow()
ceil()

Other Functions

Function Note
abs() 用于求整数的绝对值 (用于浮点数时存在精度问题)
fabs() 用于求浮点数的绝对值

Classification Macro/Functions

Macro/Function Note
isinf() 判断浮点数是否无穷大
isnan() 判断浮点数是否为实数

Comparison Macro/Functions

Function
isgreater()
isgreaterequal()

stdio.h

Formatted Input/Output

Function Note
scanf() 格式化输入
printf() 格式化输出
sscanf() 格式化输入到字符串
sprintf() 格式化输出到字符串
getchar() 该方法不会跳过空白字符(回车, 换行, 空格)
gets() 输入1行 (以\n作为分隔符) 字符串
puts() 输出1行字符串 (该方法会在末尾自动添加\n)

Macros

Macro Note
EOF 值为-1的整数, 作为 文件流的末尾标识字符 .<br>注: EOF并不属于 文件内容 的一部分, 它只是一个 流状态标识符
NULL 整数值为0的字符, 作为 字符串的末尾标识字符.<br>注: NULL字符 确实属于 C语言风格字符串 的内容的一部分
size_t 无符号类型整数<br>注: 当其作为循环变量并与int类型的增量相运算时, 将存在类型转化不兼容

stdlib.h

String Conversion

Function Note
atoi(), atof(), atol(), atoll() 转换string到int, double, long, long long
strtod(), strtoll(), strtoul(), strtoull() 转换string(解释为以base为基数)到long, long long, unsigned long, unsigned long long

Pseudo-Random Sequence Generation

Function Note
srand() 初始化随机数种子
rand() 生成下一个随机数

Dynamic Memory Management

Function Note
malloc()
calloc() 该方法会自动进行填0初始化
reallocI()
free() 释放动态申请的内存

Searching and Sorting

Function Note
qsort() 快速排序
bsearch() 二分查找

string.h

Copying

Function
memcpy()
memmove()
strcpy()

Concatenation

Function
strcat()

Comparison

Function
memcmp()
strcmp()

Searching

Function
memchr()
strchr()
strrchr()
strpbrk()
strcspn()
strspn()
strstr()
strtok()

Other

Function Note
memset() 该方法本质是 字符串. 若需要填充整数, 则只有下列整数的可行的: 0, -1
strlen() 该方法不计入字符串末尾的结束字符

time.h

Time Manipulation

Function
clock()
difftime()
mktime()
time()

Conversion

Function
asctime()
ctime()
gmtime()
localtime()
strftime()

Containers

vector

queue

deque

stack

list

set

map

unordered_map

unordered_set

Other Libraries

Library
algorithm
bitset
chrono
codecvt
complex
exception
functional
initializer_list
iterator
limits
locale
memory
new
numeric
random
ratio
regex
stdexcept
string
system_error
tuple
typeindex
typeinfo
type_traits
utility
valarray

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

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

注意:该种方法只能用于填充 0-1

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

  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

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

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

  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():返回 最后一个相等的子序列首元素下标

  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

  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

  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

  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

  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

  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

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

Copy range of elements

  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

  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

  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

  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():只有当 谓词 测试通过时,才会用 新值 替换 当前元素

  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

  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

  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

  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)

  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()而言,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

n.b. 上述的 所有的归并操作在使用之前,都需要用 sort()集合A集合B 进行 预处理

否则将导致输出结果的错误。

Min/Max

Heap

堆操作函数将一个 数组维护 堆结构,但除此之外,我们还需要一个 表示堆大小的整数

n.b. 数组的大小 不一定等于 堆的大小,我们有可能 只使用数组中的一部分连续区域 来构成

n.b. 使用 数组时需要 额外维护一个表示堆大小的整数。但如果使用的是 vector,则可以 在每次堆操作后手动地 维护vector,使得 vector的大小始终与 heap的大小 相等。

Java的是,C++Heap默认是 最大堆,同理,基于Heap的PriorityQueue也默认是 最大优先队列

除此之外,还有一些 辅助操作

大部分情况下,如果需要使用 优先队列可以首先考虑 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

  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++的很多数据结构来说,并不适合。

Sorting

Partitions

Bitset

位图 (bitset) 是C++ 容器库之外的一个数据结构,它用 1个二进制位表示 1个逻辑型变量

相比于 char (8-bit)而言,更 节约空间

更重要的是,bitset提供了一些方便的 数据操作函数数据查询函数,以及对 字符串输出的支持。

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

  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);
  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

Accumulate values in range

  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

  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

  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

  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

  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()运算符重载,完成类似 普通函数函数调用

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

上述 算术操作函数对象可以非常方便地用于 transform()

Comparison Operation

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
Adaptor and Conversion Functions
Negators

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

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

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

在用 not1not2进行 取反时还必须要求定义 typedef int argument_type,而且对于 运算符函数必须用 const作修饰。

使用并不方便。

Parameter Binders

bind1st()bind2nd() 适用于 操作类的函数对象

一般与 Comparison Functions搭配使用。

Conversors

mem_fun()mem_fun_ref() 可以在 流操作时将 成员函数 转化为 函数对象,可以用于 调用对象的getter函数mem_fun():适用于 指针版本,如 容器的元素指针类型 mem_fun_ref():适用于 引用版本,如 容器的元素引用类型

Instrumental Types

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
  vector<int> v(10, 3);
  copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
3 3 3 3 3 3 3 3 3 3
  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
  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;
  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

Capacity

Element Access

Modifiers

  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中旧的数据会被 删除

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

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

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即可。

Map

map中的 条目 (entry)类型为

typedef pair<const Key, T> value_type;

map

STL中的 map底层数据结构是基于 Red-Black Tree 的,通过 operator <来完成 比较

而且,可以直接对 map进行 迭代来得出 已排序的key序列

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
```
  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来进行 排序

  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不存在,则 无事发生

  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()幂等的

miltimap

map 的区别在于, miltimap支持 不同pair有重复的key

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 更快

Function Note
bucket_count() return number of buckets
max_bucket_count() return maximum number of buckets
bucket_size() return bucket size
bucket() locate element's bucket
Function Note
load_factor() return load factor
max_load_factor() get or set maximum load factor
rehash() set number of buckets
reserve() request a capacity change

unordered_multimap

unordered_set

unordered_set

unordered_map类似,均是基于 bucket的。

unordered_multiset

Compute Remainder and Quotient

Branch

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

- `at_quick_exit()`

Time

Time Manipulation

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

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也可以被接受。

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_wdaytm_yday字段被 忽略

year1900开始,month0开始

Conversion

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