七：STL容器类

前文

本章节了解C++标准库（Standard Template Library）中常用的容器类的用法。

正文

容器类即C++本身开发了一些管理数组、链表等数据结构的类。从 要点： 头文件： 用法： 创建： 访问： 增加： 修改： 删除： 大小： 几个方面来学习使用。

通用语法和注意事项

• 大部分都可用at(i)函数访问相应位置数据（和存储方式有关），at会检查越界情况（因此比[]耗时）
• 连续存储和使用地址的链表是存储方式，其他大部分数据结构底层还是这两个
• begin等迭代器是常用访问方式，但不是所有的都支持+i这种偏移量来访问偏移量位置元素，这和底层是不是连续存储有关

数组 array（C++11）

要点：

• C++11中新增
• 栈，不需要自己分配释放
• 初始化设定元素数量，即大小固定

头文件：

#include <array>

用法：

创建：

// array<int, 3> myArray{1, 2, 3}; // 创建大小为3且元素初始化为1 2 3的数组
// array<int, 3> myArray = {1, 2, 3}; // 同上
// array<int, 3> myArray; // 创建大小为3，此时元素值是随机未初始化的
array<int, 3> myArray{}; // 元素会被初始化为0
// 操作符=隐式声明，以来自另一array的每个元素重写array的对应元素
// 这里myArray2必须也是相同类型相同大小，否则编译报错
array<int ,3> myArray = myArray2;

访问：

// 返回的迭代器可以访问相应的元素
*myArray.begin() // *myArray.rbegin() *myArray.cbegin() *(myArray.end()-1)
myArray[i] //下标访问
myArray.front() // 访问第一个元素
myArray.back() // 访问最后一个元素
*(myArray.data()+1) // data() 返回底层的连续存储，相当于第一个元素的地址
// for遍历
for(auto i : a)
    cout << i << " ";
// 迭代器
for(auto it = a.begin(); it != a.end(); it++) 
    cout << *it << " ";
// 使用at会检查越界情况 下标不会
myArray.at(1)

增加：

// 创建时大小固定

修改：

// 可以使用访问的方法修改对应的值
void fill(const Type& val); // 清除数组并将指定元素赋值给数组所有位置
myArray.fill(0xa); // 替换所有元素值为10
myArray.swap(myArray2); // 交换两个array

删除：

// array是在栈上分配内存，不需要手动释放空间，当数组超出作用域时，会自动调用析构函数释放内存

大小：

cout << myArray.empty() << endl; // 判定空
cout << myArray.size() << endl; //返回元素数
cout << myArray.max_size() << endl; //返回最大元素数量 这里和size是一样的，因为array固定大小

数组 vector

要点：

• 可变长度
• 自动管理内存，通常占用多于静态数组的空间，因为要分配更多内存以管理将来的增长。
• 在内存中连续存储
• 访问和修改元素时间复杂度小，更换元素顺序即需要参考各时间复杂度的排序算法
• 在额外内存耗尽时进行重分配，分配的内存总量可用capacity()函数查询

头文件：

#include <vector>

用法：

创建：

vector<int> myVector; // 构造一个空的数组
vector<int> myVector = {1}; // 且初始化一些数据
vector<int> myVector(3, 4); // 构造初始3个值为4的数组
vector<int> myVector = myVector2; // 将vector赋给vector
myVector.assign(10, 100); // 使用arrign函数重新分配10个值100的数组
// assign_range(C++23)将一个范围的值赋给容器 

访问：

// 通过begin等迭代器访问
cout << myVector.front() << endl; // 第一个
cout << myVector.back() << endl; //最后一个
cout << *(myVector.data()) << endl; //取地址值
cout << myVector.at(2) << endl; // 带越界检查访问位置元素
cout << myVector[2] << endl; // 通过操作符[]访问，不进行越界检查

增加：

// insert方法插入指定位置
auto it = myVector.begin();
it = myVector.insert(it, 200); // 在开始插入200
// insert_range(C++23)插入一个元素范围
myVector.push_back(11); // 在结尾插入元素

