文章目录
Day9 数据结构学习笔记（2025.04.01）
一、C++基础快速回顾
- 内存模型
- 栈（stack）与堆（heap）分配
- 指针与引用（左值引用、右值引用、const 引用）
- 类型系统
- 内置类型与自定义类型
- 构造与析构（RAII）
- 拷贝与赋值（深拷贝/浅拷贝，共享/独占语义）
- 移动语义（C++11）
- 操作符重载
- 继承与多态（虚函数、RTTI）
- 模板
- 泛型编程基础
- 模板函数与模板类
二、STL（标准模板库）
STL由以下五个核心部分组成：
- 容器（Containers）
- 存储和管理数据结构（如数组、链表、哈希表、树等）
- 常见限制：不能使用引用类型或函数作为元素
- 迭代器（Iterators）
- 提供统一方式访问容器元素
- 本质行为类似指针（重载
*,->,++,--等）
- 算法（Algorithms）
- 提供常见操作如排序、查找、复制、删除等
- 与容器无关，仅依赖迭代器
- 函数对象与适配器
- 如
std::less，可定制算法行为
- 如
- 工具类与API封装
- 如智能指针、时间、线程、文件系统等
三、常见容器及其对应的数据结构
| 容器 | 数据结构 | 特点 |
|---|---|---|
std::array |
固定大小数组 | 编译期大小，栈分配 |
std::vector |
动态数组 | 支持随机访问，自动扩容 |
std::forward_list |
单向链表 | 内存使用少，不能反向遍历 |
std::list |
双向链表 | 可双向遍历，插入删除效率高 |
std::set/map |
红黑树（有序） | 元素有序，插入删除O(logn) |
std::unordered_set/map |
哈希表（无序） | 查询效率高，O(1)平均复杂度 |
std::stack |
栈（适配器） | LIFO，默认基于deque实现 |
std::queue |
队列（适配器） | FIFO，默认基于deque实现 |
std::priority_queue |
堆（适配器） | 默认大顶堆 |
std::deque |
双端队列 | 头尾高效插入删除 |
std::tuple / std::pair |
异构数据结构 | 用于存储不同类型的多个值 |
四、容器操作演示
1. 基本容器使用
std::array<int, 10> arr = {}; // 固定数组
std::vector<int> vec; // 动态数组
std::forward_list<int> flist; // 单向链表
std::list<int> dlist; // 双向链表
std::set<int> s; // 红黑树（有序）
std::unordered_set<int> uset; // 哈希集合（无序）
std::map<int, std::string> m; // 红黑树（键值对）
std::unordered_map<int, std::string> umap; // 哈希键值对
std::stack<int> st; // 栈（基于 deque）
std::queue<int> q; // 队列（基于 deque）
std::deque<int> dq; // 双端队列
2. 异构类型容器
std::tuple<int, double, float> t;
std::pair<int, std::string> p;
五、迭代器详解
特点
- 类似指针，可使用
*取值、->访问成员、++移动 begin()：指向首元素；end()：指向末元素之后的位置- 容器变化后迭代器可能失效（如
resize()）
示例
std::vector<int> v = {1, 2, 3};
auto it = v.begin();
std::cout << *it; // 1
v.resize(100); // it 失效
it = v.begin(); // 重新获取
用户自定义结构体访问成员
struct RAE { double R, A, E; };
std::vector<RAE> raes;
raes.push_back({1.0, 2.0, 3.0});
raes.begin()->R = 100.0; // 使用 operator-> 访问
六、算法库与排序演示
STL算法特点
- 以迭代器为输入
- 解耦容器与算法实现
- 多数算法在
<algorithm>中定义
示例：排序
std::array<int, 10> arr = {9, 7, 8, 2, 5, 4, 3, 1, 2, 0};
std::sort(arr.begin(), arr.end(), std::less<int>());
// 默认升序排序，std::less<int>() 可省略
for (int i : arr) {
std::cout << i << " ";
}
C++20 ranges（了解）
- 新增
ranges::sort,views::filter,views::transform等函数式风格 - 示例：
ranges::sort(arr);（需要头文件<ranges>）
七、完整测试代码
#include <iostream>
#include <vector>
#include <array>
#include <forward_list>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>//std::sort
#include <functional>//std::less
#include <tuple>
/*
C++基础快速回顾
指针
引用（左值，右值，常量）
栈
堆
内置类型
自定义类型
1. 构造 析构 RAII
2. 拷贝 独占（深拷贝）共享（浅拷贝）
3. 移动
4. 操作符重载
5. 继承
6. 多态 RTTI
模板
查漏补缺
*/
/*
STL: standard template library
标准模板库，简称标准库
标准库包含
1. 容器，是可以放进容器的元素的集合（什么不能做容器的元素类型？引用和函数）
2. 迭代器，提供一种访问不同容器元素的统一接口，隐藏了容器组织元素的数据结构细节
3. 算法，基于迭代器实现，以统一接口操作不同容器，比如排序算法
4. 跨平台的操作系统API封装，比如文件系统，IO操作，区域化，时间，线程等
5. 通用工具和其他，比如智能指针用于帮助自动释放堆内存，同时提供独占和共享语义
*/
/*
容器实现了各种数据结构：
- 不变的数组，array
- 动态数组，vector
- 字符串，string / wstring，可看成 vector<char> / vector<wchar_t>
- 单向链表，forward_list
- 双向链表，list
- 二叉平衡搜索树（红黑树），set & map
- 哈希表，unordered_set & unordered_map
- 双端队列，deque
- 栈，stack，容器适配器，使用 deque 实现
- 队列，deque，容器适配器，使用 deque 实现
- 堆，最小/大堆，也称优先队列，priority_queue，容器适配器，使用 vector 实现
- 异构体，tuple
常见数据结构的复杂度：
1. 数组 索引 O(1) 插入删除 O(n)
2. 链表 索引 O(n) 插入删除 O(1)
3. 红黑树（有序） 索引 O(logn) 插入删除 O(logn)
4. 哈希（无序） 索引 O(1) 插入删除 O(n)
按所需的数据结构选择恰当的容器
*/
/*
迭代器
一种设计模式，用于隐藏容器内元素的组织方式，以一种统一的接口来访问
行为类似指针，重载了 operator-> ，operator++ 等
注意：之前赋值的迭代器在容器发生改变后可能会失效，指向非法内存，需要重新取迭代器
*/
static void iterator_demo()
{
std::vector<int> v{ 1, 2, 3 };
auto iter = v.begin(); // *iter == 1 == v[0]
iter++; // *iter == 2 == v[1]
iter = v.end(); // 指向最后一个元素的下一个位置，禁止对其使用operator*解引用！！！
iter--; // *iter == 3 == v[2]
// 看看v的第一个元素的地址在哪里，那是一个堆地址
std::cout << v.data() << ' ';
// 或者
// 由于 cout 无法打印迭代器，因为迭代器没实现operator<<
// 迂回一下，对迭代器解引用再取地址，可得到普通指针int*
int* p = &(*v.begin());
std::cout << p << ' ';
// 或者
// 回想下数组名其实就是个指针，那迭代器表现得像指针，是不是也可以看成数组名？
// 的确，可以使用下标作用到迭代器上（只有数组的迭代器有这个特权）
// 注意[]的优先级比&高，先调用[]然后&
std::cout << &v.begin()[0] << ' '; // 不放心就加括号 &(v.begin()[0])
// 或者
// v本身就是个数组，可以直接取下标
std::cout << &v[0] << std::endl;
// 把v的尺寸改为100个元素，势必引起迭代器失效
// 需要在堆上重新找容纳100个int的空间，使用new分配
// 然后把当前这3个int拷过去
// 最后释放这3个的int的空间（形成内存碎片），不可以再访问，即不可以再操作原来的迭代器
// 前3个是1，2，3，剩下全部填0
v.resize(100);
// 再看看第一个元素在哪，和上面已经不一样了
std::cout << v.data() << std::endl;
// 缩小改为3个元素，没有引发迭代器失效（出于性能考虑）
// 后面97个元素的空间还给操作系统了（形成内存碎片），不可以再访问
// 但是，不要管缩小会不会引起迭代器失效，只要修改了容器，就总是重新取迭代器
v.resize(3);
std::cout << v.data() << std::endl;
struct RAE
{
double R;
double A;
double E;
};
std::vector<RAE> raes;
raes.push_back({ 1.0, 2.0, 3.0 });
// 由于重载了operator-> 迭代器可以像使用指针一样访问成员变量
raes.begin()->R = 100.0;
}
static std::ostream& operator<<(std::ostream& os, const std::vector<int>& v)
{
// 使用迭代器遍历容器，其实编译器看到 for (int i : v) 就是转成以下代码
for (auto iter = v.cbegin(); iter != v.cend(); ++iter)
{
os << *iter << ' ';
}
return os;
}
int main()
{
//不变的数组
// 修正：避免越界访问
std::array<int, 10> arr1 = {}; // 初始化为全0
arr1[0] = 1; // 合法索引 0~9
arr1[9] = 1; // 合法
// arr1[10] = 1; // 错误：注释掉越界访问 保持和原生C语言一样的语义，不做任何检查
// arr1.at(10) = 1; // 错误：注释掉越界访问 做检查，运行时报错
//动态数组
std::vector<int> vector;
vector.push_back(1);
//单向链表
std::forward_list<int> forwardList;
forwardList.push_front(1);
//双向链表
std::list<int> list;
list.push_back(1);
list.push_front(1);
//平衡树,(有序)单个元素
std::set<int> set;//默认从小到大排序
set.insert(1);
//平衡树,(默认有序) 键值对 ，按照键的大小来排序
std::map<int, std::string> map;
map[0] = "zhangsan";
map[1] = "lisi";
//无序关联式容器
//哈西（无序）
std::unordered_set<int> unorder_set;
unorder_set.insert(1);
//哈希 （无序）键值对
std::unordered_map<int, std::string> unordered_map;
unordered_map[0] = "abc";
unordered_map[1] = "def";
//栈（使用双端队列实现）
std::stack<int> stack;
/*入栈*/
stack.push(1);
/*出栈*/
int top = stack.top();
stack.pop();
//队列
std::queue<int> queue;
queue.push(1);
queue.front();
queue.pop();
//双端队列
std::deque<int> deque;
deque.push_back(1);
deque.push_front(2);
deque.pop_back();
deque.pop_front();
//异构 ： 支持不同类型
struct Tuple {
int a;
double b;
float c;
};
std::tuple<int, double, float> tuple;//元组
std::get<0>(tuple) = 1;
//异构之std::pair,只存放两个值，是map unorder_map的存储单元
//键值对
std::pair<int, double> pair;
//迭代器 设计模式
//目的：隐藏容器中元素的组织形式，用提供统一的接口来访问
//最常见的方法：eg:获取第一个元素begin ,访问下一个元素next
//迭代器是行为指针的类型
auto firstElement = vector.begin();
//访问vector容器中元素的几种方式
int a = *firstElement;
int b = vector[0];
int c = vector.at(0);
firstElement++;
auto firstElement2 = vector.begin();
firstElement2++;
/*
算法
在C++20之前，算法库一般接收迭代器
使用 begin 获取起始迭代器，指向第一个元素
end 获取末迭代器，指向最后一个元素的下一个位置
函数式编程是C++20的一个重要发展方向
C++20起，引入了 ranges 库，为算法提供了不同的访问方式
C++23继续完善 ranges 库
C++20及之后的内容，权当了解最新的发展，可以完全不管
*/
//算法
/*由于迭代器隐藏了容器的具体数据结构，算法进而使用迭代器，从而使用统一的方式，操作不同的容器*/
std::array<int, 10> arrayRandom= { 9,7 ,8 ,2 ,5 ,4 ,3 ,1 ,2 ,0};
//arrayRandom.end() 是指向容器中最后一个元素的下一个位置
// 排序（升序，std::less<int>() 是默认行为，可省略）
std::sort(arrayRandom.begin(), arrayRandom.end(), std::less<int>());
// 打印排序后的元素
for (auto i : arrayRandom) {
std::cout << i << " "; // 输出每个元素，用空格分隔
}
std::cout << std::endl; // 换行
return 0;
}
八、总结
- STL 提供统一的数据结构与算法接口，核心三件套是容器、迭代器、算法
- 学会根据实际使用场景（性能、顺序、插入/删除频率）选择合适容器
- 操作容器时，要注意迭代器失效问题
- 算法库配合迭代器提供高效、可复用的操作方式