程序设计实习#

C++#

类和对象#

面向对象I#

面向对象：数据抽象、继承、动态绑定
将数据结构和操作该数据结构的函数捆绑在一起，形成了类（带函数的结构）
C++中，设计程序的过程就是设计类的过程
对象所占内存大小是成员变量之总和
可以用=在对象间赋值，但没有重载运算符时无法使用比较运算符

使用类的成员变量和成员函数
1. 对象名.成员名
2. 指针
3. 引用 定义引用时需要初始化其成为一个变量 e.g.CRectangle & rr = r2
  - 引用好处：减少拷贝开销
  - 如果函数内不需要修改，使用常引用const int & xxx，原变量仍可以修改
成员函数其他写法
在类T中声明后，类外使用void T::function(xxx)这样的语法
成员的访问权限
1. private 只能在成员函数内访问，缺省权限，对再开发时的修改很有帮助
2. public
3. protected
- struct中，缺省权限为public
函数重载
函数名相同而参数个数/类型不同，编译器调用时根据实参个数类型匹配
最右边起连续若干个参数可以使用缺省值（如void function(int x = 0, int y = 0)中的x、y 只要是有定义的表达式，都可以作为函数参数的缺省值（如int x,int y=max(a,b),int z=min(a,b)）
函数重载时如果存在二义性，则会编译错误

面向对象II#

构造函数 用于初始化对象
1. 基本信息
  不是void，只是没有返回值，需要和类同名
  编译器会默认生成无参数的构造函数，如果定义了，则不生成
  构造函数的参数可以是本类的对象 e.g.Complex::Complex(Complex c1, Complex c2)
  private的构造函数不能直接用来初始化对象
2. 构造函数在数组创建中的应用
  指针new申请的空间如果没有元素则不参与初始化
  e.g.T *array[3] = {new T(1,2), new T(4)}只会调用两次构造函数
复制构造函数
1. 基本信息
  与类同名，有且仅有一个参数为同类对象的引用 / 常引用也即T::T(&T) / T::T(const &T)
  编译器会默认生成无参数的复制构造函数，如果定义了，则不生成
  调用过程：
```
Complex::Complex(Complex &c){}
Complex c1;
Complex c2(c1); //等同于Complex c2=c1，此处是初始化，执行了复制构造函数而非赋值
```
cpp
1. 调用情况
  1. 如上，用一个对象初始化同类的另一个对象（区别于用等号链接两个同类对象如c2=c1！）
  2. 函数的参数为类的对象，调用函数时（尽量传引用）
  3. 函数返回值为类的对象，函数返回时（尽量传引用）
2. 类型转换构造函数
  只有一个类型不同的参数的构造函数，e.g.Complex(int i){real = i, imag = 0;}
  上例调用时，可以直接使用Complex c=1这样的语句
  隐式类型转换构造函数会使得c=1（其中c是已经定义的Complex对象）也调用之
  若要避免上方情况，则需要使用explicit Complex(int i)（显式类型转换构造函数），定义为显式后若调用只能在初始化时使用
析构函数
1. 基本信息
  名字与类相同，名字加~
  编译器会默认生成无参数的析构函数，如果定义了，则不生成
2. 调用情况
  1. 对象数组生命期结束时，每个元素的析构函数都会被调用 e.g.main函数结束时、delete后
  2. 函数调用对象消亡时
  3. 函数调用返回值消亡时
    static变量消亡时间早于全局变量
this指针
1. 作用：指向成员函数作用的对象，隐式存在于每个成员函数之中
  区分成员函数传入的参数和本身参数/return *this以支持链式调用
  在非静态成员函数中，隐式含有*this这一参数

面向对象III#

课前小测注 常量指针int *constv.s.指针常量int const*：前者不能通过指针修改的变量，后者不能修改指针指向的地址

内联函数减少函数调用的开销
在返回类型前加inline
成员函数前加inline则成为内联成员函数；类内部的成员函数自动成为内联成员函数
静态成员变量和静态成员函数
在声明前加static
静态成员变量为所有对象共享，在sizeof时不计在内
静态成员函数不必然需要通过对象访问，访问静态成员可以通过类名::成员名直接进行
实际上，相当于封装进类内的全局变量/全局函数
注意： 静态成员函数中不能调用非静态成员变量/函数
常量成员函数
在期望提高效率并且实参值不会被修改的情况下，可以使用const T &(variable)
1. 常量对象
  某个对象的值不会变，可定义为const T (variable)
  常量对象只能使用构造/析构/常量方法
2. 常量方法
  函数声明后加入关键字const，例如void Sample::GetObj()const{}
  注意， 常量成员函数中不能调用非常量成员函数和修改非静态属性的值
  如果两个函数除const之外全部相同，那么也算重载
3. mutable成员变量
  可以在const成员函数中被修改的成员变量
成员对象和封闭类
一个类的成员变量是其他类的对象，这样的类称作封闭类
封闭类必须有构造函数，构造函数必须有初始化列表
1. 初始化列表
  先构造成员对象，后执行封闭类构造函数，构造顺序与变量在类中的说明次序一致，析构时顺序对称
2. const成员和引用成员
  其初始化必须在初始化列表中进行
友元
友元函数：可以访问该类的private成员，声明时在返回类型前添加关键字friend
友元类：类的所有成员函数都可以访问另一类的private成员
友元类的关系不能自反/传递/继承

运算符重载#