修改：

// swap 交换内容
// 通过访问方式修改相关元素
myVector.resize(4, 100); //通过重新设置大小方式修改元素，这里不会改变已有元素，不够填充值100

删除：

myVector.erase(myVector.begin()); // 擦除指定位置元素
myVector.erase(myVector.begin(), myVector.begin() + 2); // 指定范围
myVector.pop_back(); // 移除末尾元素
myVector.resize(2); // 通过重新设置大小方式删除结尾元素
myVector.clear(); // 清除所有元素 并且size变成0，empty为真

大小：

cout << myVector.empty() << endl; // 判空
cout << myVector.size() << endl; // 当前大小
cout << myVector.max_size() << endl; // 最大可存数量大小 例如本机结果：4611686018427387903
cout << myVector.capacity() << endl;// 当前预留的存储空间可存储的数量 本机此时：6
void reserve( size_type new_cap ); // 预留存储空间

单向链表 forward_list

要点：

• 不支持快速随机访问。它实现为单链表，且实质上与其在C中的实现相比无任何开销。
• 与list相比，此容器在不需要双向迭代时提供更好的存储空间效率。
• 在从链表移除元素（通过erase_after）时，指代对应元素的迭代器或引用会失效。

头文件：

#include <forward_list>

用法：

创建：

forward_list<int> myFwlist;
forward_list<int> myFwlist{100, 200, 100};
forward_list<int> myFwlist2(myFwlist.begin(), myFwlist.end());
forward_list<int> myFwlist2(myFwlist);

访问：

// 通过begin等迭代器访问
cout << myFwlist.front() << endl; // 访问链首元素

增加：

// insert_range_after(C++23) 插入元素范围到元素后 
myFwlist.push_front(1); // 链首插入数据

修改：

// merge() 合并两个有序列表 
// sort() 排序
myFwlist.reverse(); // 反转链表
myFwlist.assign(3, 4); // 重新分配3个值为4的元素

删除：

myFwlist.pop_front(); // 移除链首元素
myFwlist.erase_after(myFwlist.begin()); // 擦查指定位置后的元素
myFwlist.unique(); // 删除连续重复元素 会保留一个
myFwlist.remove(200); // 移除值为200的所有元素

大小：

cout << myFwlist.empty() << endl; // 判空
cout << myFwlist.max_size() << endl; // 最大可存数量大小

链表 list

要点：

• 实现为双向链表，存储时每个元素需要知道前后元素地址，存储空间不需要连续
• 在结构中增加删除元素方便（如设置空指针重指向即可），
• 链表不是数组，不支持下标访问，支持从容器任何位置进行常数时间的元素插入和移除的容器

头文件：

#include <list>

用法：

创建：

list<int> myList; // 空链表
list<int> myList(11, 1); //初始化11个值1数据
list<int> myList = {1}; //初始化数据
vector<int> arr = { 1,2,3,4,5,6 };
list<int> myList(arr.begin(), arr.end()); // 通过迭代器构造
list<int> myList2(myList); // 拷贝一个现有的list
const char* str = "str";
list<char> myList(str, str + strlen(str)); // 意味着可以拷贝其他类型，字符串字面量是const char[]

访问：

// 通过begin等迭代器访问
myList.front() //访问哨兵位数据，开始是头数据，随指针变化
myList.back() //访问链尾数据

增加：

myList.push_front() //头插
myList.push_back() //尾插
// 中间插入数据需要配合find使用，即告诉编译器在哪个位置插入数据
// 下代码告诉编译器在开始和结尾找值为2的元素并返回其迭代器
auto poss = find(myList.begin(), myList.end(), 2);
myList.insert(poss, 6); //指定位置插入6
myList.insert(poss, 3, 8); //指定位置插入3个8
myList.insert(poss, myList2.begin(), myList2.end()); //指定位置插入一段数据

修改：

