C++基础容器
序列型容器
数组
● 概念
○ 代表内存里一组连续的同类型存储区
○ 可以用来把多个存储区合并成一个整体
● 数组声明
○ int arr[10];
○ 类型名称int表述数组里面所有元素的类型
○ 名称arr是数组的名称
○ 整数10表示数组里面的元素个数
○ 数组里元素个数不可以改变
● 使用
○ 每个元素都有下标，通过下标可以直接访问任意一个元素
○ 下标从0开始到元素个数减一为止
○ 超过范围的下标不可以使用
○ 数组名称和下标一起可以表述数组里面的元素。arr[4]
● 优点
○ 可以编写循环依次处理数组里面所有的元素
○ 循环变量可以依次代表所有有效下标
○ 下标标识了一个元素在数组的位置
off-by-one error（差一错误）
● 考虑问题原则
○ 首先考虑最简单的情况的特例，然后将结果外推
○ 仔细计算边界
○ 一般使用左闭右开的区间来表示范围
C语言中设计数组下标的原则：从0开始使用非堆成区间；
1.让这个区间是非对称区间
2.让下界可以取到，让上界取不到
这样设计的好处：
1.取值范围：下界到上界
2.如果这个取值范围为空，上界值==下界值
3.即使取值范围为空，上界值永远不可能小于下界值
数组的增删改查
1.在尾部添加和删除时间复杂度为O(1)；
2.不在尾部添加和删除时间复杂度为O(n)；
3.数组遍历高效，时间复杂度为O(1)；
4.数组查找的时间复杂度为O(n)，取决于数组容量；
二维数组的访问
1.在一个小的时间窗内访问的变量地址越接近越好，这样执行速度快；
2.也就是说一般情况下需要将长循环放在内层，最短的循环放在外层以减少cpu跨切循环层的次数；
代码展示：
#include <iostream> using namespace std; #include <vector> int main() { // 数组访问 int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 0, 0}; // 推荐方式 ++ 写在前面避免拷贝构造 提速 for (int index = 0; index < 10; ++index) cout << a[index] << " "; cout << endl; // 不推荐方式 for (int index = 0; index <= 9; ++index) cout << a[index] << " "; // 数组的查找 int b[] = { 1, 2, 3, 4 }; int len = sizeof(b) / sizeof(b[0]);//得到数组容量 for (int index = 0; index < len; ++index) { if (b[index] == 5) { cout << index << endl; return 0; } } //二维数组的访问： int c[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 << c[row][col] << " "; } cout << endl; } return 0; }
动态数组 std::vector
vector是面向对象的动态数组 – 使用简单的数组是无法动态扩容插入元素，因为容量有限
vector插入操作
● vec.insert(–vec.end(), 6);
● vec.push_back(5);
vector删除操作
● vec.pop_back();
● vec.erase(vec.end() - 2);
示例代码：
#include <iostream> #include <vector> using namespace std; int main() { // 创建动态数组vector vector<int> vec = { 1,2,3,4 }; cout << "size is " << vec.size() << endl; cout << "capacity is " << vec.capacity() << endl; // 遍历所有元素 for (int index = 0; index < vec.size(); ++index) { cout << vec[index] << endl; } // 在尾部插入一个元素5 vec.push_back(5); cout << "size is " << vec.size() << endl; cout << "capacity is " << vec.capacity() << endl; // 遍历所有元素 for (int index = 0; index < vec.size(); ++index) { cout << vec[index] << endl; } // 在中间插入一个元素6 vec.insert(--vec.end(), 6); cout << "size is " << vec.size() << endl; cout << "capacity is " << vec.capacity() << endl; // 遍历所有元素 for (int index = 0; index < vec.size(); ++index) { cout << vec[index] << endl; } // 在尾部移除一个元素 vec.pop_back(); cout << "size is " << vec.size() << endl; cout << "capacity is " << vec.capacity() << endl; // 遍历所有元素 for (int index = 0; index < vec.size(); ++index) { cout << vec[index] << endl; } // 在任意位置移除一个元素 vec.erase(vec.end() - 2); cout << "size is " << vec.size() << endl; cout << "capacity is " << vec.capacity() << endl; // 遍历所有元素 for (int index = 0; index < vec.size(); ++index) { cout << vec[index] << endl; } return 0; }
字符串和字符数组
● 字符串变量
○ 字符串是以空字符{‘\0’}结束的字符数组
○ 空字符’\0’自动添加到字符串的内部表示中
○ 在声明字符串变量时，应该为这个空结束符预留一个额外的元素空间 char str[11] = {“helloworld”};
● 字符串常量
○ 字符串常量是一对双引号括起来的字符序列
○ 字符串中每个字符作为一个数组元素存储 “helloworld”
ASCII码一览表，ASCII码对照表 (biancheng.net)
Unicode编码
● 最初目的是把世界上的文字都映射到一套字符空间中
● 为了表示Unicode字符集，有五种Unicode编码方式，这里说3中
○ utf-8 ： 1byte 表示，可以兼容ascii
■ 存储效率高，变长，无字节序问题
○ utf-16
■ 特点是定长，有字节序的问题（不可作为外部编码）
○ utf-32
■ 特点是定长，有字节序问题（不可作为外部编码）
● 编码错误的根本原因是在于编码方式和解码方式的不统一
windows文件可能有Bom 如果在其他平台可以去掉bom
字符串的指针表示方法
● 指针表示方法 – char* pStrHelloWrold = “helloworld”;
字符串的常见操作
● 字符串长度：strlen(s);
● 字符串比较：strcmp(s1, s2);
● 字符串拷贝：strcpy(s1, s2); 复制s2到s1s
● 复制指定长度字符串：strncpy(s1, s2, n);
● 字符串拼接：strcat(s1, s2);
● 查找字符：strchr(s1, ch);
● 查找字符串：strstr(s1, s2)；
字符串操作的问题
● C中原始字符串操作在安全性和效率存在一定的问题
○ 缓冲区溢出问题
○ strlen的效率可以提升：空间换时间
#include <string.h> #include <iostream> using namespace std; int main() { // 定义一个数组 char strHelloWorld[11] = { "helloworld" }; // 这个定义可以 char* pStrHelloWrold = "helloworld"; pStrHelloWrold = strHelloWorld; //strHelloWorld = pStrHelloWrold; // 数组变量的值不允许改变 // 字符0, '\0', '0'的区别 char c1 = 0; char c2 = '\0'; char c3 = '0'; // 通过数组变量遍历修改数组中的元素值 for (int index = 0; index < strlen(strHelloWorld); ++index) { strHelloWorld[index] += 1; std::cout << strHelloWorld[index] << std::endl; } // 通过指针变量遍历修改数组中的元素值 for (int index = 0; index < strlen(strHelloWorld); ++index) { pStrHelloWrold[index] += 1; std::cout << pStrHelloWrold[index] << std::endl; } cout << endl; // 换行 // 计算字符串长度 cout << "字符串长度为: " << strlen(strHelloWorld) << endl; cout << "字符串占用空间为: " << sizeof(strHelloWorld) << endl; return 0; }
#include <string.h> //使用C库的头文件 #include <iostream> using namespace std; const unsigned int MAX_LEN_NUM = 16; const unsigned int STR_LEN_NUM = 7; const unsigned int NUM_TO_COPY = 2; int main() { char strHelloWorld1[ ] = { "hello" }; char strHelloWorld2[STR_LEN_NUM] = { "world1" }; char strHelloWorld3[MAX_LEN_NUM] = {0}; //strcpy(strHelloWorld3, strHelloWorld1); // hello strcpy_s(strHelloWorld3, MAX_LEN_NUM, strHelloWorld1); //strncpy(strHelloWorld3, strHelloWorld2, NUM_TO_COPY); // wollo strncpy_s(strHelloWorld3, MAX_LEN_NUM, strHelloWorld2, NUM_TO_COPY); //strcat(strHelloWorld3, strHelloWorld2); // wolloworld1 strcat_s(strHelloWorld3, MAX_LEN_NUM, strHelloWorld2); //unsigned int len = strlen(strHelloWorld3); unsigned int len = strnlen_s(strHelloWorld3, MAX_LEN_NUM); for (unsigned int index = 0; index < len; ++index) { cout << strHelloWorld3[index] << " "; } cout << endl; // 小心缓冲区溢出 //strcat(strHelloWorld2, "Welcome to C++"); strcat_s(strHelloWorld2, STR_LEN_NUM, "Welcome to C++"); return 0; }
C++中的std::string
● C++中提供了string类型专门表示字符串
● 使用string可以更加安全方便的管理字符串
使用起来比原始的C风格的方法更安全和方便，对性能要求不是特别高的常见可以使用。
示例代码：
#include <iostream> #include <string> using namespace std; int main() { // 字符串定义 string s1;//定义空字符串 string s2 = "helloworld";//定义并初始化 string s3("helloworld"); string s4 = string("helloworld"); // 获取字符串长度 cout << s1.length() << endl; cout << s1.size() << endl; cout << s1.capacity() << endl; // 字符串比较 s1 = "hello", s2 = "world"; cout << (s1 == s2) << endl; cout << (s1 != s2) << endl; // 转换成C风格的字符串 const char *c_str1 = s1.c_str(); cout << "The C-style string c_str1 is: " << c_str1 << endl; // 随机访问 for (unsigned int index = 0; index < s1.length(); ++index) { cout << c_str1[index] << " "; } cout << endl; for (unsigned int index = 0; index < s1.length(); ++index) { cout << s1[index] << " "; } cout << endl; // 字符串拷贝 s1 = "helloworld"; s2 = s1; // 字符串连接 s1 = "helllo", s2 = "world"; s3 = s1 + s2; //s3: helloworld s1 += s2; //s1: helloworld return 0; }
