from xiongdilian

leetcode 022. Generate Parentheses

• Concise recursive C++ solution

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

  class Solution { public: vector<string> generateParenthesis(int n) { vector<string> res; addingpar(res, "", n, 0); return res; } private: void addingpar(vector<string> &v, string str, int n, int m){ if(n==0 && m==0) { v.push_back(str); return; } if(m > 0){ addingpar(v, str+")", n, m-1); } if(n > 0){ addingpar(v, str+"(", n-1, m+1); } } };

• The most concise solution I know ever

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

  class Solution { public: vector<string> generateParenthesis(int n) { if(n==0) return vector<string>(1,"") ; if(n==1) return vector<string>(1,"()") ; vector<string> result; for(int i=0;i!=n;i++) for(auto inner: generateParenthesis(i)) for(auto outter: generateParenthesis(n-i-1)) result.push_back("("+inner+")"+outter); return result; } };

• My 4ms C++ solution without using recursion

  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

  M Mein-Fuhrer Reputation: 3 class Solution { public: vector<string> generateParenthesis(int n) { vector<string> result; string str("("); result.push_back(str); vector<int> left({1}); for(int pos = 1;pos < 2*n;++pos) { int tmp = left.size(); for(int i = 0;i < tmp;++i) { if(left[i] < n) { if(pos - left[i] < left[i]) { result.push_back(result[i] + ')'); left.push_back(left[i]); } result[i] += '('; left[i]++; } else { result[i] += ')'; continue; } } } return result; } };

写在补课之后：

**

• 补课强度高，消化不良，但是有一点明确，让你知道要学什么
• 有一堆志同道合的人一块自习撸码还是很享受的，科大的实验课真心不错
• 碰撞，或者老司机带路跟自己干还是不一样的
• 将来找团队，找妹子也一定要志同道合啊…… :joy: :joy:

• 数据结构：树变种，复杂堆，红黑树，图剪枝回溯

  leetcode 随算法导论进行

• 网络：socket 编程，网络协议，TCP/IP三卷，

  UNP 随高网进行

• 操作系统：linux私房菜未看完，在正式开学前搞完

  APUE 随CSAPP进行

• 数据库：范式理解需要加深

  高性能mysql 随高级数据库进行

• c++：

  c++ primier ：后四章理解不够，
  effective c++ ：中关于泛型编程 理解不足，缺少使用经验
  stl 标准库 ：明显理解不够需要重新理解思考 随c++ 面向对象复习

• 当前未涉及领域

  机器学习/推荐算法，python
  python 参考手册
  提前理解孟宁老师网络程序课程涉及的机器学习框架和内容
  刷网易云课堂：保健老师编译原理计划待定

尝试图形化笔记，增加会议性笔记，以代码注释代替文字笔记
辅助技能：git不能满足于基本操作，markdown语法加入html，vim进阶，linux深入

思考：

1、看书的正确方式：从c++书籍的经验看，直接上效果低，先用遇到问题查询，缺哪块补哪块
2、笔记的正确方式：禁止抄书，以思考写笔记，注意总和测试

• 问题：

  书籍pdf 还是纸质版？
  中文书籍书籍速度快，效果差，解析未必透侧
  文外书籍，阅读慢，讲解透侧，官网教程代码简洁

• 是否涉入JAVA：

  优点：JAVA应用广，框架多，封装良好，岗位多
  困境：目前位涉猎java领域，c++（算法）/python（机器学习） 将在第一学期计划中占据很大代码量

技能树存在java 和 编译原理 缺口
分布式缺口在下学期的分布式与云计算课同步补齐

###总结：
增加代码量，代码为主，看书为辅
新知识关注官网tutorial
图形化笔记，回忆性笔记
重理解，英文化

• 管理用户：
  USE mysql；
  SELECT user FROM user；
• 创建账户：
  CTEATE USER name IDENTIFIED BY ‘PASSWAORD’；
• 删除用户 DROP USER name；
• 设置权限：
  SHOW GRANTS FOR name；
• 修改权限：
  GRANT SELECT ON …. TO username；

• sql语句创建库:
  SOURCE 绝对路径+文件名；
  SHOW columns FROM tablename；
  SHOW STATUS;
  SHOW GRANTS;
  SHOW CREATE TABLES;
  SHOW ERRORS;

• create database and use
  create database [if not exists]database_name;
  show databases;
  show tables;
  drop database [if exists]database_name;
  create table [if not exists] table_name(
  column_name data_type[size] [not null|null] [default value] [auto+increment]
  )engine=engine_name;
  alter table table_name
  change/add/drop/rename column column_name ….

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

  A temporary table is only available and accessible by the client who creates the table. SELECT column_1, column_2, ... FROM table_1 [INNER | LEFT |RIGHT] JOIN table_2 ON conditions WHERE conditions GROUP BY column_1 HAVING group_conditions ORDER BY column_1 LIMIT offset, length;

• A temporary table is only available and accessible by the client who creates the table.

  1 2 3

  CREATE [UNIQUE|FULLTEXT|SPATIAL] INDEX index_name USING [BTREE | HASH | RTREE] ON table_name (column_name [(length)] [ASC | DESC],...)

• INNER JOIN
  

• INTERSET NO DUPLICATE
  The left query produces a result set of (1,2,3)
  The right query returns a result set of (2,3,4)
  The INTERSECT operator returns the distinct rows of both result sets which are (2,3).
  

• Index

  1 2 3 4 5 6 7 8 9 10

  NUMERIC TYPES DESCRIPTION TINYINT A very small integer SMALLINT A small integer MEDIUMINT A medium-sized integer INT A standard integer BIGINT A large integer DECIMAL A fixed-point number FLOAT A single-precision floating point number DOUBLE A double-precision floating point number BIT A bit field

• DATE functions

  1 2 3 4 5 6

  NOW(); DATE(NOW());//format DATE_FORMAT(CURDATE(), '%m/%d/%Y');//foramt_function CURRENT_TIME()//HHMMSS ADDTIME(CURRENT_TIME(), 023000), SUBTIME(CURRENT_TIME(), 023000);

