【C++】基础容器（学习笔记）

一、数组

1、数组概述

1）数组概念

数组：代表内存里一组连续的同类型存储区，可以用来把多个存储区合并成一个整体

2）数组的声明

int arr[10]

1. 类型名称int表示数组里所有元素的类型
2. arr是数组的名称
3. 整数10表示数组里包含的元素个数
4. 数组里元素个数不可以改变

3）数组的使用

1. 每个元素都有下标，通过下标可以直接访问任意一个元素
2. 下标从0开始到元素个数減一为止
3. 超过范围的下标不可以使用
4. 数组名称和下标一起可以表示数组里的元素
5. 下标标识了—个数组元素在当前数组容器中的位置

4）数组的优点

可以编写循环依次处理数组里的所有元素

2、数组下标

1）off-by-one error(差一错误）

假定整数x满足边界条件x>=16 并且x<=37，那
么此范围内x的可能取值个数有多少？

37-16+1=22

high-lovw+1

2）下标的原则

下标的原则：从0开始，使用非对称区间

让下界（左侧）可以取到值，让上界（右侧）取不到值

3）下标从0开始的优点

1. 取值范围的大小：上界-下界
2. 如果这个取值范围为空，上界值=下界值
3. 即使段值范围为空，上界值永远不可能小于下界值

3、数组增删改查

在尾部添加删除，时间复杂度为O(1）

在中间添加删除，时间复杂度为O(n)

数组遍历高效，时间复杂度为o(1)

查找时间复杂度一般为O(n)，取决于数组容量

4、二维数组

二维数组：包含行列两个维度的数组

int a[2][4] = {{1,2,3,4},{5,6,7,8}};
for(int row = 0; row < 2; row++){
	for(int col = 0; col < 4; col++){
		cout << a[row][col];
	}
	cout << endl;
}
1
2
3
4
5
6
7

循环时尽可能要满足 “空间局部性〞

在一个小的时间窗口内，访问的变量地址越接近越好，这样执行速度快

一般来说，需要将最长的循环放在最内层，最短的循环放在最外层

二、动态数组

1、vector概述

vector是面向对象方式的动态数组

使用最简单的数组，无法实现动态扩容插入元素，因为容量有限

2、vector的操作

1）Vector尾部添加

使用vector容器，轻松实现动态扩容插入元素，传入的C数组，容量有限，vector可以动态管理扩容

#include 
using namespace std;
vector<int> vec = {1,2,3,4};
vec.push_back(5);
1
2
3
4

2）Vector的遍历

for (int index = 0; index < vec.size(); index++){
	cout << vec[index] << endl:
}
1
2
3

可以使用vec的capacity和size方法来查看vector当前的容量和己经存储的元素个数

3）Vector的插入

vec.insert(vec.end()-1, 4);
1

4）Vector的删除

vec.pop_back();
vec.erase(vec.end()- 1);
1
2

三、字符串

1、字符串简介

字符串是以空字符(‘\0’)结束的宇符数组

空字符(‘\0’)自动添加到字符串的内部表示中

在声明字符串变量时，应该位这个空结束符预留一个额外元素的空间

2、Unicode编码

Unicode编码：最初的目的是把世界上的文字都映射到一套字符空间中

1. UTF-8：1byte来表示字符，可以兼容ASCII码。特点是存储效率高，变长(不方便内部随机访问），无字节序问题(可作为外部编码）
2. UTF-16：2byte来表示字符。分为UTF-16BE(big endian)、UTF-16LE(little endian)。特点是定长(方便内部随机访问)，有字节序问题(不可作为外部编码）
3. UTF-32：4byte来表示字符。分为UTF-32BE(big endian)、UTF-32LE (little endian)。特点是定长(方便内部随机访问)，有字节序问题(不可作为外部编码）

Windows的文件可能有BOM(bvte order mark)。如要在其他平台使用，可以去掉BOM

编码错误的根本原因在于编码方式和解码方式的不统一

3、字符串的指针表示

char* pStrHelloWrold = "helloworld";
1

char[] 和 char*的区别

strHelloworld 不可变，strHelloworld[index]的值可变

pStrHellowrold 可变，但是pStrHelloWrold[index]指向的值不可变

4、字符串的基本操作

C中原始字符串的操作在安全性和效率存在一定的问题

调试时预处理可能需要添加：CRT_SECURE_NO_WARNINGS

1）字符串长度

strlen(s)

返回字符串s的长度（s的长度不包括’\0’）

2）字符串比较

strcmp(s1, s2)

如果s1和s2 是相同返回0

如果s1

如果s1>s2则返回值大于0

两个字符串自左向右逐个字符相比（按ASCI值大小相比较），直到出现不同的字符或遇’\0’为止。

3）字符串拷贝

strcpy(s1, s2)

复制字符串 s2到字符里 s1

4）复制指定长度字符串

strncpy(s1, s2, n)

将字符串s2中前n个字符拷贝到s1中

5）字符串拼接

strcat(s1, 2)

字符串s2接到s1后面

6）查找字符串

strchr(s1, ch)

指向字符串s1中，ch字符首次出现的位置

7）查找字符串

strstr(s1, s2)
指向字符串s1中，字符串s2首次出现的位置

四、string字符串

1、string概述

C++标准库中提供了string类型专门表示字符串

使用string可以更为方便和安全的管理字符串

使用起来比原始的C风格方法更安全和方便，对性能要求不是特别高的场景可以使用。

#include 
using namespace std;

string s1;					//定义空字符串
string s2 = "helloworld";	//定义并初始化
string s3("helloworld");	//构造函数
string s4 = string("helloworld");
1
2
3
4
5
6
7

2、字符串相关函数

1）获取字符串的长度

cout << s1.length() << endl;	//字符长度
cout << s1.size() << endl;		//字符长度
cout << s1.capacity() << endl;	//分配的空间长度
1
2
3

2）字符串比较

cout << (s1 == s2) << endl;
cout << (s1 != s2) << endl;
1
2

3）转换为C风格的字符串

const char *c_str1 = s1.c_str();
cout << c_str1 << endl;
1
2

4）随机访问

string s = "hello";
cout << s[0] << endl;	//"h"
1
2

5）字符串拷贝

string s1 = "hello";
string s2 = s1;
1
2

6）字符串连接

string s3 = s1 + s2;
1