C++ primer 5th笔记

多态最直接的定义就是让具有继承关系的不同类对象可以调用相同名称的成员函数，并产生不同的响应结果。主要是软件的扩展性
#include <头文件名> 与#include “头文件名” ：前者为编译环境默认路径下的头文件，后者一般为自己定义的头文件（要求与程序代码位于相同的路径下）
由于各家所研发出来的类库可能会有相同的类名称，因此有了命名空间的概念。
变量一般为小写字母开头，常数全大写字母并配合下划线，函数习惯小驼峰
编译后，产生’目标文件.obj’和’可执行文件.exe’两个文件，源代码程序每修改一次都必须重新编译，但是运行速度快。解释器会对高级语言源代码进行逐行解释，解释完一行执行后才会接着解释下一行，运行速度慢，但占用内存少。
静态内存分配：变量内存分配是在程序编译时进行的，即编译时就确定变量类型
动态内存分配：变量内存分配是在程序运行时才进行，即运行时才确定变量的类型。
C++属于静态内存分配语言，必须在编译时分配内存空间给变量，因此变量需先声明后使用。
使用宏#define定义常数时，程序会在编译前就调用宏处理程序，用宏定义的内容替换宏定义的标识符，然后进行编译。
有符号整数（signed）就是有正负号之分的整数，范围：-2147483648 到 2147483647
无符号整数（unsigned）只能存储正整数，所以它的数值范围更大：0 到 4294967295
浮点数没有signed与unsigned之分
字符型每一个字符占用1个字节（8位）长度，在内存中仍然以整数数值方式存储，也有signed与unsigned之分，范围：-128 到 127
char ch = 65 即 char ch = ‘A’
取模符号%只能用于两个整数
bool num = true; cout << "num = " << num << endl; // num = 1;
设置数组值时，如果初值个数少于指定数组元素个数，则剩余的被填0
要获取arr[2][3]的内存地址，使用 *(arr+2)+3
基本上在C/C++中，字符串是由字符数组组成的，但一定要在最后加上’\0’
char name[4][10] = {“justinian”, “momo”, “becky”, “bush”}; // 这样声明会使得每个维数一定会使用10个字符类型的内存空间，这样就会浪费许多内存空间来存储空字符’\0’
可以使用 char *name[4] = {“justinian”, “momo”, “becky”, “bush”}; 这样的话，每个数组元素name[i]都用来存储所指定字符串的内存地址，不会造成浪费。
一旦有了引用，那么所有作用于引用的运算产生的效果都会累积到原变量
如果在主程序main()函数里调用了自定义函数，却将自定义函数定义在main函数后面，则会产生报错。
在C++中，传递参数有三种方式：传值、传址、传引用（推荐）
传地址：

void fun(int *a, int *b){
}
fun(&a, &b);
1
2
3

边际效应：我们向往某事物时，情绪投入越多，第一次接触到此事物时情感体验也越为强烈，但是，第二次接触时，会淡一些，第三次，会更淡……以此发展，我们接触该事物的次数越多，我们的情感体验也越为淡漠，一步步趋向乏味。这种效应，在经济学和社会学中同样有效，在经济学中叫“边际效益递减率”，在社会学中叫“剥夺与满足命题”，是由霍曼斯提出来的，用标准的学术语言说就是：“某人在近期内重复获得相同报酬的次数越多，那么，这一报酬的追加部分对他的价值就越小。
C++提供了5种变量等级的"类型修饰词"：auto、static、extern、static extern、register
private:此区块的成员只能被此对象的成员函数所存取
protected：主要让继承此类的新类能定义该成员的存取级别
public：可被其他对象或外部程序调用与存取

第一、二章：变量和基本类型

基本内置类型

unsigned

除去布尔型和扩展的字符型外，其他整型可以划分为带符号的和无符号的两种。带符号类型可以表示正数、负数或0，无符号类型则仅能表示大于等于0的值。