• TRANSICTION

  1 2 3

  START TRANSACTION .... COMIT

  if all the action in the tansaction sucessed it will commit,if not it will rollback to start

• TABLE LOCK
  LOCK TABLE tablename [READ|WRITE];

  read:
  other session can read without lock but this session cao only read but not write;
  write:
  only this session can read and write
  other session cannot read and write untill the lock is released.

UNLOCK TABLES;

1
2
3
4
5
6
7
8
9
10
11

``when a table locks other  session cann`t use it untill it unlocked``
* * A REFERENCRS B  ON []
  when B [] act which will act to A the same
* SELECT column FROM tablename LIMIT num1，num2；
输出从num1行开始的num2行
> **BETWEEN AND 两值之间
[NOT] IN(范围) 制定范围之间
LIKE 字符匹配**
* MYSQL REGEXP

| 或
[ a-z ] 范围所有小写字母
. 任意字符
\ 转义
[: :] 匹配字符类

1

* 重复前字符

* 0或多个匹配
+ 1或多个匹配
？ 0或1个匹配
{n} 指定数目匹配
{n，} 不少于制定数目匹配
{n,m} 匹配数目不超过m

1

* 定位符

^ 文本开始
$ 文本结尾
[[:<:]] 词开始
[[:>:]] 词结束

1
2
3

**LIKE 匹配整串 REGEXP 匹配子串**
mysq以concat()实现拼接，一般sql可以用+或者||实现
* 文本函数

rtrim() 去掉数值右侧空格
Left() 返回串左边字符
Length() 返回串长度
Locate() 找出串中一个子串
Lower() 转换为小写
Ltrim() 去除左边空字符
Rtrim() 去除右边空字符
Right() 返回串右边字符
Soundex() 发音相似
Substring() 返回子串
Upper() 转换为大写

1
2

1. DISTINCT 只能用于COUNT(),不能用于COUNT(*)
2. GROUP BY 子句嵌套分组时，数据将在最后规定的分组进行汇总
3. HAVING 过滤分组子句
4. WHERE 在数据分组前进行过滤，HAVING 在数据分组后过滤

   1 2 3 4

   等值连接即内连接INNER JOIN ON 子句筛选 自链接，使用表别名防止链接错误 * 全文匹配

FULLTEXT（tablename）:为该列建立索引
MATCH（指定搜索列）AGAINST（搜索文本）[WITH QUERY EXPANSION]/查询扩展
FULLTEX与MATCH参数必须一致
全文匹配自动排序，相似度高的先输出
扩展查询：两次索引查询，第一次查询相似词，第二次用相似词查询并返回结果

1

* IN BINARY MODE

+ 包含，词必须存在
— 排除，词不出现
> 包含，增加等级
< 包含，减少等级
() 词组排列组合
~ 取消一个词的排序值
* 词尾通配符
“” 定义为一个短语

1

* 引擎类型

ENGINE=[]
InnoDB 事务处理，不支持全文搜索
MEMORY 快速MyISAM，内存存储，速度快
MyISAM 支持全文搜索不支持事务处理

1
2
3
4

0. **外键不能跨引擎**
1. **在视图定义中有如下操作不能更新:分组、链接、子查询、并、、聚集函数，distinct**
* 创建存储过程：

CREATE PROCEDURE procedurename(参数)
BEGIN
………;
END;

1
2

* 调用存储过程：CALL preocedurename（@p1，@p2，@p3）；
*参数变量以@开头*

* 备份前FLUSH TABLES; 刷新
* 备份：mysqldump 转储所有内文件到外部文件
* mysqlhotcopy 复制数据库
* BACKUP TABLE /SELECT INTOOUTFILE 转储到外部文件

1

*

SHOW CHARACTER SET； 显示字符集
SHOW COLLATION； 显示校对
ANALYZE TABLE tablename； 分析表状态
CHECK TABLE tabkename； 检查表状态
```

sqlite

格式化输出

.heade on
.mode column

LIKE

% 任意多个字符 LIKE ‘XX*’;
_ 唯一一个字符 LIKE ‘_X’;

GLOB

* 任意字符
? 单一数字或者字符

LIMIT

LIMIT n
从开始到n项
LIMIT n OFFSET m;
以 n项为中心,m正向下m项,m负向上m项

SELECT [] FROM [table.name] ORDER BY [column] ASC|DESC;
SELECT 语句中，GROUP BY 子句放在 WHERE 子句之后，放在 ORDER BY 子句之前
聚集函数

COUNT(DISTINCT|ALL<列名>);
SUM(DISTINCT|ALL<列名>);
AVG(DISTINCT|ALL<列名>);
MAX/MIN(DISTINCT|ALL<列名>);

HAVING [condition]
HAVING 子句必须放在 GROUP BY 子句之后，必须放在 ORDER BY 子句之前
DISTINCT

SELECT DISTINCT [] FROM
与 SELECT 语句一起使用，来消除所有重复的记录

链接实现:
1、nested-loop
2、排序合并：子表排序后顺序查找

sqlite约束:

NOT NULL
DEDFAULT:创建表格时设置默认值
UNIQUE
PRIMMARY KET
CHECK:输入值时check,false则输入无效
example:SALARY REAL CHECK(SALARY> 0);

重命名列,删除列,删除约束在sqlite不可实现

sqlite joins

CROSS JOIN

• SELECT COLUMN1,…COLUMN2 FROM TABLE1 CROSS JOIN TABLE2
  INNER JOIN
• SELECT COLUMN,…COLUMNn FROM TABLE1 JOIN TABLE2 USING COLUMN1…COLUMNn;
• SELECT COLUMN,…COLUMNn FROM TABLE1 INNER JOIN TABLE2 ON condition;
• SELECT COLUMN,…COLUMNn FROM TABLE1 NATURE JOIN TABLE2 COLUMN1 … COLUMNn;
• OUTER JOIN:LEFT OUTER JOIN\ RIGTH OUTER JOIN\ FULL OUTER JOIN
• SELECT…..FROM table1 [ ] OUTER JOIN table2 ON condition/ USING column….

