堆

• 完全二叉树实现：节点i的左子2i，右子2i+1，父节点i/2
  • build_max_heap 复杂度O(n)
  • heap_sort 复杂度O(nlgn)n取最小
  • inset extract_max max_heap 复杂度均为O(n)
• 保持堆性质（递归下调）
  
• 建堆：O(n)次 调用 max_heap复杂为O（lgn）准确上界为O（n）
  
• 直接构造堆时间复杂度为O(n)， 插入构造堆复杂度为O(nlgn)

  优先级队列

• 内部由堆实现
  • 抽取最大值
    

堆操作分析

• 建堆：从n/2至0调用求最大，调整位置使得根最大
• 插入：直接插入数组尾部，递归向上调整，保持堆性质
• 删除最值：直接交换根和尾值。缩小空间（-1），递归向下调整保持堆性质
• 优先队列操作间接调用堆操作
• k路归并，构建k路小根堆，每次取最小值，复杂度O(nlgk）

  快排

• 找出pivit，以pivot为轴心做一次partition，分割成两个子集，对子集递归调用快排
• partiiton过程
  
  
• 快排性能分析：划分极端不对称时，复杂度退化为O(n^2)序列有序时性能退化最严重
• 随机化版本：随机选取pivot
  
• 利用随机化版本，快排期望时间复杂度为O(nlgn)

线性时间排序

• 计数排序
  • n个输入元素每一个都介于0~k之间，且k=O(n)
  • 对每一个输入的元素x都直接确定出比x小的元素的个数，则可以直接将其放入排序后的位置
    
  • 倒序插入是为了保证稳定性，即值相同元素的插入顺序与排序前顺序保持一致
• 基数排序
  • 先按低位排序，然后递归的的向高位排序
  • 复杂度O(d(n+k))
• 桶排序
  • 输入均匀分布时，可以达到线性时间复杂度
  • 桶内以插入排序实现
    
  • θ（n） + n*O(2-1/n) = θ（n）
• 中位数
  • 随机选择算法:平均情况下，顺序统计量可在O(n)复杂度内得到，最坏时间复杂度为O(n^2)
    
  • 最坏时间复杂度为O(n)的顺序统计量
  • pivot 的选择以中位数的中位数来衡量，保证避免最坏划分（组划分size>=5的奇数个，都可以保证线性时间复杂度）
    
  • select 方法嵌入快排的partition，可以使得快排的最坏时间复杂度为O(nlgn)
  • 任意序列的O(n)算法
    
  • 寻找两个已排序数组 （长度均为n）的中位数
    
  • 找出已排序的前i个最大数
    • 排序，输出前i个数，复杂度θ(nlgn)
    • 建立优先队列，输出i次最大值θ(n+ilgn)
    • 顺序统计量量找出第i大元素，然后以第i大元素作为pivot进行partition，将partiton结果排序 θ(n +ilgi)
    • 顺序读入元素，维护一个i个元素的大根堆，依次输出堆中元素。复杂度 θ（nlgi）

循环不变式与算法正确性

• 初始化：循环第一轮开始前是正确的
• 保持： 每次迭代之后，下次迭代开始前，保持正确
• 终止： 循环节俗时，算法性质保持正确
• 以插入排序为例：一个元素必定有序，插入一个元素保证有序，迭代至最后一个元素，整体必然有序

  传统分析方法与表示

• 最坏情况：运行时间的上界
• 合并排序使用分治法，最坏运行情况为O(nlgn)
• 在合并排序中对小数组使用插入排序
  • n个元素分为定长k的小数组排序，共分为n/k个子数组，每个时间复杂度为kk，总的时间复杂度为n/kk*k = O(nk)
  • 合并n/k个小数组，复杂度最差为n*lg（n/k）

• 上下渐进界
  
  

• 代换法

  • 猜测解的形式，用数学归纳写出解有效的常数，调整边界条件
    
• 递归树方法：每层代价之和即为代价上界
  • 对T(n) = 3T(n/4) + cn^2
    
• 主定理
  

ER模型转为关系模型转换规则

• 每一个实体转化为一个关系模式，实体标识符即关系模式的主键
• 二元关系转换
  • 实体间联系（1:1）：两个实体类型中转换乘关系模式中任意一个关系模式的属性加入另一个关系模式的键和联系类型属性
  • 实体间联系（1:N）：N端实体烈性转换扯个关系模式中加入1端实体类型的键和联系属性
  • 实体间联系（M:N）：联系类型转为关系模式，属性为两端实体键加上联系属性，键为两端实体键的组合
• 最小依赖集
  • 右边都是单属性
  • 不存在冗余关系（不存在不影响函数依赖集的函数依赖：即存在的函数依赖都对函数依赖集有影响）
  • 左边无冗余属性（不存在左边的真子集可以替代父集，即左边集均是最小集）
    
    
    
    
    
    
• 函数依赖集求解
  • 右边分裂为单属性
  • 左边消除冗余属性 （消除不影响函数依赖集的函数依赖）
  • 消除冗余依赖（消除可由其它依赖推到得出的函数依赖）
    

• 分解成2NF：消除非主属性对候选键的局部依赖，拆分候选键
• 分解成3NF：消除非主属性对候选键的传递依赖，直接关联候选键与非主属性
• 分解成3NF的算法：
  • 求出最小依赖集，左部相同依赖合并
  • 每一个依赖关系构成一个模式
  • 在构成模式集中，每个模式都不包含候选键，则吧候选键作为一个模式加入模式集

选择运算

• A1：线性搜索，平均代价Br/2，最坏情况Br
• A2: 二分搜索，属性有序，代价[logBr]

  索引选择

• A3: (主索引，码属性等值比较)可以检索到唯一一条满足条件的记录，代价：B+树树高加上读取一条记录I/O代价
• A4: (主索引，非码属性等值比较)主索引可以检索到多条满足条件的记录，且多条记录顺序存储，代价：B+树树高加上具有搜索码值的盘块数
• A5: (辅助索引，等值比较)索引字段为码属性直接得到一条记录．索引字段为非码属性，得到多条记录

  比较选择

• A6: (主索引，比较)B+树有序主索引
• A7: (辅助索引，比较)有序辅助索引，小值从小段开始，大值从　大端开始

  比较选择

• A8: 索引合取（取交）先现则满足一个条件的记录，加入缓冲区，在缓冲区中验证其他条件
• A9: (组合所用合取)直接利用合适的符合索引查询
• A10: (记录标识符的交)每个条件遍历标记一边，取所有被标记的交际
• A11: (记录标识符的并）逐一扫描索引获取满足单个条件的元祖指针，将所有指针集做并集

连接运算

• 嵌套循环（重名属性会出现）
• 块嵌套循环，每次在块内循环嵌套检查元组匹配，有效减少比较次数
• 索引嵌套循环连接：嵌套循环连接的内层如果有索引，使用索引代替循环
• 归并链接：用于自然链接和等值连接
  • 双有序直接有序归并
  • 单有序，归并后，对索引项进行按地址排序，可实现有序
• 消除重复: 代价高，明确声明是否去重
  • 归并/散列可直接在过程中消除重复
• 集合
  • 并集：　Hr建立散列索引，将Hs中元组加入到上诉散列索引中，条件是该元组不在散列索引中，散列索引最终即结果
  • 交集：　Hr建立散列索引，对Hs中元组探查散列索引，出现在散列索引的记录放入结果
  • 差集：　Hr建立散列索引，对Hs中元组探查散列索引，出现在散列索引的记录从索引中删除

外连接

-　计算连接法：
    - 左外连接：计算链接，将左集未参与链接集合扩展放入结果
    - 右外连接：计算链接，将右集未参与链接集合扩展放入结果
    - 全外连接：计算链接，将左右集未参与链接集合扩展放入结果
- 嵌套修改法
    - 左外连接：左边外循环，右表内循环，内外匹配加入结果，内部均不匹配的外记录也加入结果
    - 右外连接：右边外循环，左表内循环，内外匹配加入结果，内部均不匹配的外记录也加入结果
- 扩展归并连接获得自然链接和等值全外联
    - 归并完成，将不与另一关系任一记录匹配的记录加入结果

表达式计算

• 实体化：中间结果实体化，供下一层运算，磁盘代价高，双缓冲降低磁盘代价
• 流水线：生产者驱动流水线，需求驱动流水线

###　内容说明

• 一项课程作业Java编写Ｓｏｃｋｅｔ长连接监控分布式终端，并将终端状态写入数据库供前端查询

####　基础：c++/Posix/APUE/Mysql&sqlite

####　核心内容：Socket/线程/并发/同步

难点：Java语言未系统学习过,Java中JDBC操作数据库未接触过　

• 过程:
  • 心跳包程序理解重写:
    • 问题与技能：java语言面向对象，Java语言的Socket使用，Java异常基本使用
    • 解决方法：
      • 熟悉一下Java语法，套用c++面向对象方法（其实面向对象部分基本一样，包括Python的面向对象）
      • 抄代码，理解代码逻辑，（相信每一个关键词，每一行代码都有其意义和功能）学习新语言新工具最快的方式就是使用它
      • 就遇到问题集中问题点查询，避免盲目查询，一次解决一个Bug,多用Google和Stackoverflow(超级高效)
  • Server端处理
    • WatchDog监视新连接
    • 多线程处理各连接内部报文，超时未收到报文，清除连接释放资源
    • 加入机器状态协议消息标识
    • 考虑了多种通信状况的可能，终于理解TCP/IP为什么设计那么多头部和校验了
  • 本地Hashmap缓存消息较少数据库读写次数
    • 设计之初没考虑状态包对数据库的高频读写更新，后来为了减少数据库读写在本地建立一个最新状态缓存即Hashmap映射集，一般尽量只更新本地状态缓存即Hashmap,必要时读写数据库
    • hashmap可能不是很好的实现，健壮性欠考虑，考虑用Redis或者sqlite作为本地缓存数据库，效果应该会好些
  • 数据库操作更新
    • sql语句嵌入到Java语句中（JDBC），基本的增删改查，封装成了一个查询类
    • 之前学过Mysql和sqlite的基本操作．在Java里是通过是所谓的JDBC（其实还是执行sql语句），这两天看了Python的数据库接口，发现都一样的执行sql语句

后记

• 好奇Java的线程实现和同步，之前看Posix和APUE的线程章节，一堆的Mutex和lock,感觉Java直接靠关键字synchronized 就搞定了（其实内部还是锁机制）
• 不管哪种语言
  • Socket，一样的bind/connect
  • 线程的同步，一样的加锁互斥等待同步资源共享
  • 线程/进程通信，一样的写进一个＂文件＂，给另一个进程读：信号/信号量（非典型读写），，共享文件/管道（典型读写）

第一章 http概述

1.3.1 媒体类型

- http为每种web传输的数据格式加上MIME类型数据标签（multipurpose internet mail 

1.4 事务

• 一个请求 + 一个响应 构成一个事务，通过 格式化的http报文实现

  1.4.1 方法

• GET 从服务器向客户端发送命名资源
• PUT 将客户端数据存储到命名服务器中
• DELETE 从服务器删除命名资源
• POST 将客户端信息发送到一个服务器网关应用程序
• HEAD 仅发送命名资源响应中的HTTP首部

1.4.2 状态码

- 200 ok 
- 302 redirect
- 404 notfound

###第二章 URL与资源

• 在获取用户URL的源端处处理组件不完全字符

第三章 HTTP报文

3.1 报文流

• 不管是请求还是响应，所有报文向下游流动

  3.2 报文组成部分

  request：
  
  
  
  respose:
  
  
  
  ####### 3.2.2 起始行
• 请求行：请求报文起始行：说明要做什么，响应报文说明：发生了什么
• 响应行： http 版本，状态码， 状态文本描述
• 状态码：
  
  ####### 3.3.1 方法
• 安全方法: GET HEAD 不产生动作即不会再拂去其上产生什么结果
• HEAD:不获取资源情况下查看资源情况，查看响应状态码，了解对象情况，查看首部，了解资源是否被修改
• TRACE：行程最后一站服务器弹回一条响应，携带收到的原始请求报文，方便发送方查看原始报文是否被修改

状态码与首部：查字典http 口袋书

第四章 连接管理

• tcp 的socket 套接字通信
  

####### 4.2 HTTP 事务时延

• url 地址端口映射， tcp连接的建立，端口的释放时延
• tcp链接建立的握手机制
• tcp慢启动拥塞控制
• 捎带确认的tcp延迟算法
• time_wait 时延和端口耗尽

####### 4.4 并行连接

• 并行连接可以加快加载速度，但是不是一定可以加快加载速度
• 多个对象同时出现在页面，让用户感觉好像加快了加载

####### 4.5 持久连接

• 在http设备事务处理结束之后将tcp连接保持在打开状态直到客户端决定关闭
• http/1.0 + keep—live 连接
  客户端通过包含connection：keep_live首部请求将连接保持在打开状态
  服务器允许下一条请求将连接保持在打开状态，将响应中包含相同首部
  响应中没有conncetion： keep-live首部，客户端认为服务器不支持keep—live，会在响应之后关闭连接
• keep-alive通用首部选项
  timeout： 响应首部发送，服务器保持连接活跃的时间
  max： 响应首部发送，服务器可以保持的活跃的连接数

####### 4.6 管道化连接

####### 4.7 连接关闭

• 客户端、服务器、代理都可以在任何时刻关闭一条TCP传输连接
• 事务多次执行所得结果相同， 则该事物是幂等的（GET\ HEA\ PUT\DELETE\ TRACE\ OPTIONS）

第五章 http结构

• web服务器动作内容： 建立连接，接受请求，处理请求，访问资源，构建响应，发送响应，记录事物处理过程
• 新连接添加到web服务器列表中，并驾驶连接的数据传输准备
• ip地址解析成主机名用于访问控制和日志记录，但是会降低web事务处理速度
• 服务器通过ident协议找到发起连接的用户名用于日志记录
• 报文的内部解析
  

第六章 代理

• 代理连接的是使用相同协议的应用程序，网关连接的是使用不同协议的端点
• 反向代理代替web服务器处理请求必要时向web服务器请求资源
• 网络交换代理：通过缓存减轻节点拥塞
• 动态父代理：
  • 负载均衡：根据父代理工作负载决定选择哪一个父代理
  • 地理位置附近的路由
  • 协议类型路由
  • 基于订购的路由，高性能付费用户
    
• 没有设置科幻段使用代理时，发送部分URL
• 设置使用客户端代理时，发送完整URL
• 通用代理服务器应该既支持完整URL，也支持部分URL
  ####### 追踪报文
• via首部列出把报文途径的每个节点的有关信息
• max-forward 最大转发次数

####### 代理认证

• 受限请求到达服务器，服务器返回一个要求范文证书的的407代码里认证请求状态码
• 用户收到407 响应，尝试从本地数据库寻找证书
• 获得证书，客户端重新发送请求，在proxy-authorization首部字段提供所要求的的证书
• 证书有效，代理将院士请求沿着传输链路向下传送，否则发送另外一条407 应答

第七章 缓存

• 缓存：减少冗余数据传输，缓解网络瓶颈，降低对原始服务器的要求，降低时延
• http再验证（revalidation）：缓存与服务器一致性验证
  • 再验证命中：响应http304not modified
  • 再验证未命中：响应普通带内容的http200ok（更新缓存）
  • 对象被删除： 响应404not found 缓存删除相应副本
• 字节命中率：缓存提供的字节在传输的所有字节中所占的比例
• 提高文档命中率，阻止通往外部的web事务，有理由降低延迟， 提高字节命中率，阻止字节传向因特网，节省带宽
• 缓存响应与服务器响应的区分： 缓存响应的date标签早于当前时间，服务器响应的data标签晚于当前时间
  

缓存副本新鲜度

文档过期

• cache-control 首部：max-age 相对第一次生成时间的最大合法生存时间（version 1.1）
• Expires 首部： 过期时间 （version 1.0）

  服务器再验证： 缓存文档过期，向服务器请求验证文档是否改变，改变则更新文档，为改变则跟新缓存文档首部（date）

• 条件再验证（条件GET）
  • if-modified-since： 如果指定日期之后修改，执行GET请求，更新缓存
  • if-none-match ：文档修改时更新版本标签，实体标签修改后条件首部可执行，实现缓存更新
• no-store ：禁止缓存对响应复制
• no-cache ：缓存本地，新鲜度验证之前不能提供给客户端

第八章 网关隧道及中继

• 协议网关
  
• 服务器协议网关、服务器端安全网关、客户端安全网关、应用程序服务器
• web 隧道

  • web隧道用http连接传送非http流量，可以穿过只允许web流量的防火墙
    

第九章 爬虫

• 避免环路冗余，url规则化处理
• 支持host首部以区别虚拟主机上的不同服务器
• 条件请求（GET）减少页面请求冗余重复

第十一章 cookie

• 会话cookie：记录用户访问站点时的设置和偏好，用户推出浏览器时删除
• 持久cookie： 硬盘存储，过期时间与临时cookie不同

  cookie:服务器为了跟踪用户而产生的id识别码，服务器根据id累计访问者的数据库信息

第十二章 认证

• http质询与响应

  服务器收到http请求时，响应一个“认证质询”要求用户提供保密信息说明身份，
  再次发起请求时，要求附上保密证书（用户名和密码），证书不匹配则再次质询客户端，并产生错误信息

• 摘要认证： 只发送密码摘要，不再明文发送密码本身
• 摘要认证中使用随机数随机化摘要，随机数由www-authenticate 质询从服务器发送给客户端
  

第十四章 http安全

https

• 增加传输安全层，请求和响应全部加密处理
  

第十七章 内容协商

• 服务器驱动协商：http服务器根据accept首部集自动评估发送的响应类型
• Apache web服务器内容协商根据type-map类型映射文件，查找变体和先关内容协商首部集
  MultiViews指令自动为目录创建type-map文件

• 透明协商：代理了解客户需求，代替客户向服务器请求相应最佳匹配变体类型

  不同变体代表文件类型不一样，必须同时缓存变体和器请求首部、服务器响应首部，代理选择最合适变体方会给用户

• 转码：服务器不能满足客户端请求时，将已存在文档转化为用户可用文档

1. 格式转换
2. 信息综合
3. 内容注入

• 即时转换比静态预生成更加容易实现

第二十章 重定向与负载均衡

• http重定向：短的重定向白问发回给客户端，或者找到负载最想内容服务器做负载均衡，重定向服务器回到用户端IP地址

  增加用户时延，原始服务器处理重定向流量，重定向服务器瘫痪导致站点瘫痪

• DNS 重定向：DNS解析返回的ip地址是多个服务器地址的轮转或者负载最小选择或者跳过故障服务器（故障屏蔽）

  DNS缓存失效，同一个主机的多个服务被分支到多个服务器，每次解析得到的DNS地址均不一样

• 任播寻址： 多个分离服务器拥有相同IP地址，通过主干路由器的最毒路径路由功能将客户请求发送给最近服务器

• IP MAC转发
  

• IP地址转发
  

• 用户选择配置从代理服务器上获取内容

  代理崩溃时，系统无法联系原始服务器

• 记录内容:http方法，http版本，请求资源url，响应状态码，请求与响应报文尺寸，事务开始时间戳，referer首部，user-agent 首部值

• 日志格式
  

5.2流和file对象

1
2
3

#include <wchar.h>
int fwide(FILE *fp, int mode);
Returns: positive if stream is wide oriented,negative if stream is byte oriented,or 0 if stream has no orientation

• mode 负：字节定向，mode 正:宽字节定向， mode 0：不设置流定向但是返回流定向值

5.4缓冲

IO缓冲方式：全缓冲（缓冲区满存入磁盘），行缓冲（收到换行符存入磁盘），不带缓冲

1. 标准错误不缓冲
2. 终端设备行缓冲
3. 其他全缓冲

1
2
3
4
5
6
7
8
9
10
11

#include <stdio.h>
void setbuf(FILE *restrict fp, char *restrict buf );
int setvbuf(FILE *restrict fp, char *restrict buf, int mode,size_t size);
        Returns: 0 if OK, nonzero on error
fp: 已打开的文件指针
buf:未未指定缓冲的流指定缓冲区
size： 制定的缓冲区大小
mode：
 * _IOFBF   全缓冲
 * _IOLBF   行缓冲
 * _IONBF   不缓冲

5.5 打开流

1
2
3
4
5

#include <stdio.h>
FILE *fopen(const char *restrict pathname, const char *restrict type);
FILE *freopen(const char *restrict pathname, const char *restrict type,FILE *restrict fp);
FILE *fdopen(int fd, const char *type);
All three return: file pointer if OK, NULL on error

• fopen 指定方式读取pathname路径名指定的文件
• freopen 指定流上打开指定文件
• fdopen 关联一和IO流和一个指定文件指针

5.6 读写流

1
2
3
4
5

#include <stdio.h>
int getc(FILE *fp);
int fgetc(FILE *fp);
int getchar(void);
All three return: next character if OK, EOF on end of file or error

1
2
3
4
5

#include <stdio.h>
int ferror(FILE *fp);
int feof(FILE *fp);
Both return: nonzero (true) if condition is true, 0 (false) otherwise
void clearerr(FILE *fp);

• 每个问价对象维护一个出错标志和一个结束标志，clearerr清除这两个标志

  1 2 3

  #include <stdio.h> int ungetc(int c, FILE *fp); Returns: c if OK, EOF on error

• 字符压回流中，顺序与读出相反（暂时写回缓冲区，并未写回磁盘）

1
2
3
4
5

#include <stdio.h>
int putc(int c, FILE *fp);
int fputc(int c, FILE *fp);
int putchar(int c);
            All three return: c if OK, EOF on error

• 行读入

  1 2 3 4 5 6 7

  #include <stdio.h> char *fgets(char *restrict buf, int n, FILE *restrict fp); char *gets(char *buf ); Both return: buf if OK, NULL on end of file or error int fputs(const char *restrict str, FILE *restrict fp); int puts(const char *str); Both return: non-negative value if OK, EOF on error

5.9 二进制IO

1
2
3
4
5
6

#include <stdio.h>
size_t fread(void *restrict ptr, size_t size, size_t nobj,FILE *restrict fp);
size_t fwrite(const void *restrict ptr, size_t size, size_t nobj,FILE *restrict fp);
                            Both return: number of objects read or written
size : object size
nobj : number of object

5.10 定位流

1
2
3
4
5
6
7
8
9
10
11
12

#include <stdio.h>
long ftell(FILE *fp);
                    Returns: current file position indicator if OK, .1L on error
int fseek(FILE *fp, long offset, int whence);
                    Returns: 0 if OK, .1 on error
void rewind(FILE *fp); 流指针返回初始位置
#include <stdio.h>
int fgetpos(FILE *restrict fp, fpos_t *restrict pos);
将文件位置指示器存入pos
int fsetpos(FILE *fp, const fpos_t *pos);
将文件位置指示器设置为pos
            Both return: 0 if OK, nonzero on error

5.11格式化IO

• output

  1 2 3 4 5 6 7 8 9 10

  #include <stdio.h> int printf(const char *restrict format, ...); int fprintf(FILE *restrict fp, const char *restrict format, ...); int dprintf(int fd, const char *restrict format, ...); All three return: number of characters output if OK, negative value if output error int sprintf(char *restrict buf, const char *restrict format, ...); Returns: number of characters stored in array if OK, negative value if encoding error int snprintf(char *restrict buf, size_t n,const char *restrict format, ...); Returns: number of characters that would have been stored in array if buffer was large enough, negative value if encoding error

• input

  1 2 3 4 5

  #include <stdio.h> int scanf(const char *restrict format, ...); int fscanf(FILE *restrict fp, const char *restrict format, ...); int sscanf(const char *restrict buf, const char *restrict format, ...); All three return: number of input items assigned,EOF if input error or end of file before any conversion

第一章关于对象

• c++在布局和存取时间的额外负担主要有virtual引起
  • virtual function：运行期动态绑定
  • virtual base class ：base class多次出现在派生类中，但只有一个单一而被共享的实体（虚基类）
    
    

• 对象模型

  • 简单模型：每一个地址slot指向一个成员
    

  • 表格模型：数据表和成员函数表

    1. 数据表包含数据本身
    2. 成员函数表包含指向每个成员函数的指针slot
       

• 虚函数表
  • 每个class产生一堆指向virtual function的指针，，指针形成一个virtual function table；
  • 每一个class object 添加一个指向virtual function table 的指针vptr
  • 每一个class 关联一个type_info object由虚函数表指出

    被指定的object在执行点之前是无法确定类型的，必须通过指针或者引用操作实现

• c++支持多态的方式

  • 隐含转化操作，子类指针赋值给父类指针
  • virtual function
  • dynamic_cast 和 typeid
  • 基类定义接口，通过virtual function方式，在运行时确定object类型并执行相应操作

• 继承后类及对象的内存布局

  • 继承关系
    
  • 内存布局
    
  • 虚函数表

第二章 构造函数

2.1 default constructor 的构建

• 生成default constructor 的要素：
  • 含有member object 且member object 均有default constructor
  • class本身无任何constructor，则调用constructor 时编辑器将为class合成一个default constructor
  • 以member objects 在class 声明次序调用各个member object 的 default constructor
    如果derived class 拥有多个constructor 但是没有default constructor，编译器将扩张每一个consturctor，加入每一个必要的基类default constructor,但不会再合成default constructor

2.1.1“带有default constructor ”的base class ：

• 自动合成default constructor

  - class 声明（继承）一个virtual function
  - class 派生自一个继承串联，其中至少一个virtual base class
  

• 自动合成过程
  • 产生一个virtual function table，内放class的virtual functions 地址
  • 每一个class object合成一个pointer（vptr）指向class 的virtual function table
    已定义constructor则扩展，未定义则合成default constructor， 保证正确初始化每一个class object 的vptr

2.1.2“带有一个virtual base class”的class

• 在derived class object 的每一个virtual base class 中插入一个指向，经由pointer 和reference 存取virtual base class 的操作由这个指针完整（指向同一份内容）
  • 已定义constructor则扩展，未定义则合成default constructor， 保证允许每一个virtual base class 执行器存取操作

• summary:合成 implicit nontrivial default constructor
  • 借用member object 或者 base class 的default constructor
  • 为每一个object 初始化virtual function机制 或者 virtual base机制
  • 除以上以外，如无任何声明constructor 则不会合成default constructor
• 合成的default constructor 中只有base class objects 和member class objects 被初始化，其他nonstatic data member，指针，数组都不会自动初始化
• 解析
  ``
  1. 不是任何class都会合成 deafault constructor，只有member object 或者 base class 有default constructor 时，或者需要初始化virtual function 机制和virtual base class 机制时，合成default constructor
  2. 编译器合成的default constructor 并不会明确初始化每一个data member值
     ``
     ####2.2 copy constructor 的构建

     • 执行copy constructor的三种情况：
       • 赋值
       • 作为参数传递
       • 作为返回值
     • default memberwise initialization
       • 对于member data 逐一赋值
       • 对于member function 递归调用 memberwise initialization
     • 当class 不展现一个“bitewise copy semantics”(如下四种情况)，需要合成copy constructor

  3. class 内包含一个member object 且后者（声明或者合成）copy constrctor 时
  4. class 继承一个base class 且后者（声明或者合成）copy constrctor 时
  5. class 声明至少一个virtual function时
  6. class 派生自一个继承串联，其中至少一个virtual base class

2.3 program transformation semantics

• explicit initialization:直接逐位赋值member data
  • argument initialization:参数构造临时对象并copy constrcuct
  • copy construct and 返回引用

2.4 member initialization list

• initial 时：= 操作符以arguement初始化对象时分为三步：1、以arguement 构造一个 临时对象，2、将临时对象copy给目标对象，3、销毁临时对象
  • 初始化顺序是由members声明次序决定的，不是由member list 顺序决定的；
  • member list 中初始化先于explicit assignment：即：之后的初始化先于{}内部member data的初始化或者赋值
    X::x(int v):j(v){i = j;}j 的初始化先于i的初始化

第三章 the semantaic of data

3.1 data member 绑定

- 局域绑定

3.2 data member layout

- 同一access session 按照声明顺序合并，静态成员不存在class 内部

3.3 data member 存取

- static data member 
 > 独立于class 之外，不论是继承virtual base class而来或者函数调用得到的static 都是直接存取，通过指针和通过对象存取是一样的
- nonstatic data member
 > 通过指向对象的指针和对象访问一致的，当访问的member data是一个从virtual base class 继承而来的member时，指针访问在运行时才能确定
- 多重继承
![pointer实现：共享虚基类](http://odfcr7qs4.bkt.clouddn.com/IMG_0073.PNG)
![offset实现：共享虚基类](http://odfcr7qs4.bkt.clouddn.com/IMG_0074.PNG)
- 多重继承的数据布局
![](http://images2015.cnblogs.com/blog/900750/201702/900750-20170211192953869-280093158.png)
- 虚拟继承：
    - 指针方式实现

-  虚函数表首项偏移指向虚基类 

3.6 pointer to data member

* &Pointer：：z   “取一个nonstaic data member，得到它在class 中的偏移量”
* &origin.z   “取一个class object 的data menber地址， 得到member在内存中的真正地址”
* 继承层次越深，指针代码执行速度越慢

第四章 the semantics of function

4.1 member 调用方式

* nonstatic member function
  〉 0. 安插this指针   
    1. 对nonstatic member function 经由this 指针存取
    2. 将member function 改写成独一无二（name mangling）的外部函数
  - nonstatic member function 与外部函数的访问性能是一样的
* virtual member function
 >  经由对象调用virtual function 被处理为编译绑定，与nonstatic member function的调用方式一致
* static member function
 >  0. 通过指针或者对象调用静态成员函数都被当做一般函数处理
 〉 1. static member function 没有this 指针，被当做一般函数处理

第五章 the semantics of construction destruction and copy

5.1 无继承的对象构造

1. bitwise member copy
   1. ADT class 执行default copy constructor，copy constructor， destructor，但是并不产生相应函数

• 构造函数初始化vptr，构造函数不可以虚，构造函数内部调用虚拟函数不能实现多态只能调用本地版本
• 传值方式传回一个local class object 时最好定义一个copy constructor，以避免被NRV优化

  5.2 继承体系下的对象构造

• vptr 初始化语义学
  • 在class的constructor 或者 destructor 中调用一个virtual function ，调用的必须是本class 中的那个function实体
  • vptr初始化时间在base class constructor 调用后member initialization list 所列members之前，以保证初始化过程中幻化出完整的基类对象
    

• 只有在默认行为不安全或者不正确是才需要设计一个copy assignment operator
  

1. dervied class constructor 中所有virtual base class 和base class constructor 被调用
2. 对象vprt被设置，指向相关virtual function table
3. member initialization list 在constructor 内部展开
4. 执行程序直接赋值代码和生成对象的代码

• 不要在虚基类中声明数据，避免copy assignment operator 的不完整性

5.5 semantics of destructor

• 如果class 未声明destructor 且member object 拥有destructor ，编译器自动合成destructor，否则不合成

  1. destructor 函数本身最先执行
  2. 拥有destructor 的 member class object按声明顺序相反执行自己的destructor
  3. object 内带vptr 重置，指向响应基类virtual table
  4. 直接上层的nonvirtual base class 以其声明的顺序的逆序执行destructor
  5. virtual base class 按照与构造顺序相反的顺序执行destructor

第六章 runtime semantics

6.2 new delete 运算符

- new 和delete 底层以malloc 和free 实现
- new 失败，必须在new 内部完成已分配空间的释放

6.3 临时对象的处理

- 临时对象的销毁，必须在完整表达式求值过程的最后，该完整表达式造成临时对象的生成
- 如果临时对象被reference 对象将残留到reference 生命周期结束

第七章 on the cusp of the object model

template

> member function 只在使用时具现出来
- template class 中所有与类型有关的检验，如果牵涉到template 参数，都将延迟到真正的具现操作发生

异常处理

- exception handing 快速检阅
> 0. throw 子句，发出exception
  1. 多个catch 子句捕获相应类型的exception
  2. try区段处理
- 异常抛出后，控制权转移，函数调用也被推离，在函数堆栈推离前local class objects 的destructor会被调用

直到找到一个吻合的catch子句，或者直到堆栈被unwound而terminate已被调用

- 异常对象以复制构造方式传入catch子句，处理完成后后local excepton object被销毁，处理终结或者将原异常对象继续抛出

RTTI

>  dynamic_cast 通过vptr指向type_info运行时判定类型实现转型，比static_cast代价高但是更安全
>  dynamic_cast 应用于pointer 时，安全转型则直接向下转型，不安全则pointer置0
>  dynamic_cast 应用于reference 时，安全转型则直接向下转型，不安全则返回一个bad_cast exception
>  typeid 返回一个 const reference，类型为type_info,

learn from this

• DP

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

  class Solution { public: int numSquares(int n) { if(n<=0)return 0; int * dp = new int[n+1](); for(int i=1;i<=n;i++){ dp[i]= INT_MAX; for(int j =1;j*j <=i;j++){ int tmp = dp[i-j*j]+1; dp[i]=dp[i]<tmp?dp[i]:tmp; } } //for(int i=0;i<=n;i++)cout<< dp[i]<<' '; return dp[n]; } };

• BFS

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

  class Solution { public: int numSquares(int n) { if (n <= 0)return 0; else if(pow((int)sqrt(n),2) == n)return 1; vector<int> perfectSquares;//candinates vector<int> cntPerfectSquares(n);//count_index for (int i = 1; i*i <= n; i++) { perfectSquares.push_back(i*i); cntPerfectSquares[i*i - 1] = 1; } queue<int> searchQ; for (auto& i : perfectSquares) searchQ.push(i); int currCntPerfectSquares = 1; while (!searchQ.empty())//BFS { currCntPerfectSquares++; int searchQSize = searchQ.size(); for (int i = 0; i < searchQSize; i++) { int tmp = searchQ.front(); for (auto& j : perfectSquares) { if (tmp + j == n)return currCntPerfectSquares; else if ((tmp + j < n) && (cntPerfectSquares[tmp + j - 1] == 0)) { cntPerfectSquares[tmp + j - 1] = currCntPerfectSquares; searchQ.push(tmp + j); } else if (tmp + j > n)break; } searchQ.pop(); } } return 0; } };

• 定义const 成员函数时,const 位于参数与函数体之间
• const成员函数只能调用 const成员函数,保证不做修改
• 禁用默认函数(构造,赋值构造等),将默认函数私有化private
• const成员变量只能参数列表初始化
• 成员函数内部static变量为所有调用该成员函数的对象共有
• this指针不用于static 成员函数中,不能指向const 对象
• 隐藏的父类成员,子类不可直接调用,通过父类共有函数调用
• 派生类同名成员或者函数 屏蔽父类同名成员或者函数
• 为基类设置默认构造函数,方便子类继承
• 基类声明虚函数后,子类同名自动定义为虚函数
• 构造函数不可以是虚成员函数, 析构函数可以
• 重载在编译时期绑定,虚函数(多态) 运行期间绑定
• 覆盖:多态虚函数函数签名相同, 遮蔽: 共享函数名但签名不同
• 抽象基类确保派生类必须定义某些特定函数（纯虚函数），否则派生类不可以实例化
• 抽象基类：包含一个纯虚函数　　virtual =0;

• 抽象基类不可实例化，可派生，其派生类必须覆盖全部纯虚函数才可被实例化

• 重载不改变符号优先级

• 除new new[] delete delete[]外以顶层函数重载操作符必须包含一个类对象
• 操作符[] ()　->必须以类成员形式重载
• 以成员函数重载二元操作符，只需一个参数，而以顶层函数重载二元操作符时必须两个参数
• 使用顶层函数重载非对象操作数可出现在操作符左边，类成员函数重载时第一个操作数必须是类对象
  -　praivete member only access by menberfunction and friend funtion.
• protect member can be accessed by menber funtion, friend function and member function of derived class
• using friend function only in overloading operator as possible as we can
• 前置自增：　operator++() 后置自增：　operator++(int );
• new new[] return type must be void*, the first parameter must be size_t
• delete delete[] return type must be void*, the first parameter must be void * wihch point to the object need to destroied

• 对象不能属于模板类，只能属于模板类实例

• duque :双端插入删除效率一致，vector 尾部插入删除效率高

• protect成员只能被该类和子类的方法访问
• 父类成员必须定义默认构造函数，否则子类构造前出现编译错误
• 同一域名空间，函数名相同，签名不同
• 编译期绑定确定绑定函数，也称为静态多态

  重写:覆盖(override)

• 虚函数
• 子类空间，函数名相同，签名相同

  重定义：遮蔽（redefine）

• 非虚函数，子类成员函数与父类成员函数同名
• 虚函数，子类成员函数与父类成员函数同名但不同签名

  多态：（动态多态）

• 运行期确定绑定对象，也称为动态多态
• 同签名虚函数构成覆盖
• 父类指针指向子类对象，调用属于子类的函数

• 顶层函数重载操作符
  • 非对象操作数可以出现在操作符左边
  • 使用类成员函数重载是，第一操作数必须是累的对象
  • 顶层函数不能直接访问类私有成员，最好将顶层重载函数设为友元函数，方便直接访问私有数据成员
• 重载[]: 重载为成员函数，检查下标 ， 返回一个引用适应左值情况
• 重载（）： 函数调用重载操作符
• 析构函数出现，必须定义拷贝构造，赋值构造函数

• 继承下的构造函数：
  • 先父类按继承顺序构造，再成员按顺序构造，最后派生类构造
  • 每一层只负责调用父类构造函数
  • 基类没有默认构造时，子类构造函数必须显式调用基类的某个构造函数
  • 创建派生类对象时，自动调用基类默认构造函数
    • 子类有构造函数，基类没有默认构造，创建子类对象时，自动创建基类默认构造函数
    • 子类没有构造函数，基类有默认构造，创建子类对象时，自动调用基类默认构造
    • 子类有构造函数，基类也有默认构造，创建子类对象时，直接调用基类默认构造，或者调用子类显式调用的构造函数
    • 子类基类均有构造，但是基类没有默认构造，创建子类对象时，必须显式调用基类构造函数
• 继承下的析构函数: 定义实现对派生类新增成员的析构释放
• 虚基类构造优先于非虚基类的构造
• 虚基类构造由最派生类调用，其他派生类跳过对虚基类构造的调用
• 派生类对象和指针可适用于任何基类对象或指针使用的位置（子类可以向上转型）
• 赋值兼容：子类对象可以赋值或者初始化父类对象，基类指针可以指向子类对象地址