// 通过访问修改
// swap
merge(const &list) 合并两个有序列表 
myList.reverse(); //反转顺序
myList.unique(); // 删除连续的重复元素 会保留一个
myList.sort(); // 默认从小到大排序

删除：

myList.pop_front() //删除头部
myList.pop_back() // 删除结尾
// 同样的，也要先找到元素
myList.erase(poss); //删除指定位置的值
myList.erase(myList.begin(), myList.end()); //全删
myList.clear(); // 全删，empty为真，size为0
myList.remove(2); //移除元素2 会删除所有值为2的元素

大小：

cout << myList.empty() << endl; // 判空
cout << myList.size() << endl; // 当前大小
cout << myList.max_size() << endl; // 最大可存数量大小
resize(num); //重新设置空间大小
resize(num, elem); //并以elem元素填充不足

栈 stack

要点：

• 底层一般是数组实现
• 符合栈先进后出的特点，一种容器适配器，更多的是给予栈的功能

头文件：

#include <stack>

用法：

创建：

stack<int> myStack; // 定义一个储存数据类型为int的stack容器
stack<int> myStack[];

访问：

// stack没有begin等迭代器
top() //返回堆栈顶部的元素

增加：

myStack.push(10); //向堆栈顶部添加元素
//  push_range(C++23) 在栈顶插入元素范围 

修改：

删除：

pop() //弹出堆栈顶部的元素

大小：

cout << myStack.empty() << endl; // 是否为空
cout << myStack.size() << endl; // 当前大小

队列 queue

要点：

• 一种容器适配器，提供队列的功能——尤其是 FIFO（先进先出）数据结构
• 此类模板表现为底层容器的包装器——只提供特定的函数集合。queue 在底层容器尾端推入元素，从首端弹出元素

头文件：

#include <queue>

用法： 创建：

queue<int> myQueue; // 创建空的队列
queue<int> myQueue2(myQueue);
deque<int> deq{3, 1, 4, 1, 5};
queue<int> myQueue(deq); // 和c1类似，重载双段队列
// C++23特性
const auto il = {2, 7, 1, 8, 2};
queue<int> myQueue{il.begin(), il.end()}; // C++23

访问：

cout << myQueue.front() << endl; // 访问队首元素
cout << myQueue.back() << endl; // 访问队尾元素

增加：

myQueue.push(10); // 从队尾推入元素

修改：

删除：

myQueue.pop(); // 移除队首元素

大小：

cout << myQueue.empty() << endl; // 是否为空
cout << myQueue.size() << endl; // 当前大小

双端队列 deque

要点：

• 底层是双向队列结构（double ended queue）
• 底层由指向内存块的指针数组构成而不是链表，对deque的索引访问必须进行二次指针解引用
• 存储空间连续，结构比vector复杂
• 队列特点：首位增加删除效率高，和数组一样，中间插入要移动位置效率不高
• 创建双端队列对象时会自动分配一块内存，以便可以将对象存储在连续的位置
• 添加开头新元素时，会分配一个新的内存块并连接前一个内存块，再次向前面添加，将被存储在这个新的内存块中，直到完全填满
• 插入末尾时，分配的内存块会保留，直到完全填满；如果满了，分配新内存块并将连接到前一个块的末尾。 添加到双端队列后面的元素现在存储在新的内存块中。
• deque的存储按需自动扩张及收缩。扩张deque比扩张vector更轻便，因为它不涉及将既存元素复制到新内存位置。
• 随机访问——常数 O(1)。
• 在结尾或起始插入或移除元素——常数 O(1)。
• 插入或移除元素——线性 O(n)。

头文件：

#include <deque>

用法：

创建：

deque<int> myDeque; // 空队列
deque<int> myDeque{1, 2, 3, 1}; // 初始化数据
deque<int> myDeque2(myDeque.begin(), myDeque.end());
deque<int> myDeque(myDeque2);
// 通过assign赋值

访问：