※ 如果表达式里既有带符号类型又有无符号类型，当这个带符号类型取值为负时会出现异常，因为带符号数会自动转换成无符号数。所以切勿混用带符号与无符号类型。
unsigned u = 10, u2 = 42 ,u - u2 = 4294967264
10, 10u, 10L, 10uL, 012, 0xC：整形字面值，无符号整形字面值，长整形字面值，无符号长整形字面值，八进制整形字面值，十六进制整形字面值；
int month = 09, day = 07; 八进制整形，八进制中没有9，所以会报错。
1024f；非法，整形字面值不可加后缀f；

float与double

float最小尺寸为6位有效值，double最小尺寸为10位有效值。

'A’与"A"

前者代表单独的字符A
==※==后者代表了一个字符的数组，包含两个字符：一个是字母A，另一个是空字符(‘\0’)

布尔类型转换时

非布尔类型值赋给布尔类型值时，初始值为0，结果为false。除此之外为true
布尔类型值赋给非布尔类型值时，初始值为false，结果为0。初始值true，结果为1

初始化与赋值

初始化不是赋值
初始化：创建变量时赋予其一个初始值
赋值：把对象的当前值擦除，用一个新的值来替代

初始化

定义于函数体内的内置类型的对象如果没有初始化，则其值未定义，如果试图拷贝或者访问此类值将引发错误。（所以建议初始化每一个内置类型的变量）
而类的对象如果没有显式地初始化，则其值由类决定。（例如string类如果没有指定初值则生成一个空串）

int i = { 3.14 }; 非法，不能执行强制转换，因为存在丢失信息的风险
int i = 3.14;合法，已强制转换。

声明与定义

声明规定了变量的类型和名字，定义不仅这样，还会申请存储空间，也有可能直接赋初始值。

extern int i；	//声明i，但无定义（如果赋初始值就是定义了）
int j; 			// 声明并定义j
1
2

变量能被多次声明，但只能被定义一次

含义是在编译阶段检查类型

用户自定义的类名一般以大写字母开头 Sales_item

一旦定义了引用，就无法令其再绑定到另外的对象

复合类型

引用与指针

引用是其他对象的别名。指针本身就是对象（所以它本身也有自己的地址），存放其他对象的地址
※ 因为引用不是对象，没有实际地址，所以不能定义指向引用的指针

int *p1 = nullptr;  int *p1 = NULL; //等价于int *p1 = 0
int *p1 = 0;  //直接将p1初始化为字面常量0来生成空指针
1
2

推荐使用nullptr

pi = &ival；//pi的值被改变，此时pi里是ival的地址，pi指向了ival
*pi = 0; //ival的值被改变，指针pi并没有改变
1
2

任何非0指针对应的bool都是true；if(pi)
建议 int *p这种写法

指向指针的指针

int  ival = 1024;
int *pi = &ival；
int **ppi = &pi；
1
2
3

遇到复杂的指针和引用时，建议从右向左阅读

指向指针的引用

int i = 42;
int *p；
int *&r = p；// r是一个对指针p的引用

r = &i；// 因为r是引用了一个指针，所以给r赋值&i就是令p指向i
*r = 0; // 解引用r得到i，将i的值改为0；
1
2
3
4
5
6

为什么没有指向引用的指针？因为引用本身就不是一个对象。

const

const对象一旦创建后其值就不能再改变，所以const对象必须初始化
如果想在多个文件之间共享const对象，就必须在变量的定义之前加extern关键字

int errNumb = 0；
int *const curErr = &errNumb； // curErr将一直指向errNumb（此时可以通过指针修改errNumb的值）
const double pi = 3.14;
const double *const pip = &pi；	// pip是一个指向常量对象的常量指针（都不可修改）
const int *p;	//合法，指向常量的指针可以不初始化。
onst int *const p3;	//不合法，常量指针未初始化；
1
2
3
4
5
6

第三章 字符串、常量和数组

命名空间

操作符（::）的意思是：编译器应从操作符左侧名字所示的作用域中寻找右侧那个名字
※ 头文件里的内容会拷贝到所有引用它的文件中，所有应该避免在头文件中使用using声明

string

在用cin读取string对象时，会自动忽略开头的空白，并在下一个空白处停止
如果输入" Hello World “，那么输出将是"Hello”
要解决这个问题可以使用getline(cin, s)，当遇见换行符时停止