实质：函数重载
运算符可以被重载成普通函数，也可以被重载成类的成员函数
重载为成员函数时，只需要传递(运算符目数-1)个参数
赋值运算符重载
赋值运算符只能重载为成员函数，其两侧类型可以不匹配
引用可以作为左值，因此为了实现obj="hello"这样的语句，重载函数返回值需要是引用(return *this;)
Problem a. 浅拷贝/深拷贝： 拷贝应该复制地址所指向的值而不是地址，如果简单复制地址，在析构时会重复析构、在修改时会联动
修改方法：传常引用
Problem b. 避免自赋值： 通过if(this==&other) return *this;实现，减少开销
Problem c. 链式调用？返回值必须是引用
Problem d. 重载为普通函数时，如果调用private对象，则需要声明为友元
注意： 对于所有非构造函数的涉及动态分配内存的函数，先delete旧的指针再申请空间
流插入运算符重载
cin/cout事实上是istream/ostream类的对象，<</>>由于运算符重载得以支持输入输出
其他可重载运算符
1. 数组下标[]
  必须返回引用！否则无法作为左值参与赋值语句
2. 类型转换运算符operator type()
  必须做成员函数，没有形参，不指定返回值类型，类型转换时会自动调用，常定义为const
3. 自增/自减++/--
  前置运算符作为一元函数重载（重载operator++但只在++i中被调用）返回引用，后置运算符作为二元函数重载（重载operator++但只在i++中被调用）返回值
其他注意事项
1. 不能定义运算符
2. 运算符重载后优先级不变
3. 重载()``[]``->``=时必须在类内

继承与派生#

基本概念
1. 若类B拥有类A的全部特点，称A为基类/父类，B为派生类/子类
2. 派生类语法：class 派生类名:派生方式说明符基类名{}，其拥有基类的全部成员，但无法访问基类的private成员
3. 派生类对象中，基类对象的存储位置在派生类对象新增的成员变量之前
  派生类vs封闭类：A是B的一种orA中含有B
4. 基类和派生类若拥有同名成员，则通过作用域符号来区分，若在派生类内部则缺省访问派生类对应成员 （通常不定义同名成员）
成员组成与可见性
基类的private成员不能被派生类访问
1. protected可以被派生类成员函数/this指针访问
2. 继承方式：
  1. public：保持原有状态
  2. private：基类private/protected均变private
  3. protected：基类private/protected变protected

继承方式	public成员	protected成员	private成员
public	public	protected	不可访问(private)
private	private	private	不可访问(private)
protected	protected	protected	不可访问(private)

构造构造派生类时，要注意构造函数内不能直接访问基类的private成员
与封闭类不同，派生类构造时先构造基类后派生类；封闭类相反
如果派生类成员也存在其他类对象，则在基类后再构造
public继承的赋值兼容
派生类对象可以赋值给基类，可以初始化基类引用，可以把地址赋值给基类指针 （以上赋值不会包含派生类特有对象）
强制指针转换
使用如下语句可以强制将基类地址赋给派生类，但是可能引发程序崩溃（访问未知内存）
```
class Base{}
class Derived:public Base{}
Base* ptrbase=&objDerived;
Derived* ptrderived=(Derived*) ptrbase;
```
cpp
基类指针调用基类函数
~~多继承（非考点）~~
有多个基类的派生类，按照继承顺序调用基类构造函数，然后构造自身
声明语法：class Derived:public Base1,public Base2{};
多继承的二义性检查在访问权限之前（即不能多个基类的同名函数通过一个public若干个private来通过编译）

多态#

虚函数
在类定义中前加virtual关键字的函数（声明时即可）/基类中加virtual关键字的所有派生类中的同名函数
基类指针指向基类/派生类对象时，调用基类/派生类虚函数
**优点：**便于总框架调用各层次派生类的函数，且扩展性强
多态
实质：父类定义接口，子类不同实现，父类用相同操作操作不同子类的行为
实现要求：利用基类指针可以指向派生类的特性
**注意：**一定要使用基类指针访问虚函数！！！
动态联编
普通成员函数中，函数调用语句在编译时不确定调用哪个函数，调用时再判断
但语法检查不考虑实际执行结果，例如基类指针指向派生类对象，基类虚函数private而派生类public，编译错误！
多态的实现原理
有虚函数的类会存放虚函数表（列出了虚函数的地址）
占用4bytes
虚析构函数
不将析构函数声明为virtual的，则使用基类指针删除派生类对象时不调用派生类析构函数，只调用基类析构函数
纯虚函数与抽象类
纯虚函数：没有函数体的虚函数 e.g. virtual void function()=0;
抽象类：包含纯虚函数的类，只能作为基类，不能创建抽象类对象，但可以创建抽象类指针/引用以指向其派生类对象
抽象类构造/析构函数内不能调用纯虚函数由抽象类派生的类必须实现全部基类中的纯虚函数才能成为非抽象类

输入输出和文件处理#