// 通过begin等迭代器访问
cout << myDeque.at(1) << endl;
cout << myDeque[2] << endl; // 使用操作符[]访问
cout << myDeque.front() << endl; //第一个
cout << myDeque.back() << endl; // 结尾
for(auto it: myDeque)
	cout << it << endl;

增加：

myDeque.insert(myDeque.begin(), 333); //在指定位置插入元素 
// 支持双端，所以下列是push和front、back的组合
push_back() //在队列的尾部插入元素。
push_front() //在队列的头部插入元素。
//  append_range(C++23)	添加元素的范围到末尾 

修改：

// 通过访问方式修改

删除：

// 支持双端，所以下列是pop和front、back的组合
pop_back() //删除队列尾部的元素。
pop_front() //删除队列头部的元素。
myDeque.erase(myDeque.begin()+2); //在指定位置删除元素 
clear() //清空队列中的所有元素。

大小：

cout << myDeque.empty() << endl; // 判空
cout << myDeque.size() << endl; // 当前大小
cout << myDeque.max_size() << endl; // 最大可存数量大小

不重复集合 set

要点：

• 用比较函数 比较 (Compare) 进行排序。搜索、移除和插入拥有对数复杂度。set通常以红黑树实现。
• 不精确地说，如果两个对象相互比较不小于对方：!comp(a, b) && !comp(b, a)，那么认为它们等价。
• 自动比较会删除重复元素，并且重新排序

头文件：

#include <set>

用法：

创建：

set<int> mySet;
set<int> mySet{1, 20, 2, 10};
set<int> mySet2(mySet); // 复制
set<int> mySet2(mySet.begin(), mySet.end());

访问：

// 通过begin等迭代器访问
cout << mySet.count(2) << endl; // 输出值为2的元素数量，set只有1，0，因为不允许重复

增加：

修改：

// 不能通过访问方式修改
mySet.insert(mySet.begin(), 111); // 通过insert插入会自动排序

删除：

mySet.erase(mySet.begin()); // 擦除指定位置元素
clear(); // 清空

大小：

cout << mySet.empty() << endl; // 判空
cout << mySet.size() << endl; // 当前大小
cout << mySet.max_size() << endl; // 最大可存数量大小

映射 map

要点：

• 一种有序关联容器，具有唯一键的键值对。键之间以比较函数排序。搜索、移除和插入对数复杂度。map通常实现为红黑树
• 比较后会自动以key重新排序，默认从大到小

头文件：

#include <map>

用法：

创建：

// 创建空的自己初始化
map<std::string, int> myMap;
myMap["key2"] = 2;
myMap["key3"] = 3;
myMap["key1"] = 1;
// 带数据初始化
map<std::string, int> myMap
{
	{"key2", 2},
	{"key3", 3},
	{"key1", 1}
};

访问：

// 通过key访问数，注意符号，字符串双引号
cout << myMap["key2"] << endl;
cout << myMap.at("key1") << endl;
cout << myMap.begin()->first << endl; // 通过迭代器配合first second 分别访问key和值
cout << myMap.begin()->second << endl;
//遍历 需要使用->操作符访问对应位置元素
for (auto it = myMap.begin(); it != myMap.end(); ++it)
	cout << it->first << ", " << it->second << '\n';

增加：

myMap["key4"] = 400; // 通过操作符[]命名新的key和值 at函数不行
myMap.insert({"key5", 500}); // 通过insert方式新增
// insert_range(C++23) 插入一个元素范围 
// insert_or_assign(C++17) 插入元素，或若键已存在则赋值给当前元素 

修改：

// 通过访问方式修改
// 注意 通过迭代器修改时 不能修改first 即key
// merge(C++17)	从另一容器合并节点 

删除：

myMap.erase(myMap.begin()); // 擦除指定位置键值对
clear(); // 清空所有键值对

大小：

cout << myMap.empty() << endl; // 判空
cout << myMap.size() << endl; // 当前大小
cout << myMap.max_size() << endl; // 最大可存数量大小