【OOP】模板与STL初步
命名空间
问题背景
设想，在一次的大规模程序中，你和几位搭档合作写代码。
由于所需的代码量无比庞大，你们遇到了一个无法避免的问题——标识符命名高度重合，造成了代码极度混乱。
如果要重新修改标识符的名称，不仅耗时耗力，还会导致代码的可读性降低。
这种情况下，你会怎么解决这个棘手的问题呢？
。。。。。。。。。。（手动暂停，让我们来稍作思考）。。。。。。。。。。
这时候，团队里的大神提议，将每个人的代码中所用到的标识符，都放进各自的一个专属空间里。
例：A、B、C 三人，虽然都用了标识符名称 x，但是放入各自的空间后，就可以用 A 的 x、 B 的 x、 C 的 x 来区分这三个同名不同意义的 x。
经过尝试和实行后，你们发现，问题果然迎刃而解了。
知识点
-
命名空间 = 名字空间 = 名称空间 = namespace
- 是标识符的可见范围/作用域
- 多个命名空间中可以定义同样的标识符，但是不同命名空间内的标识符意义不同，且互不干扰
- 最常见的命名空间是 std，包含了标准 C++ 库的所有内容
-
使用方法：
-
定义命名空间
namespace A { int x; float y; } -
使用命名空间
-
直接使用
// 使用命名空间 A 里的标识符 x 和 y A::x = 3; A::y = 2.2; -
使用整个命名空间
using namespace A; // 直接声明要使用的命名空间 // 由于已经声明了使用命名空间 A，因此可以直接使用标识符 x = 3; y = 2.2; -
使用部分命名空间
using A::x; // 声明要使用命名空间 A 的 x x = 3; // 由于提前声明，因此可以直接使用 A::y; // 因为没有声明要用 y，所有要用 A::y
-
-
STL初步
简介
我们最常用的命名空间是 std，因此在一开始学习代码的时候就会用using namespace std。
在命名空间 std 里，有一个十分重要且实用的 C++ 软件库——STL。
- STL = Standard Template Library = 标准模板库
- 包含组件：算法、容器、函数、迭代器
- 关键理念：基于模板编写，将 “要操作的数据” 和 “对数据执行的操作” 分离
- 命名空间：std
- 使用时需要用
std::name - 可以直接
using namespace std（但是在大型工程中不推荐使用）
- 使用时需要用
容器
容器是包含、放置数据的工具，可以分为：简单容器、序列容器、关联容器。
1. 简单容器（simple container）
- 例子：pair、tuple
- 实际上，pair 和 tuple 也不能算是容器，只可以算是 STL 中基本的数据单位
A) pair
-
由两个单独数据组成（可以是同数据类型/不同数据类型）
-
常用于 map 中，也可以用于函数中两个返回值的传递
-
代码实现：
template <class T1, class T2> // 基于模板编写 struct pair { T1 first; // 第一个成员变量 T2 second; // 第二个成员变量 } -
使用方法：
#include <utility> // pair 的头文件 #include <string> // string 的头文件 using namespace std; int main() { // 方法1：同时创建+初始化 pair <string, float> p1 ("Karry", 92.1); // 方法2：创建之后再赋值 pair <string, float> p2; p2.first = "Brenda"; p2.second = 22.1; // 方法3：使用函数 make_pair 创建+初始化 // 优势：程序可以自动推导成员变量的类型 auto p3 = make_pair ("Roy", 11.8); return 0; } -
访问方法：
// 因为 pair 只有两个元素，只需要用 first 和 second 来访问 cout << p1.first << " " << p2.second << endl; // 输出结果为：Karry 22.1 -
对 pair 进行大小比较（先比较 first，再比较 second）
template<class T1, class T2> void compare(T1 a, T2 b) { if (a > b) cout << ">" << endl; else if (a < b) cout << "<" << endl; else if (a == b) cout << "=" << endl; } //（1） pair <string, int> x = make_pair (2, "Alice"); pair <string, int> y = make_pair (2, "Bob"); compare(x,y); // 输出结果为：< //（2） pair <string, int> x = make_pair (2, "Alice"); pair <string, int> y = make_pair (1, "Bob"); compare(x,y); // 输出结果为：> //（3） pair <string, int> x = make_pair (2, "Bob"); pair <string, int> y = make_pair (2, "Bob"); compare(x,y); // 输出结果为：=
B) tuple
-
和 pair 类似，但是可以由 n 个数据组成
-
适用于有多个返回值的函数的返回值传递
-
使用方法：
#include <tuple> // tuple 的头文件 #include <string> // string 的头文件 using namespace std; int main() { // 方法1：同时创建+初始化（需要多少个数据就写多少个） tuple <string, int, float> p1 ("Karry", 23, 92.1); // 方法2：使用函数 make_tuple 创建+初始化 auto p2 = make_tuple ("Brenda", 20, 22.1); // 方法3：结合函数 tie 和 make_tuple 进行赋值创建 // 没有一个特定的 tuple 标识符，但是可以同时对个别数据进行操作 string name; int age; float marks; tie (name, age, marks) = make_tuple ("Roy", 22, 11.8); return 0; } -
访问方法：
// 使用 get 函数，通过下标访问 // 下标需要在编译时确定，只能使用确定的数字，不能使用变量，否则会编译错误 auto x = get <0> (p1); // p1[0] = "Karry" auto y = get <1> (p2); // p2[1] = 20 auto z = get <2> (p3); // p3[2] = 11.8 cout << x << " " << y << " " << z << endl; // 输出结果为：Karry 20 11.8 -
对 tuple 进行大小比较的方式和 pair 类似 [点击跳转]
-
返回值类型为 tuple 时：
tuple <int, float> calc(int n) { return make_tuple(n + 2, n / 2.0); } // 方法1：用 tuple 来接收函数返回值 tuple <int, float> a; a = calc(3); cout << get<0>(a) << " " << get<1>(a) << endl; // 方法2：用 tie 函数来接收函数返回值 // 优势：可以直接分开使用函数返回值 int num; float data; tie(num, data) = calc(3); cout << num << " " << data << endl; // 输出结果皆为：5 1.5
2. 序列容器（sequence container）
-
例子：array、vector、deque、list、forward list
-
特点概览：
长度 添加元素 删除元素 访问元素 array 固定 可以在任意位置 可以在任意位置 通过下标 vector 不固定 一般在尾部 一般在尾部 通过下标 deque 不固定 在头部、尾部 在头部、尾部 通过下标 list 不固定 可以在任意位置 可以在任意位置 双向 forward list 不固定 可以在任意位置 可以在任意位置 只可以正向
A) vector
-
可以自动扩展容量的动态数组
- 容量（capacity）是可以存放的数据数量，大小（size）是现存放的数据数量
- 当 size 达到 capacity 时，会自动将 capacity 扩充一倍
-
使用方法：
#include <vector> // vector 的头文件 using namespace std; // 创建：vector <容器中的数据类型> 容器名称; vector <int> vec; -
常用函数：
vec.size(); // 返回 vector vec 中的元素数量 vec.clear(); // 清空数组 vec.push_back(1); // 把 1 添加进 vector vec vec.pop_back(); // 把最后一个元素删除 vec.insert(vec.begin() + ind, 5); // 在下标为 ind 的位置添加元素 5，其余元素往后挪 vec.erase(vec.begin() + ind); // 把下标为 ind 的数据删除 -
遍历方法：
// 方法1：使用下标 for (int ind = 0; ind < vec.size(); ++ind) { cout << vec[ind] << " "; } // 方法2：按照范围 for (auto &x : vec) { cout << x << " "; } // 方法3：使用迭代器 // 为了方便，也可以使用 auto it; vector <int>::iterator it; for (it = vec.begin(); it != vec.end(); ++it) { cout << *it << " "; }
B) list
-
双向链表容器
-
list 中的元素可以分散存储在内存空间
优势：在任意位置插入和删除元素的时间复杂度 = O(1)，效率高，且迭代器不会失效
缺点：无法使用下标访问元素，只能遍历寻找
-
-
使用方法：
#include <list> // list 的头文件 using namespace std; // 创建：list <存储的数据类型> 标识符名称; list <int> num; -
常用函数：
num.push_front(1); // 在头部插入元素 1 num.push_back(1); // 在尾部添加元素 1 num.pop_front(); // 删除第一个元素 num.pop_back(); // 删除最后一个元素 num.insert(iter, 1); // 在 iter 指向的位置添加元素 1 num.erase(iter); // 删除 iter 指向的位置的元素 find(num.begin(), num.end(), 1); // 返回元素 1 所在位置的迭代器
3. 关联容器（associative container）
- 关联性容器，实现了有序关联数组
- 使用的数据结构是 “红黑树”（一种二叉平衡树）
- 例子：set、map
A) set
-
set 是包含不重复元素的无序集合
无序，指的是 set 内的元素不按照 “插入顺序” 进行排列
-
内部的元素根据大小顺序进行排列
-
使用方法：
#include <set> // map 的头文件 using namespace std; set <int> s; -
常用函数：
s.insert(val); // 插入元素 val（不可以插入重复的元素） s.find(val); // 返回 val 所在位置的迭代器 s.erase(s.find(val)); // 由于 set 无序且无法用下标访问，需要遍历寻找再进行删除 s.count(val); // 统计 set 内有多少元素 val // 由于不允许出现重复性的元素，因此返回值只有 0 和 1
B) map
-
将一个数据映射到另一个数据，每个元素都是一个 pair <Key, T>
map 中的每个 Key 不允许出现重复
-
可以通过下标访问，访问时如果元素不存在，则会创建一个
-
使用方法：
#include <map> // map 的头文件 #include <string> // string 的头文件 using namespace std; int main() { map <string, int> m; // 添加的方法1 // 为 map 中添加 make_pair("Karry", 921) m["Karry"] = 921; // 添加的方法2 m.insert(make_pair("Brenda", 221)); return 0; } -
常用函数：
m.find(key); // 返回指向 key 的迭代器 m.count(key); // 返回 map 内 key 的数量 // 由于不允许出现重复元素，因此返回值只有 0 或 1 m.erase(m.find(key)); // 删除元素 key
迭代器
介绍
-
迭代器（iterator）类似指针，是一种用来遍历元素的数据类型
优势：不需要暴露访问对象的内部表示就可以顺序访问对象的元素
-
以 vector 为例的使用方法：
// 定义迭代器 // 迭代器 iter 指向 int 类型的 vector vector <int>::iterator iter; x.begin(); // 返回 vector x 中第一个元素的迭代器 x.end(); // 返回 vector x 中最后一个元素之后的位置的迭代器 // begin 和 end 形成了左闭右开的区间 ++iter // 下一个位置的迭代器 --iter // 上一个位置的迭代器 iter += n // 从 iter 位置开始算，后面第 n 个位置的迭代器 iter -= n // 从 iter 位置开始算，前面第 n 个位置的迭代器 *iter // 解引用运算符，返回左值引用，返回 iter 指向的位置的数据 -
用迭代器来遍历容器的方法可参考 vector 处的遍历方法
失效
-
迭代器失效 = 迭代器不再指向原本应指向的元素
-
以 vector 为例，导致迭代器失效的情况：
-
添加元素
-
使用
insert插入元素在特定位置添加元素，其余的元素会向后挪，由于原先内存空间存储的元素改变，因此受影响的迭代器失效。
-
使用
push_back插入元素当 size 达到 capacity 时，vector 会额外申请一个 2*capacity 的内存空间，并将原有的数据移到新内存空间，因此所有的迭代器均失效。
-
-
删除元素
-
使用
erase删除元素删除特定位置的元素后，其余位置会向前挪，原先的内存空间存储的元素改变，受影响的迭代器失效。例：
vector <int> vec = {1, 2, 3, 4, 5}; auto first = vec.begin(); // first 指向 1 auto second = vec.begin() + 1; // second 指向 2 auto third = vec.begin() + 2; // third 指向 3 auto itr = vec.erase(second); // 删除了迭代器 second 指向的元素，vec = {1, 3, 4, 5} // first 指向 1，没有改变 // second 和 third 失效 // itr 指向第二个位置的新元素 3
-
-
-
迭代器的失效和容器的数据结构有关，绝对安全的准则是：修改了容器内容后，不使用先前的迭代器