UNION

每个 SELECT 被选择的列数必须是相同的，相同数目的列表达式，相同的数据类型，并确保它们有相同的顺序，但它们不必具有相同的长度。

1 2 3 4

SELECT .... FROM TABLE1....WHERE ..... UNION SELECT .... FROM TABLE2....WHERE ..... //UNION 去重，UNION ALL 不去重

Alias

1
2
3
4
5
6
7
8

table：
SELECT  aliase_name.column... 
FROM  table.name AS aliase_name
WHERE [condition];
column:
SELECT column_name AS alias_name
FROM table_name;
WHERE [condition]；

TRIIGGER

1
2
3
4

CREATE TRIGGER tiggername [AFTER/BEFORE] [action] ON tablename
BEGIN
.....
END;

• 显示触发器：
  SELECT name FROM SQLITE——master
  WHERE type=’trigger’;
• 删除触发器：
  DROP TRIGGER triggername；
• INDEX:
  CREAT [UNIQUE] INDEX indwx_name ON table_name(column1,column);
• 显示单表中index：
  .indices table
• 显示全部：
  SELECT * FROM sqlite_master WHERE type = ‘index’;
• DROP INDEX index_name;
  索引不应该使用在较小的表上。
  索引不应该使用在有频繁的大批量的更新或插入操作的表上。
  索引不应该使用在含有大量的 NULL 值的列上。
  索引不应该使用在频繁操作的列上。

• ALERT
  ALTER TABLE tablename RENAME TO new_tablename
  ALERT TABLE databasename.tablename ADD COLUMN columnname def…..

• VIEW
  CREATE [TEMPORY|TEMP]VIEW viewname AS
  SELECT column1 column2….
  FROM tablename
  WHERE [condition];
  SELECT * FROM viewname;
  DROP VIEW viewname;

• TRANSICTION

  原子性（Atomicity）：确保工作单位内的所有操作都成功完成，否则，事务会在出现故障时终止，之前的操作也会回滚到以前的状态。
  一致性（Consistency)：确保数据库在成功提交的事务上正确地改变状态。
  隔离性（Isolation）：使事务操作相互独立和透明。
  持久性（Durability）：确保已提交事务的结果或效果在系统发生故障的情况下仍然存在。

BEGIN;/BEGIN TRANSACTION; ROLLBACK/COMMIT;

• VACUUM
  VACUUM 命令通过复制主数据库中的内容到一个临时数据库文件，然后清空主数据库，并从副本中重新载入原始的数据库文件。这消除了空闲页，把表中的数据排列为连续的，另外会清理数据库文件结构
  VACUUM 命令只适用于主数据库，附加的数据库文件是不可能使用 VACUUM 命令。

  1 2 3

  sqlite> PRAGMA auto_vacuum = NONE; -- 0 means disable auto vacuum sqlite> PRAGMA auto_vacuum = INCREMENTAL; -- 1 means enable incremental vacuum sqlite> PRAGMA auto_vacuum = FULL; -- 2 means enable full auto vacuum

• ELF文件格式与windows PE/COFF章节未做细致分析

review

操作系统：硬件资源管理，抽象接口
同一个系统：页大小固定
fork并不复制原任务内存空间，而是和原任务共享一个写时复制的内存空间
写时复制：两个任务可同事自由读取内存，任意任务视图修改时，复制一份原内存内容给修改方，以免影响其他任务。
i++；汇编变为三个指令，非原子操作，会被多线程打断。
读写锁：自由态 共享/独占均可，共享态 共享成功/独占失败 ，独占态 共享失败/独占成功
volatile：直接存取原始内存地址
（两者均可能造成线程执行顺序错误）
1、阻止编译器为了提高速度将一个变量缓存到寄存器而不写回；
2、阻止编译器调整操作volatile变量的顺序
barrier指令：阻止编译器将barrier之前的指令换到barrier之后

compile and link

预编译 gcc -E
以“#”开头语句被处理，宏展开，注释清楚，
保留#prama给编译器，插入行号和文件名表示用于编译错误提醒
编译 gcc -S
生成汇编代码
gcc 根据不同参数，调用预编译程序，汇编器，链接器
汇编
as/gcc -c
链接：地址空间分配，符号决议（绑定），重定位
编译时不能确定地址，链接时确定和修改地址：重定位

object file

目标文件、动态链接库、静态链接库、可执行文件均按照可执行文件格式存储，linux中为ELF
ELF文件分类
1、可重定位文件relocatable file linux.o
2、可执行文件 executable file windows.exe
3、共享目标文件shared object file linux.so windows.dll
4、核心转储文件 coredump file linux.core dump(意外终止进程文件内容与信息)
c语言编译后文件：
.text 执行语句
.data 以初始化的全局变量和局部静态变量
.bss 未初始化的全局变量和局部静态变量

objdump -x -s -d name.o
文件name.o内容显示格式：
.字段名 十六进制存储标识 汇编语言

自定义段存储位置
attribute((section(“name”))) int var=value;
将var放置在name段中
readlf -h name.o显示ELF文件

static link

链接器为目标文件分配地址和空间：
1、分配输出文件空间
2、完整装载厚厚的地址定位，即形成程序虚拟地址
two-passing link
1、空间域地址分配：文件、符号合并，建立映射关系
2、符号解析与重定位：调整代码中地址为虚拟地址
可重定位文件中，每一个可重定位ELF段赌赢一个重定位表
objdump -r name.o 查看name.o的重定位表
重定位过程中：每个重定位入口都是对一个符号的引用
readelf -s name.o 查看name.o的符号表
重定位方式：
R_386_32 1 绝对寻址修正S+A
R_386_PC32 2 相对寻址修正S+A-P
A=保存在被修正位置的值
P=被修正的位置（相对于断开始的偏移量或者虚拟地址）
S=符号实际地址r_info（重定位表）确定的符号的实际地址

