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 - 1}, b_{i - 1})$ 和 $(a_i,b_i)$ $(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$ $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

0 从C到C++

课程内容

C++的语言特性

主要特性

解读

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

STL：内置数据结构

deque

string

map相关

代码演示

strlen与length()的比较

map和unordered_map的比较

sort

随堂练习

HZOJ-245：货仓选址

HZOJ-166：字符串操作1

HZOJ-216：获取姓名并排序

HZOJ-287：合并果子

HZOJ-256：国王游戏

Tips

感谢您的支持，我会继续努力的!