0 从C到C++

C++ 比 C 难学，究竟难在哪里？
感性认识一下 C++ 的美？

课程内容#

问：为什么以C++ 11标准作为学习重点？

答：C++ 03 到 11 变化很大，而 11 到 14、17 变化很小，20 标准很新，还不普遍，所以从 C++ 11 标准入手是非常好的选择。

C++ 的语言特性#

主要特性#

头文件：130 个（C 语言：29 个）
STL
类和对象
模板
Lambda（C++ 11）
异常处理（C++ 11）

解读#

头文件非常多，不能以啃头文件作为学习方式
STL

本来不属于标准头文件，惠普实验室的大佬们开发的，C++ 后来将其纳入

面向对象（类和对象）
泛型编程（模板）：开发一个函数，相当于开发一百个函数
函数式编程（Lambda）

相比 C 语言的面向过程编程范式，C++ 增加了 3 种编程范式，工程项目中，一般同时使用 1～2 种编程范式，面向过程和面向对象较常用
新编程范式的本质作用：提高开发效率
- 不同的编程范式对应不同的开发效率，开发效率考虑写代码 + 测试 + 维护的时间
- 越往后，开发效率可能更高，但写代码难度也更高
- 使用新编程范式的主要情景：可以提高开发效率
PS：C 也可以实现面向对象范式，参考微软的COM in plain C

异常机制

针对某些特定的运行时错误，挽回程序崩溃退出的一种机制
设计哲学：程序的逻辑错误优先表现为编译错误，再表现为运行时错误

PS：

在学习了 C++ 后，假设还需要学习 java，可以按照编程范式分门别类地去学习
C++ 继承了 C 语言绝大多数的特性（语法规则）
- C++ 删除了 C 中的一些特性，但不是关键

输入输出的程序对比 [C、C++]#

cin、cout
- 不需要指定类型（格式占位符）
- 左移、右移运算符 [<<、>>]：涉及运算符重载
printf
- "% lf"：默认保留 6 位小数
- "% g"：输出全部有效数字位数，cout 使用的规则
scanf、printf 是函数；而 cin、cout 不是函数，是对象
[PS] endl：换行 + 清空缓冲区

STL：内置数据结构#

queue、stack、string、unordered_map、map... 相比自己用 C 语言实现，这里可以很方便地支持任意类型的元素，详见《面试笔试算法上》——5 STL “容器” 的使用与练习

deque#

双端队列
可以实现单调队列，不能用 queue，因为为了维护单调性，还需要尾部出队，详见《面试笔试算法下》——3 单调队列与单调栈

string#

C 的 strcmp 与 C++ 的 ==
C 的 strcat 与 C++ 的 +=
C 的 strlen 与 C++ 的 length ()
- 实现原理不太一样
- strlen：每次都需从头到尾扫一遍字符数组，直到遇到 '\0' --> O (N)
- .length ()：成员属性 --> O (1)
substr (pos, n)：从 pos 处向后取 n 位

map 相关#

基于哈希表 [无序]

存储、查找的均摊时间复杂度：O (1)
[C++ 11] unordered_map
[C++ 11 之前，非标准] hash_map

基于红黑树 [有序]

PS：

外在表现类似数组，但功能更强大
find (key)：如果找不到，返回 end () [哈希表的结束位置]

代码演示#

strlen 与 length () 的比较#

耗时有略微差异，但差异不大，原来环境可能对 strlen 有优化
- 参考for (i=0; i<strlen (s); i++) 会每次都执行一遍 strlen 吗？—— 知乎
c_str()—cppplus

map 和 unordered_map 的比较#

迭代器的使用先感受下，类型定义明确标明，后面可用 auto 关键字代替❗
有序性体现在遍历元素时
- unordered_map 对于 key 和 value 都无序，而且还会打乱原始顺序
- map 可当成排序工具
  - auto 关键字的使用
    - 对比前面完整的迭代器类型定义，先感受下
    - 很强大，有点像 cin 和 scanf 的区别，可以自动判断 iter 的类型
  - 排序结果
    - 虽然看着有点像计数排序，但不是
    - 时间复杂度涉及底层红黑树：O (NlogN)

sort#

展示了 C++ 的 4 种编程范式
CMP () 为可调用对象
lamda 表达式为 C++11 新推出的
这里 struct 和 class 有什么区别，参考深度理解：struct 和 class 的区别—— 博客

随堂练习#

HZOJ-245：货仓选址#

样例输入

5
1 3 5 6 10

样例输出

思路
- 注意：输入可能是乱序
- 问题转换
  - 随机选择一个点 p，当前距离总和为 s1
  - 当点 p 移动很小的距离 Δ 时，此时距离总和 s2 = s1 + (n1 - n2) * Δ
    - n1：点 p 左边的商店数；n2：点 p 右边的商店数
  - 【目标】s2 < s1
    - 当 n1 - n2 <0 时，Δ> 0 --> s2 < s1：即右边商店多时，往右移动点 p，可以有更优解
    - 当 n1 - n2 > 0 时，Δ <0 --> s2 < s1：即左边商店多时，往左移动点 p，可以有更优解
  - 【最终目标】n1 = n2 即可，所以找第 n / 2 位元素坐标
    - n 为商店总个数，位数从 0 开始
代码
- 解法 1：sort 方法
  - 主要耗时在输入和求和
  - sort 使用详见《面试笔试算法上》——2 二分专题 —— 附加知识点，终止位置为最后一个元素的下一位