弱符号的COMMON块机制
原因：编译器允许不同类型的弱符号存在，本质时链接器部支持符号类型，即无法判断符号类型是否一致
弱符号：未初始化的全局变量定义
两个弱符号以大的为准
一强一弱以强为准，若果若大小大于强，报错
gcc -fno-common/int global atttribute((nocommon))
定义未初始化全局变量nocommon不以COMMON块形式处理
一个为初始化的全局变量不以COMMON块形式存在，就相当于一个强符号，如果其他目标文件还存在同一个变量的强符号定义，连接时发生符号重定义
c++中编译问题
1、重复代码
模板在不同文件被相同类型实例化造成代码重复
解决方案：将每个模板的市里代码单独放置在一个段里，每个段只把含有一个模板实例
有虚函数的类有一个虚函数表，在不同编译单元生虚函数表造成代码重复，外部内联函数、默认构造函数、默认拷贝函数、赋值操作和虚函数表做法类似
函数级别链接：每个函数单独成段，单独链接一个函数段，链接时必须明确函数依赖关系
全局构造与析构
c++的全局构造函数在mian函数之前执行，析构函数在main之后执行
linux中程序入口为_start,这个函数就是程序初始化入口，初始化完成后调用main函数主体，main完整后返回到初始化部分，清理现场，结束进程
ABI：可执行二进制兼容性相关内容（符号修饰标准，变量内存布局，函数调用方式等）二进制层面接口
静态库：一组目标文件object的集合

execute file loading and process

装载：程序局部性，覆盖装入overlay、页映射paging
进程的建立
1、创建独立虚拟地址空间\
2、读取可执行文件头，建立虚拟空间与可执行文件的映射关系
& 虚拟空间发生页错误时定位可执行文件位置
3、CPU指令寄存器设置成可执行文件入口地址
&涉及用户态与内核态转换
进程虚拟地址空间VMA：
代码VMA：只读，可执行
数据VMA：可读可写可执行
堆VMA： 可读写可执行
栈VMA： 可读写不可执行

dynamic link

gcc -fPIC -shared -o lib.s0 lib.c 生成动态库
静态共享库 ：操作系统划分固定空间存储静态库模块
动态共享库：共享对象编译时不明却自己的进程虚拟地址空间中的位置
PIC地址无关代码：
模块内部调用与跳转：相对寻址
模块内数据访问：相对寻址
模块间数据访问：全局偏移表，标记偏移位置
模块见调用域跳转：全局偏移表保存目标函数位置
延迟绑定：函数第一次调用时绑定
/lib 关键基础共享库
/usr/lib 开发共享库
/usr/local/lib 三方应用库

memory

内核空间，栈向下延伸，动态链接库在堆栈中间，堆向上延伸，读写部分（.data .bss）,只读部分(.init .text .rodata)装载起始位置0x08048000,之下为reserved
segment fault:指针非法,读写不可读写空间,指针未初始化或者初始化为NULL就使用指针
堆栈帧:储存函数返回地址与参数,临时变量,函数调用前后不便的寄存器(上下文)
esp指向栈顶,ebp指向活动栈帧,又称为帧指针
ebp函数返回位置
调用惯例calling conversion
函数参数传递顺序域方式:压栈传递参数.函数调用方压栈,函数本身弹栈取值
c语言调用惯例:从右至左压栈参数
返回值传递:使用临时栈上存储区作为中转,两次copy,一次存入栈上tmp,一次存回返回区

堆空间由运行库管理
mmap申请匿名空间实现malloc
堆分配算法:空闲链表\位图\对象池

MINI CRT的实现

Specification

• Template and generic programing not marked(40-47)
• Design and implememt need more code experience to understand
• Effective c++ need read more than one times
• Learning by code

Item1 default constructor:

called with no arguments
has no parameter or default value for every parameter.
default constructer should be ‘explicit’ to avoid ‘implicit type conversion’
‘copy instructor’:initialize an object with a different objrect of the same type.
‘copy assignment operator’: copy the value from one object to another of the same type.
‘object passed by value’ in the way of ‘copy construtor’

Rules for effective c++ programming vary,depending on the part of c++ you are using :C OOP Template STL

Item2 Prefer const ,enum,and inline to #define

const not many copy like #define and can be private.
enum can be referenced but #define cann`t
For simple constants ,prefer const objects to #define
For function-like macros, prefer inline function to #define.

Item3 Use const whenever possible

whenever it`s true ,to do so -const.
for pointer ,you can specify whether the pointer itself is const ,the data it point to is const,both or neither.

1 2 3 4 5 6 7 8

char *p = greeting;// non-const pointer, // non-const data const char *p = greeting;// non-const pointer, // const data char * const p = greeting;// const pointer, // non-const data const char * const p = greeting;// const pointer, // const data

for iterator , const iterator is the iterator itself is const , but const_iterator , the object it point to ia const
const member function make it possible to work with const object.
return in c++ is return a copy of the parameter not itself,which invoked a copy constructor

Declaring something const helps complier detect usage errors and can be applied to objects at any scope. $ compiler enforce bitwise constness but you should program using logical constness. $ when const and non-const member function have essentialy identical implementions, code duplication can be avoided by having the non-const version call the const version.

Item4 Make sure object initialized before used

make sure that all construtors initialize everything in ht eobject.
data members that are const or are reference must be initialzied and can not be assignment.

construtor Destructor and assignmentOperation

Item5: know what function c++ silently writes and calls

Item6: Explicitly disallow the use of compiler-generated functions you do not want.

make the function you don`t want be private in the base class.
To disallow functionality provided by cpmlilers, declare the corresponding member function ‘private’ and give no imlementations.

Item7: Declare destructors virtual in plomorphic base classes.

Give the base class a virtual destructor then deleting a derived class object will do exactly what you want.
a class not intended to be a base class should not have a virtual funtion.

Item8: Prevent exception from leaving destructors

1. Destructors should never emit exceptions. if functions called in a destructor may throw,the destructor should catch ant exceptions, then swallow them ot terminate the program.
2. if a class clients need to be able to react to exceptions thrown during an operation, the class should provide a regular function that performs the operation.

Item9 :Never call virtual function during constructor or destructor

Item10: Have assignment operators return a reference to *this