输入输出相关类
输入/输出类实例化的对象完成输入/输出
1. 标准流对象
  - 输入流对象cin
    可以被重定向为从文件读取数据，freopen("xx.txt",“r",stdin);
  - 输出流对象cout/cerr/clog
    可以被重定向为从文件输出数据，freopen("xx.txt","r",stdout);
    cerr无缓冲报错，clog有缓冲报错，当手动flush/缓冲区满时输出
    getline是istream类的成员函数，cin这个对象的函数getline分隔符参数缺省使用，因此无法读入整行
2. 流操纵算子（头文件#include <iomanip>）
  - 整数流的基数hex/oct/bin
  - 浮点数的精度
    cout.precision()等价于cout<<setprecision()，非定点时，设定有效位数
    定点时，添加setiosflag(ios::fixed)，设定小数点后位数，此后直到下次取消为止均定点
    取消定点，添加resetiosflag(ios::fixed)
  - 域宽
    cout.width()等价于cout<<setw()，设置这行输出左起长度
    在每次输入/输出前都需要设置域宽
    **注意：**由于后接/0，因此实际输出宽度为参数-1
  - 自定义
    实质是定义函数
```
//e.g.
ostream& tab(ostream& os){
    return os<<'\t';
}
```
  cpp
3. 文件与流将顺序文件看作一个有限字符构成的顺序字符流，然后读写类似cin/cout
  对输入/输出/输入输出，有读/写/读写指针标识读写操作在哪里进行
  打开的文件一定要通过File.close()关闭

函数模板与类模板#

函数模板
对于函数算法完全相同，仅是数据类型不同的情况，可考虑函数重载/函数模板
由编译系统根据函数调用时实参类型，自动生成相应模板函数
设置类型参数template<class T>，在函数参数/返回类型/局部变量声明中可以使用T代替具体类型，编译时自动确定
如果使用了自定义数据类型的运算，则需要重载运算符
注意： 需要避免二义性
函数模板的重载
同一函数但模板中的参数数量不同
调用顺序：参数类型完全匹配的函数→完全匹配的模板→可通过强制类型转换调用的函数→报错
类模板
快速定义一些相似的类（称为模板类）：

template<类型参数表>  
返回值类型 类模板名<类型参数名列表>::成员函数名(参数表){

}

cpp

定义对象：`类模板名<真实类型参数表> 对象名(构造函数参数)`  
同一个类模板的两个模板类是不兼容的，无法进行互相赋值等操作

plaintext

4. 类模板与派生
类模板/模板类/普通类派生类模板；模板类派生普通类
前三者声明派生类前需要写出派生类类型参数，如template<class T1,class T2>
类模板中的所有静态成员都会包含在所有模板类中，但不同模板类不能共享静态成员
5. 友元
函数/类/类成员函数/函数模板/类模板都可以作为类模板的友元
函数模板也可作为类的友元
注意： 类型参数可能影响类模板友元类模板的匹配
6. string类
成员函数详见课件andC++文档

STL#

STL1#

标准模板库-软件的重用

基本概念：容器container、迭代器iterator、算法algorithm
容器：放入容器中的类需要实现==/</>运算符，插入时放入的是对象拷贝
1. 顺序容器：vector/deque/list
  1. vector 动态数组，存取元素复杂度为常数，尾端增删
  2. deque 动态数组，存取复杂度为差于vector的常数，仅在头部插入/删除优于vector
  3. list 双向链表，增删复杂度为常数，不支持随机存取
2. 有序容器：set/multiset/map/multimap
  元素之间有序，查找时更快，原理-平衡二叉树，插入/检索复杂度logN
  1. set/multiset set不允许相同元素，multiset允许相同元素
  2. map/multimap 存放成对的key-value，根据key排序，multimap允许相同key
3. 容器适配器：stack/queue/priority_queue
  1. stack 后进先出
  2. queue 先进先出
  3. priority_queue 优先队列

容器	类型	特点	存取	增删
vector	顺序	动态数组，支持随机存取	O(1)	尾端O(1)
deque	顺序	动态数组，支持随机存取	略差于vector	头部O(1)
list	顺序	双向链表，不支持随机存取	O(n)	O(1)
set/multiset	有序	平衡二叉树，有序	O(logN)	O(logN)
map/multimap	有序	key-value对，平衡二叉树	O(logN)	O(logN)
stack	适配器	后进先出	-	-
queue	适配器	先进先出	-	-
priority_queue	适配器	优先队列，缺省最大堆顶	-	-

迭代器：
指向第一类容器，可读，若非const还可修改
定义方法：容器类名::const_iterator/iterator/reverse_iterator
iterator指向.end()时迭代结束，reverse_iterator指向rend()时迭代结束
可使用迭代器的容器中，除vector/deque外不能随机访问，仅支持双向访问，也即意味着无法使用</>运算符对迭代器范围进行限制
算法：
均为函数模板，通过迭代器操作容器/C数组元素
可以根据需要结合函数模板内容重载相关运算符，达到不同效果
注意： 在STL中，缺省时，比较大小用<进行，认为以下三者等价：

x比y小
y比x大
x<y成立
相等不等价于x==y，而是!(x<y||y<x)

顺序容器
i/ostream_iterator输入输出迭代器，实例化时需要重载postfix++/*/=三个运算符，注意重载函数返回迭代器自身解引用*this作为迭代器引用类型返回值
函数对象
在类中 重载() 运算符为成员函数，即为函数对象类，在调用该对象的()运算符时看起来且实际上进行了函数调用过程
可以保证STL中的算法比较规则/计算规则等通过一个函数规定
好处：减少反复调用函数开销，可存储参数，如果函数对象定义为模板类则泛化能力更强，编译器可以内联函数对象
STL中已定义了equal_to/greater/less
函数指针
指向函数入口地址的指针变量，其定义的一般形式为类型名 (*变量名)(参数表),调用时变量名(实参表)
如果既想接受函数指针也想接受函数对象，则应该使用模板

STL2#

关联容器：
1. multiset 参数2（函数对象）缺省为less，也即multiset<A>等价于multiset<A,less<A> >
  less的实现依赖<，因此放入multiset的类必须重载<
  成员函数lower/upper_bound返回最大/最小迭代器it使得[begin(),it)中的元素均比查找值大/小
  与multiset不同，set不允许重复值
  set的insert函数返回一个pair，first是迭代器，指向插入位置，second是bool，表是否成功
2. multimap
  缺省使用less<Key>，按Key值排序
  由于multimap的key可以重复，因此不能根据key值访问
容器适配器
top()函数返回顶部元素的引用
缺省状态下，less<T>为priority_queue的比较器，导致最大元素位于堆顶
实质上，pop()的操作是修改堆顶指针的指向
算法
1. 不变序列算法
  时间复杂度 $O(n)$
2. 变值算法
  值被修改的区间不可属于关联容器
3. 删除算法
  不使容器中元素减少，而是形成新的逻辑结尾
4. 变序算法改变顺序而不改变元素的值，复杂度 $O(n)$
5. 排序算法要求容器支持随机访问迭代器，复杂度 $O(nlogn)$ ，三参通常为函数对象，支持比较规则重载
  sort算法为快速排序，stable_sort为归并排序
6. 有序区间算法
  要求区间已升序且容器支持随机迭代器
7. bitset
  包含在头文件#include <bitset>下，为类模板
```
template<size_t N>//int常数
class bitset{
    ...
};
```
cpp
通过bitset成员函数获取并修改每一位

高阶特性#

C++98#

类型转换
C依赖强制类型转换，可能不安全
C++中的cast运算符可以辅助类型转换：static_cast/reinterpret_cast/dynamic_cast/const_cast
使用语法：cast运算符<目标类型> 原变量
1. static_cast
  进行存在类型转换运算符的转换，不能用于不同类型的指针/引用/指针与整型的转换
2. reinterpret_cast
  进行不同类型指针/引用/指针和可容纳指针的整数类型的转换，不会进行安全性检查
3. const_cast
  进行去除const属性的强制类型转换
4. dynamic_cast
  用于多态也即有虚函数的基类的指针/引用转换为派生类的指针/引用

cast运算符	用途	安全性
static_cast	存在类型转换运算符的转换，不能用于不同类型指针/引用/指针与整型	编译时检查
reinterpret_cast	不同类型指针/引用/指针与整型的转换	不检查
const_cast	去除const属性	有限检查
dynamic_cast	多态基类指针/引用转换为派生类指针/引用	运行时检查

异常处理
1. 基本语句
  throw语句抛出异常，try...catch处理异常
  用try包含需检测的代码，throw抛出异常，后接catch执行相应操作
2. 再抛出
  如果本函数内没有处理异常，会被抛出到上一级函数内
3. 标准异常类
  均由exception类派生而来，包含在头文件#include <stdexcept>下
typeid和typeinfo 包含在头文件#include <typeinfo>下
返回函数/表达式的类型
预编译和条件编译

C++11#

初始化
可以统一使用{}初始化，支持成员变量初始化
auto关键字
自编译起，自动推导变量类型
可配合decltype关键字使用，其根据表达式推导类型
智能指针
1. shared_ptr 包含在#include <memory>下，托管指针，可自动释放内存
  使用shared_ptr<T> ptr(new T);//T 类型名托管指针，通过.reset()放弃托管，当托管计数=0则delete对象
2. unique_ptr
  每个托管对象仅被一个unique_ptr托管，可通过move函数转移托管权 C++11即此后的空指针以nullptr表示
基于范围的for循环
类似于for(T/auto(&) i:array)的循环，依次访问数组元素
右值引用和move语义
能取地址的即为左值
```
class A(){}
A& ref=A() //error
A&& ref=A() //correct
```
cpp
意义：减少深拷贝开销，可直接把临时对象的成员赋值给当前对象，并将临时对象直接置零
move：把左值转换为右值引用
无序容器——哈希表
包含在#include <unordered_map>头文件中，增删查找的复杂度均为 $O(1)$ 的由于无序，因此不支持upper_bound等算法
正则表达式
包含在#include <regex>头文件中，快速判别字符串格式和提取信息
Lambda表达式
本质上是若干函数对象的封装
```
auto [](T1 ,T2 ,...)->T{
    ;
}
```
cpp
其中->后为返回类型，可以不确定，若不确定则由编译器推导，[]内给定访问外部变量的方式
[]内参数：缺省不访问外部变量，=传值，&传引用，这两类可叠加使用，变量访问方式各有差异
模板类型参数包和模板递归
支持可变个数的类型参数
首先声明类型参数包，然后递归拆解每部分类型，最终设定递归终止条件（空参数包）
万能引用和forward转发
函数模板的形参如果为&&，则事实上为万能引用（可接受右值/左值）
forward包含在头文件#include <utility>下，可用于转发传入的左值/右值到对应函数
e.g.
```
//(已经定义参数分别为左值/右值的函数function)
template<typename T>
void wrapper(T&& arg){
    function(forward<T> arg);//自动决定调用左值/右值为参数的function
}
```
cpp
多线程
包含在头文件#include <thread>下，通过thread实例化线程，不同线程可以并行

C++14#

auto相关
lambda表达式，函数返回类型支持auto自动推导
make_unique
将指针设定为指向特定对象的unique_ptr

C++17#

类模板实参推导
e.g.std::vector v{1,2,3}可被自动推导为vector<int>

结构化绑定
tuple在C++11中引入，以下方式的访问在C++17中引入：

tuple<int,string,double> t{0,3.14,"eee"};
auto [a,b,c]=t;
cout<<a; //0
auto & [x,y,z]=t;
x=1;
cout<<x; //1

cpp

if/switch初始化
折叠表达式
支持可变个数的类型参数将一个二元运算符用于参数包的所有元素上
optional
包含在头文件#include <optional>下，将函数返回值设定为optional<int>后，可以返回其中定义的nullopt（等价于python中的None）
any
安全存放任何类型的数据
在确定其中存放的数据类型的前提下，通过any_cast<T>取出数据，若类型不同，抛出异常
variant
类型安全的union
filesystem
跨平台的文件系统库，包含在头文件#include <filesystem>中

Python#

解释型语言（逐行执行） / 自动内存管理 / 语法简单 / 第三方库丰富
单行注释使用#，多行注释需要选中需要添加注释的段落利用Ctrl+L给每行加#

基本语法#

程序结构
1. 缩进：代替C++中的大括号确定作用域
2. 输出：print函数的参数end给定分隔符
3. 代码书写：没有语句分隔符，换行即可；一行太长可以使用/或()换行
4. 输入：input()函数输入的都是字符串，利用input().split()可将输入拆分为多个对象，分隔符可以作为参数传入/使用正则表达式
变量&数据类型
1. 变量：可以在不指出类型的前提下赋值且多个变量可以同步赋值，定义时必须初始化
  - 所有变量实质上都是指针，所有赋值都是把指针指向某处
```
a is b True # a/b指向同一个地址
a == b True # a/b值相同，不一定指向同一个地址  
a = b # a/b将会指向同一个地址  
```
  python
2. 标准数据类型：int/float/complex/str/list/tuple/dict（*cpp的char是长度为1的str）
  - 相当于类名，可以用于创建对象
  - list/tuple/dict依次由[]/()/{}包裹
  - isinstance函数可以用于判断类型，type函数可以用于获取类型
  - 一切负索引都是倒序计数的对应下标
3. 整数类型任意长，2/8/16进制数通过在数前加0b/0o/0x实现
4. 判断浮点数相等：
```
import sys
def equal(a,b):
return abs(a-b)<=sys.float_info.epsilon  
```
  python
5. 类型转换
  - repr()/str()均转换为字符串，但前者在输出时会显示如\n/\t等等转义字符
  - .join函数<str>=<separator>.join(<list>)将list拼接为str
  - int()/float()/str()/eval()可以把字符串转为对应类型（其中最后一个转为python表达式并求值），原字符串不变，该运算结果是对应类型
    - 其他用法相当于C的强制类型转换运算符
6. 字符串
  - 必须使用单/双/三引号交叉包裹，因此三引号实现“大段注释”实质上是定义了字符串
  - 使用类似于C的下标运算符访问的是子串，不可按位修改
  - 特殊函数：strip()去除头尾两端空白字符

切片：[start:stop:step]从[start,stop)中每step取出对应元素，start/stop中的负数是反向访问
运算符：/是小数除法，//是整除，但如果有操作数是小数，结果一定是小数
分支：没有switch，elif等价于cpp的else if，else等价于cpp的else
循环：循环正常结束后执行后接的else内的语句，若break则不执行
- range函数给出左闭右开的循环区间
- pass仅用于标记，没有实际意义

基础数据结构#

元组tuple
- 由多个逗号分隔的值组成，前后可加括号，不能修改，存放指针
- cpp11后也引入了tuple，定义在头文件#include <tuple>中
- 元组中的元素如果是可以修改元素的类型，则其元素可以被修改
- 元组也定义了运算，语义自然（注意：赋值运算都创建了新对象）
- 如果期望定义单元素的元组，那么需要定义如(100, )，逗号不可省略
  可以与list互换，通过list()/tuple()函数实现
  只能用sorted()得到排序后的元组，不能sort()（因其不可修改）
列表list
支持随机访问的、元素类型可混装的、存放对象指针（指针内存大小固定，但对象类型不定，内存大小不定）的连续数组，接近vector
- 可以使用del list[idx]删除list中的元素
- 不同于元组，list的+=只是扩展元素
- split()函数的返回值就是list，缺省分隔符是制表符/换行符/空格
1. 列表推导式：[a for b in c if d]，使用到该列表时才生成 a：期望在返回的list中含有的元素
  b：a中的需要提取的变量
  c: b的范围集合
  d: b需满足的条件
2. 成员函数：append/extend(list)/insert/remove/reverse/index(x)/len
  其中extend(list)是在尾部添加另一个list，index(x)是在能找到x的前提下返回最早出现的索引，否则报错
- map/filter(func, seq)把tuple/list seq按照func求值/过滤后返回新的tuple/list
1. 配合lambda表达式的列表函数： python中，lambda表达式的形式：lambda arg1, arg2... func
  lambda表达式可以作为map/filter等可以传入函数作为参数的函数参数
2. 使用列表构建二维数组：
```
arr=[1,2,3]
mat=[arr*3] #是一维数组
mat=[arr]*3 #是二维数组，但组成二维数组的三个一维数组是完全相同的

mat=[[0 for j in range(3)] for i in range(3)] #定义了3*3的全0二维数组
```
  python
3. 列表排序：
  - a.sort()将a按规则排序，而sorted(a)返回排序后的a，但a不变；缺省规则：升序排列
  - 自定义比较规则：修改sort()/sorted()函数中的参数key
4. 列表拷贝：
  a=b → 浅浅拷贝，a&b直接指向相同地址
  b=a[:] → 浅拷贝，如果列表中有列表元素那么这些元素指向了同一地址
```
import copy
a=[1,2]
b=copy.deepcopy(a) #深拷贝，二者即完全无关
```
  python
  注意：列表a+=b/a=a+b不相同，前者直接添加元素，后者会构建新对象
字典dict dict={key:value}
- 基于哈希表实现，key必须是可哈希的但可以混合类型
1. 成员函数：keys/items/values/pop(x)/get(k,v)，前三者分别返回字典的键/元素/值序列，pop(x)删除键为x的元素，get(k,v)有键为k的则返回其值，否则返回v
  字典的键不允许重复
集合set
- 基于哈希表实现，元素必须可哈希，但元素无序，接近数学上的集合和cpp的unordered_set
1. 成员函数：add/in，前者添加新元素，后者判断是否在集合中
2. 集合运算：运算符| & -：求并、交、差集
  比较运算符a<=/<b判断a是否是b的子集、真子集

面向对象#

函数
1. 定义函数：不需要指定参数类型，不需要指定返回值类型
```
def func(不带类型的参数表):
    return 返回值
```
  python
2. 返回多个值：return x,y即可，实质上返回了元组
3. 传递参数：按值传递，对于不可变对象，在函数内修改参数并不影响函数外部变量的值；可变对象（列表、字典、自定义类的对象，etc.）则不同
  如果函数修改了形参所指向的地方存放的内容，则实参所指的地方的内容也会修改
4. 参数的默认值：可以以任意顺序，任意个数设置和使用缺省值
5. 参数个数不确定的函数：
```
def func(a, *b) #带**的参数会把调用时的多余参数自动打包为一个元组
    print(b)
func(1, 2, "hello", [1, 2, 3])
def func(a, **b): #带**的参数会把调用时的多余参数打包为一个字典
    print(b)
func(p1=1, p2=2, p3=3)
```
  python
6. 变量作用域：
  - 不加声明，都是局部变量
  - 如果在函数内使用全局变量，需要使用关键字global
7. 内置函数exit()效果与cpp的return 0/exit(0)完全相同
8. 跨文件引用函数/变量
```
from a import func, var #引用a中函数func&变量var`
from b import * #引用b中全部函数和变量
```
  python
面向对象
1. 成员方法不同于cpp的this指针，python需要显式传入参数self
  1. __init__ 构造函数，只能写一个
  2. __del__析构函数，只能写一个
  3. __eq/lt/le/ge/gt/ne__ 比较运算符重载
    a==b等价于a.__eq__(b)，如果没定义后者则匹配b.__eq__(a)，仍未定义则报错
    如果没有定义</>/<=/>=对应方法，缺省设置为None；==缺省设置为比较两对象id
  4. __str/repr__ 强制转换成str/repr
    调用该方法会创建新的对应类型对象
2. 类的定义
```
class 类名:
    def __init__(self, *arg):
    def func(self, *arg):
    ...
```
  python
3. 成员变量
  可以随意添加，不必全部定义在类内
4. 静态属性和静态方法
```
totalsalary=0 #声明静态成员变量需要类内显式初始化
def __init__(self, arg):...
def func(self, arg):...
@staticmethod #装饰器，用于标记以下方法为静态方法
def printsalary(): #静态方法不需要参数self
    print(typename.totalsalary)
@classmethod #针对类自身属性编写的方法，可以访问类属性
def func2(cls, arg):...
```
  python
  如果对某个对象的静态成员变量赋值，则其成为非静态成员
5. 私有属性
```
class A:
	_a=1 #单下划线属性，保护类属性(protected)
    __p=20 #双下划线前缀，私有类属性(private)
    def __init__(self, arg):
        self.__q=30 #私有实例属性
```
  python
  如果需要访问私有属性，则可以通过_<typename>__q访问
6. property
  该函数可以将几个函数封装为同一个属性，调用该属性时自动匹配应当调用的函数
  e.g.
```
class A:
	def __init__(self,x):
		self._q=x
	def setq(self,x):
		self._q=x
	def getq(self):
		return self._q
	def delq(self):
		del self._q
	attr=property(getq,setq,delq) # 参数顺序固定为get,set,del,docstring(若需要)
```
  python
  此后每次调用A.attr时，都会根据运行情况决定将要set/get/del
7. 哈希
  - 不可变的内置对象和自定义类的对象，都是可哈希的，后者哈希值是对象id即地址
  - 如果重载了__eq__则不可哈希，再重载__hash__则可哈希
  - 值相同则哈希值相同
运算符重载
1. __iadd__/__add__/__radd__分别对应+=/对象前缀+/对象后缀+
2. __sub__对应-
3. __setitem__/__getitem__分别对应[]取左值/[]取右值
  在语句实际运行时自动决定取左值/右值
4. __str__/__int__等对应类型转换
5. 仿函数 def __call__(self, arg)相当于cpp的重载operator()的函数对象
6. __le__重载<，可以用于sort
  如果未重载__le__方法，可以使用key=attrgetter()或lambda表达式代替
  注：attrgetter()的参数是类的属性
泛型显然，所有函数参数类型都未规定，自然是泛型
继承和派生
1. 定义派生类：class B(A)表示B的基类为A
2. 构造派生类必须调用基类构造函数：A.__init__(self, arg)
  对派生类对象A，isinstance(A,基类)返回True

函数式程序设计#

python函数的多用途
1. 给变量赋值
2. 作为函数参数
  以上两种用途类似cpp的函数指针
lambda表达式
```
(lambda x,y,z:x+y+z)(1,2,3)
```
python
:前给出lambda表达式参数列表，:后是lambda表达式运算内容
闭包
“记忆”了自由变量的函数（实质相当于仿函数）
对于嵌套函数，带有关键字nonlocal的外层变量可以在内层函数中被修改

偏应用函数

from functools import partial
add=lambda a,b:a+b
add1024=partial(add,1024) #这就完成了一个偏应用函数：x+1024的定义

python

迭代器#

可迭代对象实现了方法__iter__和__next__的对象，可以通过for i in x实现迭代
迭代原理：先调用__iter__，然后重复调用__next__直到抛出exceptIteration
容器和迭代器
需要分离定义两个不同类，否则一次迭代后迭代器始终指向容器末尾，无法实现新一次迭代
仅实现了__getitem__而未定义__iter__的类，会缺省一个迭代器方法

生成器#

定义特殊迭代器，边迭代边计算生成，减少内存开销
作用：惰性计算，简化代码，支持无限序列
示例：

a=(i**2 for i in range(5))
print(a) #无意义，a不是一组值
for x in a:
	print(x, end=" ")

python

yield关键字
- 用于定义生成器，在函数中语义可以视作return
- yield语句被调用时返回迭代器，使用next可以执行yield语句（直到碰到yield语句为止），如果没有，抛出异常
send语句
可以向yield语句传送数据，在没有next/send(None)语句之前，无法send(x)(x!=None)
实现了生成器与外部的双向通信，使生成器可以根据外部信息调整其状态

其他语法特性#

eval``exec``compile
1. eval用于计算表达式的值，注意不能是语句
- e.g.eval(1+2)返回3，eval(a+b)报错
1. exec用于执行语句，传入参数为str，不限长度，没有返回值
- e.g.
```
py="""
def add(a,b):
	return a+b
result=add(3,4)
"""
namespace={} # 作用域可以用字典定义
exec(py,namespace) # 把exec作用域设定为namespace
print(namespace["result"]) # 7
```
  python
reflection反射
- 使程序运行时能动态获取检查、操作对象属性和方法的能力
- 使用dir()列出对象所属类的属性和方法
- 使用hasattr()/setattr()/getattr()实现判断/设置/获取对象属性和方法

异常处理

try:
	... #正常时执行
except:
	... #错误时执行
finally:
	... #不论是否抛出错误都执行

python

装饰器@decorator
在不改变原有代码的前提下扩展函数功能，进行泛化嵌套
```
def deco(func):
	def wrapper(*args,**kwargs): # 因装饰器需要提高泛化能力，不确定被装饰函数的参数表，*args对应未知个数纯参数，**kwargs对应未知个数关键字如age=18,name="aaa"等  
		func(*args,**kwargs)
		print("very good.")
	return wrapper

@deco
def hello():
	print("hello world.")

hello()
```
python
实质上是执行了如下语句
```
hello=deco(hello)
hello()
```
python
输出结果如下
```
> hello world.
> very good.
```
text
python内置装饰器：
- @staticmethod：把方法装饰成静态方法
- @classmethod：把方法装饰成类方法，即调用时自动把当前类作为第一个参数传入
- @property：把方法装饰成属性，然后调用时可以使用类似访问属性的方式

网络爬虫设计#

爬虫用途：在网络上搜集数据、模拟浏览器快速操作和重复操作
浏览器访问网页的完整过程：发送请求->（浏览器附带）请求头->（页面）接收响应（仅能获取html，不能获取css/js）->处理数据->后续操作（模拟表单提交等）

数据获取型爬虫
1. 在对应URL上查看源码，找出包含想要的内容的字符串模式
2. 编写一个可以获取对应网页并通过正则表达式抽取期望信息的程序
实现库
requests最基本，但很容易被反爬且无法爬取js动态生成的内容，只能看到html框架
selenium慢，但可替代
pyppeteer快，是更好的替代，通过向浏览器发送命令模拟用户在浏览器上的输入，让浏览器进行对应操作
pyppeteer
依赖特定版本的Chromium
协程：可以理解为程序内的线程
- pyppeteer爬虫操作依赖协程，关键字（需要import asyncio）：
  - async关键字声明一个函数为协程函数
  - await关键字挂起当前协程直到另一个协程结束
BeautifulSoup
- 用于分析html字串，在效率并未显著降低的前提下替代复杂的正则表达式
html网页中有许多重复出现的tag，格式为<X attr1='xxx' attr2='yyy' ...>text</X>，其中X是tag的名字，attr都是属性，text是正文
tag可以嵌套

数据处理#

numpy
速度快于多维list，支持向量矩阵运算，元素类型必须相同
1. 基本设定
  创建矩阵时，缺省数据类型为浮点型
  在numpy中，axis=0对应行，axis=1对应列，以此类推
  numpy数组生成后，元素不能再增删，使用np.delete等函数会返回新的numpy数组
2. 常用函数
  - a.reshape(a,b,c,d).transpose(i,j,k,l) 把数组a转为(a,b,c,d)的四位数组，然后a/b/c/d依次变为新的i/j/k/l维度
  - squeeze(a) 消除数组的第a维
  - concatenate （可以指定拼接维度）拼接多个数组和列表，参数axis指定拼接的方向（附加元素的排列方向）
  - argwhere 根据参数内的条件返回对应位置，返回类型是list，其中的每个元素是长度数组维度的list，给出符合条件的元素坐标
  - matmul和* 前者是矩阵乘法，后者是Hadamard乘法
  - numpy数组的切片返回视图，对切片修改会直接影响原数组！！（使用np.copy可以避免）
pandas-panel data
需要numpy支持，核心功能是在二维表格上进行各种操作，若有openpyxl(for .xlsx)/xlrd/xlwt(for .xls)支持可以读写excel
Series类是一维表格，DataFrame类是二维表格
注意：其数据虽然是numpy数组，但是由于dtype是object（python底层基类），因此不必限制数据类型相同
- iloc以下标形式访问，loc以标签形式访问
1. Series
  构造函数参数：data-数据 index-行索引
  每个元素带有标签且有下标的一维表格，支持切片
  注意：使用下标切片时左闭右开，标签切片时左闭右闭
  使用concat拼接列表，使用idxmax``argmax返回最大元素的标签/下标
2. DataFrame
  构造函数参数：data-数据 index-行索引 columns-列索引
  数据以二维数组的形式给出，分别具有列标签和行标签
  1. 切片：
    - 使用标签访问元素时，列索引先写
    - 不支持使用行标签/列标签的切片，不建议取单列/单行，使用loc和iloc则全部支持
    - 注意切片仍然返回视图
  2. 修改和增删：
    - 函数drop控制删除，通过参数inplace确定返回副本/修改原对象
  3. 分析和统计：
    - axis参数控制函数沿着哪个轴的方向进行操作
3. excel/csv文件交互
  csv是有逗号分隔符的文本文件，xlsx进行了二进制压缩，可以在excel中从csv导入数据到xlsx
  通过read_excel方法读取xlsx文件，参数依次是文件名、表单名/表单在xlsx中的索引、选取哪列作为列标签
  注意该方法返回的是 value为DataFrame对象的python字典
  通过read_csv方法读取csv文件，需要指定编码以避免乱码
  
  写入xlsx时，需要首先创建ExcelWriter类对象，然后再使用to_excel方法写入数据
  写入csv时，不需要创建对象，直接通过to_csv方法即可写入数据
matplotlib
~~To be filled~~

图像处理#

python中的图像处理依赖pillow（适配torch）或cv2（适配numpy）
0. 图像基本知识
- 对于灰度图像，亮度越高数值越大
- 对于k位图像（uintk），数值取值范围是 $[0,2^k-1]$
- 图像处理操作中，常用0-1内的float
- PNG/JPG格式：前者属于无损压缩，可以表示透明图像；后者属于有损压缩，不能表示透明图像
- 使用切片替代for循环，可以极大提升效率，需要注意numpy切片会直接操作对应内存地址

cv2
- 使用cv2读取图像后的数据是三维numpy数组，其中三通道顺序是B->G->R/二维数组
- 默认图像类型uint8，可以使用numpy自带方法进行类型转换
- 查看图片时会打开python窗口，如果不添加waitkey()会类同爬虫窗口，瞬间消失
- 不同于pillow，opencv的旋转依靠旋转矩阵实现
pillow
- 使用pillow读取图像后的数据是torch的三维tensor，其中三通道顺序是R->G->B/二维数组
- 查看图片时会调用默认图像查看应用
- 改变单个像素可以使用putpixel()方法
pytorch
- 在pytorch中，方法Compose可以用于聚合多个预处理方法，如Normalize/RandomHorizontalFlip等等
常用操作
1. 单张图像变换
  1. 反转变换：处理医疗影像常用，若黑色部分>>白色部分
  2. 对数变换：原始图像值域分布范围过大，可以通过取对数约束
  3. 幂律变换：控制亮暗部分的值域范围，常用于一些校正
2. 算术操作
  1. 图像相加：加噪（叠加一个随机噪声图像），优化训练表现
  2. 图像平均：去噪
  3. 图像相减：找不同
  4. 图像乘除：用于叠加掩膜，构造数据集，消除光影，etc.
图像直方图
1. 定义
  - 横轴：灰度，纵轴：对应灰度的像素个数
  - 直方图的峰不能过偏左/右，否则过暗/亮；也不能过于集中，否则对比度过低
2. 直方图均衡化
  即寻找一个像素值变换函数
  - 理想情况：调整后新的直方图对应的概率分布为均匀的，且变换保序
  - 实际情况：确定多个灰度阶，在每个阶内呈线性

程序设计实习 · 课程笔记

程序设计实习#

C++#

类和对象#

面向对象I#

面向对象II#

面向对象III#

运算符重载#

继承与派生#

多态#

输入输出和文件处理#

函数模板与类模板#

STL#

STL1#

STL2#

高阶特性#

C++98#

C++11#

C++14#

C++17#

Python#

基本语法#

基础数据结构#

面向对象#

函数式程序设计#

迭代器#

生成器#

其他语法特性#

网络爬虫设计#

数据处理#

图像处理#