- 解法 2：nth_element 方法
  - nth_element
    - 基于快速选择算法—— 知乎，借鉴快速排序的 Partition 过程，但不会对整个序列排序
    - 执行完后，【第 k 位放置着从小到大排名第 k 位的元素】❗
  - 小作业：nth_element 使用方法和技巧，见链接
- 方法比较
  - 解法 1：完全排序
  - 解法 2：不完全排序，直接得到第 k 位

HZOJ-166：字符串操作 1#

样例输入

AAAAAA
2
xxx

样例输出

6
AxxxAAAAA
6

思路
- 考察字符串操作和常用方法
- 将字符串 B 插入到字符串 A 里面
代码
- string 类
  - size()、length()是一样的
  - insert
  - rfind
    - 从右边开始查找，但返回的是其下标（正向的）
    - 在这个场景里，也可以使用find_last_of方法，关注字符串中任意一个字符的匹配，参考string 的 find 和 find_first_of 的区别—— 极客分享
- 小作业：关于 string 更多的用法，见链接

HZOJ-216：获取姓名并排序#

样例输入

5
Mr.DMY
Mr.ZY
Mr.LYH
Ms.Grace
Mr.Bill

样例输出

Bill
DMY
Grace
LYH
ZY

思路
- 可以使用 sort
- 还可以使用 map 结构，底层是红黑树，默认按 key 排序
代码
- 使用 map
- 了解迭代器 iter 的使用，->first 代表 key，->second 代表 value
- 注意
  - 需要先将名字进行截取
  - value 值用来计数，名字可能有重复

HZOJ-287：合并果子#

样例输入

3
1 2 9

样例输出

思路
- 一开始越小越好，所以可以使用最小堆
- 小作业：讨论合并果子和哈夫曼编码之间的关系，见链接
代码
- priority_queue
  - 它是一个模板，<> 里放的都是类型，默认为最大堆
  - 若要改为最小堆，需要先定义容器类型：vector；然后，
    - 方式一：定义 CMP 类，重载 () 运算符，使其可以被当成可调用对象（即仿函数、函数对象）
    - 方式二、方式三：使用模板类，后续再学

HZOJ-256：国王游戏#

样例输入

样例输出

思路
- 目标：求最小的最大值
- 算法是想：微扰
  - 令
    - 所有人左手上的数字序列为 $a_0,a_1,a_2,...,a_i,...,a_n$，
    - 所有人右手上的数字序列为 $b_0,b_1,b_2,...,b_i,...,b_n$，
    - 排在该大臣前面的所有人的左手上的数的乘积为 $A_{i-1}=a_0*...*a_{i-1}$，
  - 则
    - 每位大臣获得的金币数为 $G_i=A_{i-1}/b_i$
  - 假设有一个排列 1为
    - $G_1,G_2,...,[G_{i-1},G_i],...,G_n$，其中 $G_i$ 最大
  - 此时若调换相邻的两个大臣的位置，即 $(a_{i-1},b_{i-1})$ 和 $(a_i,b_i)$，会产生新的排列 2
    - $G_1,G_2,...,[G_{i}^{'},G_{i-1}^{'}],...,G_n$
    - ❗ 排列 1 和排列 2 哪个更接近目标呢？只需要关注发生改变的金币数 $G_{i}^{'},G_{i-1}^{'}$ 和最大的金币数 $G_i$ 的关系。如果均为小于关系，则排列 2 更接近目标
  - 分析
    - 只有被调换的两位大臣的金币数有变化
      - 已知：$G_i=A_{i-1}/b_i$
      - 调换后：$G_{i}^{'}=A_{i-2}/b_i$，$G_{i-1}^{'}=A_{i-2}*a_i/b_{i-1}$
    - 易知 $G_{i}^{'}<G_{i}$，
    - 而如果 $G_{i-1}^{'}<G_i$ 也成立，则排列 2 更接近目标，即
      - $G_{i-1}^{'}<G_i$
      - ↓
      - $A_{i-2}*a_i/b_{i-1}<A_{i-1}/b_{i}$
      - ↓
      - $A_{i-2}*a_i/b_{i-1}<A_{i-2}*a_{i-1}/b_{i}$
      - ↓
      - $a_i*b_{i}<a_{i-1}*b_{i-1}$
  - 👉大臣交换位置的条件：
    - $a_i*b_{i}<a_{i-1}*b_{i-1}$
代码
- 算法：基于微扰的思想，设计出排序规则即可
  - 使用 pair 对类型方便组织左、右手上的数字
  - 国王一直在最前，不参与排序
- ⭐数据结构：大整数
  - 单独封装一个处理进位的方法，乘法和除法过程结尾都使用一次
  - ❓ 构造函数里可以直接使用 push_back ()，后续学习关注
  - 除法的设计，主要利用余数，可能产生前导 0，要处理
  - ❓ 重载小于号需要在方法末尾添加const，否则不生效，可能会优先使用 vector 的小于比较，具体原因后续学习
- PS：这里真正将数据结构和算法分开了，这也是面向对象相比面向过程的优势

Tips#

不仅要知其然，还要知其所以然，更要知其四五六个所以然
C++ 的学习没有标准答案，多互相讨论
学会查看cppreference
推荐
- 书籍：C++ Primer、Effective C++、深度探索 C++ 对象模型...
- 视频：侯捷老师
  - 跟侯捷学 C++ 全方位提升技能素养 ——C++ 开发工程师（2016）
  - 链接：https://pan.baidu.com/s/1G7v0w4nH64SVH1FpE5czzQ
  - 提取码：y8tu