‘x=y=z=15, thus x=15,y=15,z=15’
the way is implemented is that assignment returns a reference to its left-hand arguement.

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

class Widget {
public:
...
Widget& operator+=(const Widget& rhs)
{
    ...
    return *this;
}
Widget& operator=(int rhs)
{
    ...
    return *this;
}
	...
};

Item11: Handle assignment to self in operator=

1
2
3
4
5
6
7
8

Widget& Widget::operator=(const Widget& rhs)
{
    if (this == &rhs) return *this;
        // identity test: if a self-assignment,do nothing
    delete pb;
    pb = new Bitmap(*rhs.pb);
    return *this;
}

if the ‘new’ failed, pb will pointer to an undefined address.

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

Widget& Widget::operator=(const Widget& rhs)
{
    Bitmap *pOrig = pb;          // remember original pb
    pb = new Bitmap(*rhs.pb); // point pb to a copy of  rhs’s bitmap
    delete pOrig;               // delete the original pb
    return *this;
    //$$$ be careful not to delete pa untill after we`re copied what it point to.
}
Widget& Widget::operator=(const Widget& rhs)
{
    Widget temp(rhs);// make a copy of rhs’s data
    swap(temp);      // swap *this’s data with the copy’s
    return *this;
}
Widget& Widget::operator=(Widget rhs)   // rhs is a copy of the object passed in — note pass by val
{
    swap(rhs);              // swap *this’s data with
    return *this;
}
``` 
**Make sure any funtion operating on more than one object behave corectly if two or more of the objects are the same.**
#### Item12: COpy all parts of an object
> for derived class, the copy function should not only copy the data member it defined for itself, but also the data member it inherient from the base class,which will be initialized by the constructor that takes no arguements of the base class.
 Copy all aparts:
 $ copy all local data members
 $ invoke the appropriate copying funtion in the base class.
 **Don`t try to implement one of the copy constructor funtions in terms of the other 'put common funtionality in a third funtion that both call'**
 
### Reource Management
#### Item 13:Use objects to manage resources
$ put resource inside an object whose destructor will automatically release the resource when control leaves.
> **Uing Object to Manage Resources**
 $ resource are acquired and immediately turned over to resource-manageging abjects.
 $ Resource-managing objects use their destructors to ensure that resource are released.
 'auto_ptr automaticallt dlete what it point to when the  auto_ptr is destroyed, it`s impotantly that there never be more than one auto_ptr pointing to an object'
auto_ptr have anusual characteristic: copy it (via copy constructor or copy assignment operator)and set it null.
 'auto_ptr<type>p2=p1  //p1 pointe to null and p2 pointto the object p1 point to'
 a reference -counting smart pointer: keep track of how many objects point to aaprticular resource and automaticallt delete the resource when nobady is pointing to it ang longer.
 **Both auto_ptr and tr1::shared_ptr use delete in their destructors, not delete []. That means that using auto_ptr or tr1::shared_ptr with dynamically allocated arrays is a bad idea**
 
#### Item14: Think carefully about copying behavior in resource-managing classes
> $ Peohabit copying: 
  declare the copt operations private
 $ Referene-count the underlying resource:
  use the tr1::shared_ptr. define your deleter function 
 $ Copy the underlying resource:
  make sure all the copy released when nessary
 $ Transfer ownership of the underlying resource
  using auto_ptr 
  
#### Item15 Provide access to raw resource in resource-managing classes $$$$
> shared_ptr and auto_ptr both offer a get member function to perform an explicit    conversion :return (a copy of)the raw pointer inside the smart pointer object '.get()'
 $ APIs often require access to raw resources ,so each RAII class should offer a way to get at  rhe resource it manages.
#### Item16 Use the same form in corresponding *uses* of new and *delete* 
> if you use [] in a new expression, you must use [] in the corresponding delete expression
#### Item17 Store newed objects in smart pointers standalone statements.
> 'processWidget(std::tr1::shared_ptr<Widget>(new Widget), priority());' **not good**
 'std::tr1::shared_ptr<Widget> pw(new Widget);
  processWidget(pw, priority());' // **well**
**Store new ed objects in smart pointers in standalone statements. Failure to do this can lead to subtle resource leaks when exceptions are thrown.**
### Designs ad Declarations
#### Item18 Make interface easy to use correctly and hard to use incorrectly.
> for your class and struct operation, when in doubts, do as the ints do.
  tr1::shared_ptr supports custom deleters. This prevents the cross-DLL problem, can be used to automatically unlock mutexes (see Item 14), etc.
#### Treat class design as type design
>  ■ How should objects of your new type be created and destroyed? 
How this is done influences the design of your class’s
constructors and destructor, as well as its memory allocation and deallocation functions ( operator new , operator new[] , operator delete ,and operator delete[] — see Chapter 8), if you write them.
> ■ How should object initialization differ from object assignment? 
The answer to this question determines the behavior of and the differences between your constructors and your assignment operators. It’s important not to confuse initialization with assignment, because they correspond to different function calls (see Item 4).
> ■ What does it mean for objects of your new type to be passedby value?
 Remember, the copy constructor defines how pass-by-value is implemented for a type.