※ string中的size()函数返回的其实是一个unsigned无符号的int值。所以，对于表达式s.size() < n来说，如果n是一个负值，则这个表达式的结果几乎100%是true，因为负值n会自动转换成一个比较大的无符号值。
所以如果一个表达式里已经有了size()函数就不要再使用int了，这样可以避免混用int和unsigned可能带来的问题
C++中，字符串字面值与string是不同的类型，string s = “hello” + ","是错误的。必须保证每个加号两侧的运算对象至少有一个是string。

不管什么时候，只要对string对象使用了下标，都要确认这个下标处有值
小tips:

for (decltype(s.size()) index=0;  index != s.size(); index++ ) {}
1

题目：

string s;
cout << s[0] << endl;
//合法，定义后就占用一个字节，包含’\0’。
1
2
3

vector

vector中只能存放同一种类型对象
vector不能存放引用，因为引用不是对象

vector<int> v1(10, 1);	// 有10个元素，每个值都是1
vector<int> v1{10, 1};	// 有2个元素，分别是10，1
vector<string> svec(10, "null");	//正确，创建了一个包含10个元素为“null”的vector对象。
1
2
3

范围for语句体内不应改变其所遍历序列的大小

只能对已确认存在的元素执行下标操作（否则常常会出现缓冲区溢出buffer overflow）

迭代器

begin成员指向容器中第一个元素，而end返回容器尾元素的后一个元素（即不存在的元素）
当容器为空时，begin和end返回的是同一个迭代器，即尾后迭代器

数组

要理解数组声明的含义，最好是从数组的名字开始，由内向外依次阅读
int ia[txt_size()]; 当txt_size()是constexpr时正确；否则错误

string sa[10];
int ia[10];
int main() {
    string sa2[10];
    int ia2[10];
}

1
2
3
4
5
6
7

sa：空字符串；
ia：0；
sa2：空字符串；
ia2：不确定值。

指针和数组

string nums[] = {"one", "two", "three"};
string *p = &nums[0];
string *p2 = nums;	//等价于 p2 = &nums[0]
// 	通常情况下，使用数组类型的对象其实是使用一个指向该数组首元素的指针
1
2
3
4

使用数组类型的对象，其实就是使用一个指向该数组首元素的指针

int ia[] = {0, 1, 2, 3, 4};
auto ia2(ia);	// ia2是一个整型指针，指向ia的第一个元素
但是如果使用decltype时转换不会发生、
decltype(ia) ia3 = {0, 1, 2, 3, 4};	//此时ia3是一个含有5个整数的数组
1
2
3
4

要特别注意：尾后指针不能执行解引用和递增操作

C++程序应该尽量使用vector和迭代器，而避免使用内置数组和指针
应该尽量使用string，而避免使用C风格的基于数组的字符串

多维数组

严格地说，C++中并没有多维数组，只有数组的数组。
int ia[3][4]; //大小为3的数组，每个元素是含有4个整数的数组
使用for循环多维数组时，除最内层循环外，其他循环的控制变量应该为引用类型（否则可能会出现转换为指向数组首元素指针的情况）

int ia[3][4];	//大小为3的数组，其中每个元素都是含有4个整数的数组
int (*p)[4] = ia;	//	p指向含有4个整数的数组
p = &ia[2];	// p指向ia的尾元素

int *ip[4];	//	整型指针的数组
int (*ip)[4];	//指向含有4个整数的数组
1
2
3
4
5
6

第四章：表达式

算术运算符

当优先级相同时，按照从左向右的顺序组合

bool b = true;
bool c = -b;	// c依旧是true;因为b参与运算后值被转为1，而-1不等于0，所以转为bool后为true
1
2

参与取模运算%的运算对象必须为整数类型

const char *cp = "Hello World";
if (cp && *cp)
当指针cp不为空时，才判断解引用cp的值。
我们知道，cp不为空，&&左侧为true；*cp为’H’，右侧也为真，所以if语句为真。
1
2
3
4

避免使用后置递增/递减，因为后置版本需要将原始值存储起来以便于返回这个未修改的内容