> ■ What are the restrictions on legal values for your new type?
Usually, only some combinations of values for a class’s data members are valid. Those combinations determine the invariants your class will have to maintain. The invariants determine the errorchecking you’ll have to do inside your member functions, espe-
cially your constructors, assignment operators, and “setter” functions. It may also affect the exceptions your functions throw and,on the off chance you use them, your functions’ exception specifications.
> ■ Does your new type fit into an inheritance graph? 
If you inherit from existing classes, you are constrained by the design of those classes, particularly by whether their functions are virtual or nonvirtual (see Items 34 and 36). If you wish to allow other classes to inherit from your class, that affects whether the functions you declare are virtual, especially your destructor (see Item 7).
>  ■ What kind of type conversions are allowed for your new type?
Your type exists in a sea of other types, so should there be conversions between your type and other types? If you wish to allow objects of type T1 to be implicitly converted into objects of type T2 ,you will want to write either a type conversion function in class T1(e.g., operator T2 ) or a non- explicit constructor in class T2 that can be called with a single argument. If you wish to allow explicit conversions only, you’ll want to write functions to perform the conversions, but you’ll need to avoid making them type conversion operators or non- explicit constructors that can be called with one argument. (For an example of both implicit and explicit conversion functions, see Item 15.)
>  ■ What operators and functions make sense for the new type?
The answer to this question determines which functions you’ll declare for your class. Some functions will be member functions, but
some will not (see Items 23, 24, and 46).
>  ■ What standard functions should be disallowed? 
Those are the ones you’ll need to declare private (see Item 6).
>  ■ Who should have access to the members of your new type?
This question helps you determine which members are public, which are protected, and which are private. It also helps you de-
termine which classes and/or functions should be friends, as well as whether it makes sense to nest one class inside another.
>  ■ What is the “undeclared interface” of your new type? 
What kind of guarantees does it offer with respect to performance, exception safety (see Item 29), and resource usage (e.g., locks and
dynamic memory)? The guarantees you offer in these areas will impose constraints on your class implementation.
>  ■ How general is your new type? 
Perhaps you’re not really defining a new type. Perhaps you’re defining a whole family of types. If so,
you don’t want to define a new class, you want to define a new class template.
>  ■Is a new type really what you need? If you’re defining a new de-rived class only so you can add functionality to an existing class,perhaps you’d better achieve your goals by simply defining one or more non-member functions or templates.
#### Item20 Prefer pass-by-reference-to-const to pass-by-value
> ✦ Prefer pass-by-reference-to- const over pass-by-value. It’s typically more efficient and it avoids the slicing problem.
 ✦ The rule doesn’t apply to built-in types and STL iterator and function object types. For them, pass-by-value is usually appropriate.
#### Item21 Don't try to return a refernece when you must return an object.$$
> 
any function returning a reference to a local object is broken as well as a pointer to local object.
???
#### Item22 Declare dta members private.
> Declare data members private . It gives clients syntactically uniform access to data, affords fine-grained access control, allows invariants to be enforced, and offers class authors implementation flexibility
#### Item23 Prefer none-member non-friend functions to member functions.
#### Item24 Declare non-member function when type conversion should apply to all parameters.
> make operator* a non-member function, thus allowing compilers to perform implicit type conversions on all arguments
Whenever you canmavoid friend functions, you should, because, much as in real life,friends are often more trouble than they’re worth
$ If you need type conversions on all parameters to a function (including the one that would otherwise be pointed to by the this pointer),the function must be a non-member
#### Item25 Consider suport for a non-throwing swap $$$
* Swap in STL

namespace std
{
template
void swap(T& a, T& b)
{
T temp(a);
a = b;
b = temp;
}
}

• swap in pointer the type must support copy constructor and copy assignment

  1	Not swap the object itself which is so ineffcient,but swap the pointer.

template<>
void swap(Widget& a,Widget& b)
{
swap(a.pImpl, b.pImpl);
}

• When you want to “partially specialize” a function template, the usual approach is to simply add an overload

Implementions

Item26: Positive varible definitions as long as possible

for variable to use in a loop ,define it out of the loop may be more effecient

Item27 Minimize casting

c++ style casting

const_cast( expression ): cast const object to non-object
dynamic_cast( expression ): safe downcasting
reinterpret_cast( expression )
static_cast( expression ): implicit concersion
✦ Avoid casts whenever practical, especially dynamic_cast s in performance-sensitive code. If a design requires casting, try to develop a cast-free alternative.
✦ When casting is necessary, try to hide it inside a function. Clients can then call the function instead of putting casts in their own code.
✦ Prefer C++-style casts to old-style casts. They are easier to see, and they are more specific about what they do.

Item28 Avoid returning “handles” to object internals

Item29 Strive for exception-safe code $$

Exception-safe functions leak no resources and allow no data structures to become corrupted, even when exceptions are thrown. Such functions offer the basic, strong, or nothrow guarantees.
✦ The strong guarantee can often be implemented via copy-and- swap ,but the strong guarantee is not practical for all functions.
✦ A function can usually offer a guarantee no stronger than the weakest guarantee of the functions it calls.

Item30 Understand the ins and outs of inlineing $$

inline in most c++ programs ia a compile-time activity.
inline functions typically be in header files
limit most inlineing to small as possible
Dont`t declare function template inlne just because they appear in header files

Item31 MInimize complication dependence between files

1. Avoid using objects when object reference and pointer will do
2. Depend on class declaraton instead of class definitions whenever you can
3. Provide aeperate header files for declarations and definition

Inheritence and object-oriented design

Item32 Make sure public ingeritence model “is a”

Everythings that applies to base class must also apply to the derived class ,because every derived class object is a base class object.

Item 33 Avoid hiding inheriented names.

the scope of a derived class is nested inside its base class`s scope.
the same name member funtion in derived class will hide the member funtion with the same name inthe base class ,even if the parameter is different, regaedless of whether the funtions are virtual or non-virtual.

• if you use pubic inheritence ,you can`t inherit the overloads.
  pubic derived allow to override c+ + `s default hiding of inherited names
  *using base:: functionname;
  make all things in base named functionname visible in derived class, andd the c++ scope search will find the most appropriate member funtion between tha base class function and derived class member function with the same name

Things to Remember

• Names in derived classes hide names in base classes. Under public inheritance, this is never desirable.
• To make hidden names visible again, employ using declarations or forwarding functions.**

item34 Differentiate betwwen inhertance of interface and inheritance of impletention

1. derived class inherit only the interface(declaration):interface only
2. derived class inherit both the inteface and the implement, but may be overrided the implemention:interface and a default implementation
3. derived class inherit both the inteface and the implement, but without override anything:inteface and a mandatory implementation

• pure virtual function
  $ must be redeclared in any derived class
  $ derived class inherit a function interface only.
• simple virtual function
  $ derived class inherit the interface
  $ the implementation derived can be overrided
  $ if it`s not overrided , call the default implementation in the base class
• non-virtual function
  $ inteface and a mandatory implementation
  Member function interface are always inherited

Item35 Consider alternatives to virtual functions.

1. Design Pattern : Template Method call private virtual function through public non-virtual member functions ‘??’

2. The Strategy Pattern via Function Pointers

3. The Strategy Pattern via tr1::function

4. The “Classic” Strategy Pattern

• Use the non-virtual interface idiom (NVI idiom), a form of the Template Method design pattern that wraps public non-virtual member functions around less accessible virtual functions.
• Replace virtual functions with function pointer data members, a stripped-down manifestation of the Strategy design pattern.
• Replace virtual functions with tr1::function data members, thus allowing use of any callable entity with a signature compatible with what you need. This, too, is a form of the Strategy design pattern.
• Replace virtual functions in one hierarchy with virtual functions in another hierarchy. This is the conventional implementation of the Strategy design pattern.

Item36 Never redifine an inherited non_virtual function

non-virtual function is statically bound, but virtual funtion are dynamically bound
refifine a non-virtual function will make the compiler exhaust.

Item37 Never redefine a function’s inherited default parameter value

virtual function are dynamically bound, but default parameter values are statically bound
all the derived function will inherit the defualt parameter.

Item38 Model “has a” or “is-implemented -in-terms-of”through composition $

• Composition has meanings completely different from that of public inheritance.
• In the application domain, composition means has-a. In the implementation domain, it means is-implemented-in-terms-of.

Item 39 Uasage private inheritance judiciously $$

1. can not convert a derived class object into abase class object if the inheritence relationship id private
2. members inheriente from the base class will be private member of the derived class.
3. private inheritance means only software implementation

• Private inheritance means is-implemented-in-terms of. It’s usually inferior to composition, but it makes sense when a derived class needs access to protected base class members or needs to redefine inherited virtual functions.
• Unlike composition, private inheritance can enable the empty base optimization. This can be important for library developers who strive to minimize object sizes.

####Item 40 Uasage multiple inheritance judiciously $$

• Multiple inheritance is more complex than single inheritance. It can lead to new ambiguity issues and to the need for virtual inheritance.
• Virtual inheritance imposes costs in size, speed, and complexity of initialization and assignment. It’s most practical when virtual base classes have no data.
• Multiple inheritance does have legitimate uses. One scenario involves combining public inheritance from an Interface class with private inheritance from a class that helps with implementation.

Templates and Generic Programming $$

Item41 Understand implicit interfaces and compile-time polymorphism.

• Both classes and templates support interfaces and polymorphism.
• For classes, interfaces are explicit and centered on function signatures. Polymorphism occurs at runtime through virtual functions.
• For template parameters, interfaces are implicit and based on valid expressions. Polymorphism occurs during compilation through template instantiation and function overloading resolution.

Item 42: Understand the two meanings of typename.

The general rule is simple: anytime you refer to a nested dependent type name in a template, you must immediately precede it by the word typename .

• When declaring template parameters, class and typename are interchangeable.
• Use typename to identify nested dependent type names, except in base class lists or as a base class identifier in a member initialization list.

Item43: Know how to access names in templatized base classes.

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

#include <iostream>
#include<ctime>
#include<cstdlib>
using namespace std;
#define maxn 100
int main()
{
   int i,j;
   srand((unsigned)time(NULL));
   for(i=0;i<10;i++)
   {
       j=rand();
       cout<<"随机数：  "<< j%maxn << endl;
   }
   return 0;
}

保护成员在派生类（即子类）中是可访问的
friend funtion is not belong to any class,and may access any nember of the class which it make firends.
inline function: all the funtion defined in the class is default inline function .
the compiler cooperate the inline function like #define
this pointer is the implicitly arguement of all the menber function.
in any menber funtion ,you can use the this pointer to call the object itself.
pointer to class is like the pointer to struct ,which can access the member object.

1
2
3

Box *ptrBox;                // Declare pointer to a class.
   ptrBox = & Box1;// use menber access oprator to call the
   cout << "Volume of Box1: " << ptrBox->Volume() << endl;

static menber and static mener function has the only copy int the class,
any object of this class not have a copy.but it`s accessible to any object of this class.

inheritance:
class classname: access-specifier base-class
derived-class (public,private,protected) defined class

Access public protected private
identical-class yes yes yes
inherient-class yes yes no
outer-class yes no no

A derived class inherits all base class methods with the following exceptions:

1. Constructors, destructors and copy constructors of the base class.
2. Overloaded operators of the base class.
3. The friend functions of the base class.

``
Type of Inheritance:
When deriving a class from a base class, the base class may be inherited through public, protected or private inheritance. The type of inheritance is specified by the access-specifier as explained above.

We hardly use protected or private inheritance, but public inheritance is commonly used. While using different type of inheritance, following rules are applied:

1
2
3
4

* Public Inheritance: When deriving a class from a public base class, public members of the base class become public members of the derived class and protected members of the base class become protected members of the derived class. A base class's private members are never accessible directly from a derived class, but can be accessed through calls to the public and protected members of the base class.
* Protected Inheritance: When deriving from a protected base class, public and protected members of the base class become protected members of the derived class.
* Private Inheritance: When deriving from a private base class, public and protected members of the base class become private members of the derived class.

``
Multiple Inheritances:

class derived-class: access baseA, access baseB….

Overloading function and Overloading operator
int the same scope,you can declare some function with the same name,but the parameter list must be different. when the function called ,the compiler will select the most approriate overloaded funtion or operator, which is called overloaded resolution.
overloaded funtion character:

The definition of the function must differ from each other by the types and/or the number of arguments in the argument list.
the list of operators, which can not be overloaded: :: .* . ?;

1 2 3 4 5 6 7 8 9 10 11

friend ostream &operator<<( ostream &output, const Distance &D ) { output << "F : " << D.feet << " I : " << D.inches; return output; } friend istream &operator>>( istream &input, Distance &D ) { input >> D.feet >> D.inches; return input; }

Polymorphism

polymorphism occurs when there is hierarchy of class and they are related by inheritance.
polymorphism in c++ means that a call to a member function will cause a different function to be executed depending on the type of object that invokes the function.