成员访问运算符

解引用运算符的优先级低于点运算符

ptr->men 等价于 (*ptr).men;
1

位运算

强烈建议仅将位运算符用于处理无符号类型
左移运算符 << 在右侧插入值为0的二进制位
右移运算符 >> 行为取决于左侧运算对象的类型
如果是无符号型，在左侧插入值为0的二进制位
如果是带符号型，在左侧插入值为0的二进制位或插入符号位的副本
位求反运算符 `：0置1，1置0
位异或运算符^：两个中只有1个1则为1，否则为0

cout << 10 < 42;	//错误，试图比较cout和42！
1

sizeof

sizeof(obj);	//这种情况返回存储obj所占空间的大小
sizeof obj;		//这种情况返回obj类型 所占空间的大小
1
2

int x[10];   int *p = x;
cout << sizeof(x)/sizeof(*x) << endl;	// 40/4=10，数组所占的字节数/数组类型int所占的字节数，就是数组的个数；
cout << sizeof(p)/sizeof(*p) << endl;	// 4/4=1，指针所占的字节数/int所占的字节数。

1
2
3
4

类型转换

int val = 3.14 + 3;	//	3会转换为double，然后执行浮点数加法运算，再将double转为int赋予val
3.1415L + 'a';	// 'a'提升为int，然后int转为long double
cval + fval;	// cval提升为int，然后int转为float
fval = ui - ival * 1.0;	//	ival->double,ui->double,double->float；
1
2
3
4

强烈建议避免强制类型转换

第五章： 语句

在switch中，哪怕default没用，也最好加上
鲁棒是Robust的音译，也就是健壮和强壮的意思。它也是在异常和危险情况下系统生存的能力。

第六章：函数

函数基础

局部静态对象：即使其所在的函数执行结束对它也没有影响，它直到程序终止才被销毁。
在C++中，建议使用引用类型的形参代替指针类型的形参。而且，当函数无需改变引用形参的值时，最好将形参声明为常量引用

const int &r = 42;	//正确
int &r = 42;	// 错误，不能用字面值初始化一个非常量引用
1
2

char *argv[]；等同于 char **argv；
1

不要返回局部对象的引用或指针
如果main函数结尾处没有return语句，编译器将隐式地插入一条返回0的return语句
重载：名字相同，形参列表不同

数组形参

void print(const int*);
void print(const int[]);
void print(const int[10]);
// 这三者等价，而[10]只是表示我们期望数组含有多少元素，实际不一定
1
2
3
4

通常应该在函数声明中指定默认实参，并将该声明放在头文件中

构造函数

无论何时，只要类的对象被创建，就会执行构造函数
struct 于class的区别

第九章：顺序容器

vector:	可变大小数组。访问快，在尾部之外位置插入/删除元素慢
deque：双端队列。访问快，在头尾位置插入/删除元素快
list: 双向链表。只支持双向的顺序访问。任何位置插入/删除都很快
forward_list: 单向链表。只能单向顺序访问。在任何位置插入/删除都很快
array：固定大小数组。访问快，不能添加/删除元素
string：与vector基本一样，但只能保存字符。访问快，在尾部插入/删除快
通常情况下，使用vector是最好的选择
如果要求随机访问元素：vector或deque
如果要求在中间插入/删除元素：list或forward_list
如果要求在头尾插入/删除元素且不在中间位置插入/删除元素：deque
1
2
3
4
5
6
7
8
9
10

vector

vector说明与初始化与内置函数

说明

• vector是向量类型，可以容纳许多类型的数据，因此也被称为容器
• 可以理解为动态数组，是封装好了的类
• 进行vector操作前应添加头文件 #include

初始化

//定义具有10个整型元素的向量（尖括号为元素类型名，它可以是任何合法的数据类型），不具有初值，其值不确定
vector<int>a(10);

//定义具有10个整型元素的向量，且给出的每个元素初值为1
vector<int>a(10,1);

//用向量b给向量a赋值，a的值完全等价于b的值
vector<int>a(b);

//将向量b中从0-2（共三个）的元素赋值给a，a的类型为int型
vector<int>a(b.begin(),b.begin+3);

 //从数组中获得初值
int b[7]={1,2,3,4,5,6,7};
vector<int> a(b,b+7）;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

内置函数

#include
vector<int> a,b;
//b为向量，将b的0-2个元素赋值给向量a
a.assign(b.begin(),b.begin()+3);
//a含有4个值为2的元素
a.assign(4,2);
//返回a的最后一个元素
a.back();
//返回a的第一个元素
a.front();
//返回a的第i元素,当且仅当a存在
a[i];
//清空a中的元素
a.clear();
//判断a是否为空，空则返回true，非空则返回false
a.empty();
//删除a向量的最后一个元素
a.pop_back();
//删除a中第一个（从第0个算起）到第二个元素，也就是说删除的元素从a.begin()+1算起（包括它）一直到a.begin()+3（不包括它）结束
a.erase(a.begin()+1,a.begin()+3);
//在a的最后一个向量后插入一个元素，其值为5
a.push_back(5);
//在a的第一个元素（从第0个算起）位置插入数值5,
a.insert(a.begin()+1,5);
//在a的第一个元素（从第0个算起）位置插入3个数，其值都为5
a.insert(a.begin()+1,3,5);
//b为数组，在a的第一个元素（从第0个元素算起）的位置插入b的第三个元素到第5个元素（不包括b+6）
a.insert(a.begin()+1,b+3,b+6);
//返回a中元素的个数
a.size();
//返回a在内存中总共可以容纳的元素个数
a.capacity();
//将a的现有元素个数调整至10个，多则删，少则补，其值随机
a.resize(10);
//将a的现有元素个数调整至10个，多则删，少则补，其值为2
a.resize(10,2);
//将a的容量扩充至100，
a.reserve(100);
//b为向量，将a中的元素和b中的元素整体交换
a.swap(b);
//b为向量，向量的比较操作还有 != >= > <= <
a==b;

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

顺序访问vector的几种方式

添加元素

//添加
vector<int>a;
for(int i=0;i<10;++i){a.push_back(i);}

//从数组中选择元素向向量中添加
int a[6]={1,2,3,4,5,6};
vector<int> b;
for(int i=0;i<=4;++i){b.push_back(a[i]);}

//从现有向量中选择元素向向量中添加
int a[6]={1,2,3,4,5,6};
vector<int>b;
vector<int>c(a,a+4);
for(vector<int>::iterator it=c.begin();it<c.end();++it)
{
	b.push_back(*it);
}

//从文件中读取元素向向量中添加
ifstream in("data.txt");
vector<int>a;
for(int i;in>>i){a.push_back(i);}

//错误赋值！
vector<int>a;
for(int i=0;i<10;++i){a[i]=i;}//下标只能用来获取已经存在的元素
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

从向量中读取元素
通过下标方式获取

int a[6]={1,2,3,4,5,6};
vector<int>b(a,a+4);
for(int i=0;i<=b.size()-1;++i){cout<<b[i]<<endl;}
1
2
3

通过迭代器方式读取

 int a[6]={1,2,3,4,5,6};
 vector<int>b(a,a+4);
 for(vector<int>::iterator it=b.begin();it!=b.end();it++){cout<<*it<<"  ";}
1
2
3

常用的算法

 #include
 //对a中的从a.begin()（包括它）到a.end()（不包括它）的元素进行从小到大排列
 sort(a.begin(),a.end());
 //对a中的从a.begin()（包括它）到a.end()（不包括它）的元素倒置，但不排列，如a中元素为1,3,2,4,倒置后为4,2,3,1
 reverse(a.begin(),a.end());
  //把a中的从a.begin()（包括它）到a.end()（不包括它）的元素复制到b中，从b.begin()+1的位置（包括它）开始复制，覆盖掉原有元素
 copy(a.begin(),a.end(),b.begin()+1);
 //在a中的从a.begin()（包括它）到a.end()（不包括它）的元素中查找10，若存在返回其在向量中的位置
  find(a.begin(),a.end(),10);
1
2
3
4
5
6
7
8
9

deque

deque说明

Vector 容器是单向开口的连续内存空间，deque 则是一种双向开口的连续线性空间。所谓的双向开口，意思是可以在头尾两端分别做元素的插入和删除操作，当然，vector 容器也可以在头尾两端插入元素，但是在其头部操作效率奇差，无法被接受。

eque 容器和 vector 容器最大的差异：
一在于 deque 允许使用常数项时间对头端进行元素的插入和删除操作。
二在于 deque 没有容量的概念，因为它是动态的以分段连续空间组合而成，随时可以增加一段新的空间并链接起来，换句话说，像 vector 那样，”旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间”这样的事情在 deque 身上是不会发生的。因此，deque 没有必须要提供所谓的空间保留(reserve)功能。
除非有必要，我们应该尽可能的使用 vector，而不是 deque。对 deque 进行的排序操作，为了最高效率，可将 deque 先完整的复制到一个 vector 中，对 vector 容器进行排序，再复制回 deque。

deque的API

(1)	构造函数

deque():创建一个空deque

deque(int nSize):创建一个deque,元素个数为nSize

deque(int nSize,const T& t):创建一个deque,元素个数为nSize,且值均为t

deque(const deque &):复制构造函数

(2)	增加函数

void push_front(const T& x):双端队列头部增加一个元素X

void push_back(const T& x):双端队列尾部增加一个元素x

iterator insert(iterator it,const T& x):双端队列中某一元素前增加一个元素x

void insert(iterator it,int n,const T& x):双端队列中某一元素前增加n个相同的元素x

void insert(iterator it,const_iterator first,const_iteratorlast):双端队列中某一元素前插入另一个相同类型向量的[forst,last)间的数据

(3)	删除函数

Iterator erase(iterator it):删除双端队列中的某一个元素

Iterator erase(iterator first,iterator last):删除双端队列中[first,last）中的元素

void pop_front():删除双端队列中最前一个元素

void pop_back():删除双端队列中最后一个元素

void clear():清空双端队列中最后一个元素

(4)	遍历函数

reference at(int pos):返回pos位置元素的引用

reference front():返回手元素的引用

reference back():返回尾元素的引用

iterator begin():返回向量头指针，指向第一个元素

iterator end():返回指向向量中最后一个元素下一个元素的指针（不包含在向量中）

reverse_iterator rbegin():反向迭代器，指向最后一个元素

reverse_iterator rend():反向迭代器，指向第一个元素的前一个元素

(5)	判断函数

bool empty() const:向量是否为空，若true,则向量中无元素

(6)	大小函数

Int size() const:返回向量中元素的个数

int max_size() const:返回最大可允许的双端对了元素数量值

(7)	其他函数

void swap(deque&):交换两个同类型向量的数据

void assign(int n,const T& x):向量中第n个元素的值设置为x
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

#include "stdafx.h"
#include
#include
 
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
	deque<int> d;
	d.push_back( 10 );
	d.push_back(20);
	d.push_back(30);
	cout<<"原始双端队列："<<endl;
	for(int i = 0; i < d.size(); i++)
	{
		cout<<d.at(i)<<"\t";
	}
	cout<<endl;
	d.push_front(5);
	d.push_front(3);
	d.push_front(1);
 
	cout<<"after push_front(5.3.1):"<<endl;
	for(int i = 0;i < d.size();i++)
	{
		cout<<d.at(i)<<"\t";
	}
	cout<<endl;
	d.pop_front();
	d.pop_front();
	cout<<"after pop_front() two times:"<<endl;
	for(int i = 0;i < d.size();i++)
	{
		cout<<d.at(i)<<"\t";
	}
	cout<<endl;
	return 0;
}
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

list

list说明

list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。 所以，在链表的任一位置进行元素的插入、删除操作都是快速的。
与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
list的实现原理：list的每个节点有三个域：前驱元素指针域、数据域和后继元素指针域。前驱元素指针域保存了前驱元素的首地址；数据域则是本节点的数据；后继元素指针域则保存了后继元素的首地址。
由于list元素节点并不要求在一段连续的内存中，显然在list中是不支持快速随机存取的，因此对于迭代器，只能通过“++”或“–”操作将迭代器移动到后继/前驱节点元素处。而不能对迭代器进行+n或-n的操作，这点，是与vector等不同的地方。
list与forward_list最主要的不同在于forward_list是单链表，只能朝前迭代，这让其更简单高效。

list的API

构造函数

list() 构造空的list
list (size_type n, const value_type& val = value_type()) 构造的list中包含n个值为val的元素
list (const list& x) 拷贝构造函数
list (InputIterator first, InputIterator last) 用[first, last)区间中的元素构造list
1
2
3
4

迭代器

begin() 返回第一个元素的迭代器
end() 返回最后一个元素下一个位置的迭代器
rbegin() 返回第一个元素的reverse_iterator,即end位置
rend() 返回最后一个元素下一个位置的reverse_iterator,即begin位置
cbegin() (C++11) 返回第一个元素的cosnt_iterator
cend() (C++11) 返回最后一个元素下一个位置的const_iterator
crbegin() (C++11) 即crend()位置
crend() (C++11) 即crbegin()位置
1
2
3
4
5
6
7
8

capacity

bool empty() const 检测list是否为空，是返回true，否则返回false
size_t size() const 返回list中有效节点的个数
1
2

函数

void push_front (const value_type& val)  //在list首元素前插入值为 val的元素
void pop_front()  //删除list中第一个元素
void push_back (const value_type& val)   //在list尾部插入值为val的元素
void pop_back() //删除list中最后一个元素
//在list position 位置中插 入值为val的元素
iterator insert (iterator position, const value_type& val) 
// 在list position位置插入n 个值为val的元素
void insert (iterator position, size_type n, const value_type& val) 
//在list position位置插入 [first, last)区间中元素
void insert (iterator position, InputIterator first, InputIterator last) 
iterator erase (iterator position)  //删除list position位置的 元素
iterator erase (iterator first, iterator last)  //删除list中[first, last)区 间中的元素
void swap (list& x)   //交换两个list中的元素
//将list中有效元素个数改变 到n个，多出的元素用val 填充
void resize (size_type n, value_type val = value_type())   
void clear()  //清空list中的有效元素
// push_back尾插：先构造好元素，然后将元素拷贝到节点中，插入时先调构造函数，再调拷贝构造函数
//emplace_back尾插：先构造节点，然后调用构造函数在节点中直接构造对象
//emplace_back比push_back更高效，少了一次拷贝构造函数的调用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

list的迭代器失效

迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

void TestListIterator1() {
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; 
	list<int> l(array, array+sizeof(array)/sizeof(array[0]));
 
	auto it = l.begin(); 
	while (it != l.end()) {
		// erase()函数执行后，it所指向的节点已被删除，
                //因此it无效，在下一次使用it时，必须先给其赋值
		l.erase(it);
		++it; 
	} 
}
1
2
3
4
5
6
7
8
9
10
11
12

解决办法：在实现erase的时候会返回删除后的后面的元素的迭代器。

// erase()函数：删除容器中的一个元素。
void TestListIterator1() {
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; 
	list<int> l(array, array+sizeof(array)/sizeof(array[0]));
 
	auto it = l.begin(); 
	while (it != l.end()) {
		it = l.erase(it); 
//保存当前要删除的位置
//list ::iterator to_delete=it2;
//it2++;//先向后走
//L.erase(to_delete);//再删除该节点
	} 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

map

unordered_map的无序体现在内部存储结构为哈希表，以便通过键值快速访问元素
与之对应的有序的关联容器为map，map的有序体现在内部存储结构为红黑树，存储时元素自动按照从小到大的顺序排列
unordered_map查找效率更高，可以达到O(1)，但是对于元素子集的范围迭代效率较低。
对于map，按照中序遍历的遍历次序，能够方便迭代得出从小到大的元素

力扣1.两数之和

迭代器

迭代器范围：左闭右开
向一个vector、string或deque插入元素会使所有指向容器的迭代器、引用和指针失效
调用swap后，元素本身并未交换，也就意味着指向容器的迭代器、引用和指针都依然有效（除string外）
每次改变容器的操作之后都应该重新定位迭代器，特别是vector、string和deque；