the call of the member function is being set once by the compiler as the version defined in the base class,which is called static resolution of the function call, or static linkage and also sometimes called early binding
Virtual funtion precede the declaration of menber funtion() in the base class with the keyword virtual.
virtualed in the base class and each of the child classes has a separate implementation for the function(). This is how polymorphism is generally used.
A virtual function is a function in a base class that is declared using the keyword virtual. Defining in a base class a virtual function, with another version in a derived class, signals to the compiler that we don't want static linkage for this function. What we do want is the selection of the function to be called at any given point in the program to be based on the kind of object for which it is called. This sort of operation is referred to as **dynamic linkage**, or **late binding**.

Pure Virtual Functions:

there is no meaningful definition you could give for the function in the base class.
virtual type functionname() = 0;
The = 0 tells the compiler that the function has no body and above virtual function will be called pure virtual function.

c++ inteface are implemented by Abstract class
A class is made abstract by declaring at least one of its functions as pure virtual function. using virtual and placing “=0 “ in its declaration.
The purpose of an abstract class (often referred to as an ABC) is to provide an appropriate base class from which other classes can inherit. Abstract classes cannot be used to instantiate objects and serves only as an interface.
if a subclass of an ABC needs to be instantiated, it has to implement each of the virtual functions, which means that it supports the interface declared by the ABC
Classes that can be used to instantiate objects are called concrete classes
.

Memory in c++ program ia divided into two parts:

1
2
3
4
5

The stack: All variables declared inside the function will take up memory from the stack.
The heap: This is unused memory of the program and can be used to allocate the memory dynamically when program runs
'''
> it is good practice to check if new operator is returning NULL pointer and take appropriate action as below:

double* pvalue = NULL;
if( !(pvalue = new double ))
{
cout << “Error: out of memory.” <

1
2

---
Following is the syntax of new operator for a multi-dimensional array as follows:

int ROW = 2;
int COL = 3;
double *pvalue = new double [ROW]; // Allocate memory for rows

// Now allocate memory for columns
for(int i = 0; i < COL; i++) {
pvalue[i] = new double[COL];
}

1

The syntax to release the memory for multi-dimensional will be as follows:

for(int i = 0; i < COL; i++) {
delete[] pvalue[i];
}
delete [] pvalue;

1

**Function Template**

template ret-type func-name(parameter list)
{
// body of function
}
```
CGI

规范
思考 thinkong
改进 improvement
说明 specification

When an overloaded operator is a member function, this is bound to the left-hand operand. Member operator functions have one less (explicit)parameter than the number of operands.When an overloaded operator is a member function, this is bound to the left-hand operand. Member operator functions have one less (explicit) parameter than the number of operands.

deciding whether to make an operator a member or an ordinary nonmember function:
• The assignment (=), subscript ([]), call (()), and member access arrow (->)
operators must be defined as members.
• The compound-assignment operators ordinarily ought to be members. However,
unlike assignment, they are not required to be members.
• Operators that change the state of their object or that are closely tied to their
given type—such as increment, decrement, and dereference—usually should be
members.
• Symmetric operators—those that might convert either operand, such as the
arithmetic, equality, relational, and bitwise operators—usually should be defined
as ordinary nonmember functions.

IO Operators Must Be Nonmember Functions IO operators usually must be declared as friends

The Copy Constructer

the first parameter is a reference to the class type.
usually not be eaplicit.

the difference between direct initialization and copy initialization.
direct initialization :the compiler use ordinary function matching to select the cnstructer that best matchs the arguments we provide;
copy initialization : the compiler copy the right oprand into the object being created,converting that operand if necessary.

1 2	string s(dots); // direct initialization string s2 = dots; // copy initialization

Copy initialization happens
• Define variables using an =
• Pass an object as an argument to a parameter of nonreference type
• Return an object from a function that has a nonreference return type
• Brace initialize the elements in an array or the members of an aggregate class
• Some class types also use copy initialization for the objects they allocate.
insert or push:copy initialize empalce : direct initialized

The Copy-Assignment Operater

Assignment operators ordinarily should return a reference to their left-hand operand.
copy-assignment operator is function named operator=.
and is used when assignment occurred.

The Destructor

prefixed by a tilde (~). no return value and takes no parameters:

When a Destructor Is Called
• Variables are destroyed when they go out of scope.
• Members of an object are destroyed when the object of which they are a part is
destroyed.
• Elements in a container—whether a library container or an array—are destroyed
when the container is destroyed.
• Dynamically allocated objects are destroyed when the delete operator is
applied to a pointer to the object
• Temporary objects are destroyed at the end of the full expression in which the
temporary was created.

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

#include<iostream>
#include<vector>
#include<initializer_list>
using std::cout;
using std::endl;
struct X
{
    X(){cout<<"X()"<<endl;};
    X(const X&){ cout<<"X(const X&)"<<endl;}; //copy
    X& operator=(const X&) //copy assignment
    {
        cout<<"X& operater=(const X&)"<<endl;
        return *this;
    }
    ~X(){cout<<"~X()"<<endl;};  //destucter
};
void f(const X&rx,X x)
{
    std::vector<X>vec;
    vec.reserve(2);
    vec.push_back(rx);
    vec.push_back(x);
}
int main()
{
    X* px=new X;
    f(*px,*px);
    delete px;
    return 0;
}

Classes That Need Destructors Need Copy and Assignment
If a class needs a copy constructor, it almost surely needs a copy-assignment operator.
= default:use the defaluter constructer;(only on the default constructor or a copy-control member)
= delete: unable the constructer;

The Destructor Should Not be a Deleted Member
if a class has a data member that cannot be default
constructed, copied, assigned, or destroyed, then the corresponding member will be a
deleted function.

Copy Control and Resource Management

two points in assignment operator:
• Assignment operators must work correctly if an object is assigned to itself.
• Most assignment operators share work with the destructor and copy
constructor.

SteVec

Each StrVec will have three pointers into the space it uses for its elements:
• elements, which points to the first element in the allocated memory
• first_free, which points just after the last actual element
• cap, which points just past the end of the allocated memory