数据结构、STL

排序

直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、基数排序、外部排序
算法稳定性：稳定的：关键字相同的元素在排序后相对位置不变
不稳定：相对位置变化了就是不稳定
排序算法：内部排序和外部排序
内部排序：数据都在内存中（主要管制时间、空间复杂度）
外部排序：数据太多，无法全部放入内存（除时间、空间复杂度还需关注磁盘读写次数）

直接插入排序

希尔排序

简单选择排序


堆排序

冒泡排序

快速排序

归并排序

基数排序
将关键字的三位分为个、十、百三位，第一趟先按照个位参考分配

查找

顺序查找、折半查找、分块查找、二叉排序树、平衡二叉树、散列查找
顺序查找

折半查找



分块查找

二叉排序树

平衡二叉树

散列查找

B树、B+树、红黑树、深度优先遍历、广度优先遍历、前序、中序、后序遍历、BFS和Dijkstra和Floyd算法最短路径

红黑树
BST：二叉查找树

B树



B+树

叶子节点表示47 48 50 56这四个，而不是这四个分开的单独一个一个
也就是说一定要走到叶子节点的部分

B树和B+树的区别：

1.B树n哥关键字对应n+1个分叉，B+树n个关键字对应n个分叉
2.B树（m阶）根节点的关键字树n范围[1,m-1]，其他节点关键字字数n在[(m/2)(向上取整)-1,m-1]。B+树根节点关键字数n在[1,m],其他节点的关键字数[m/2(向上取整)，m]
3.B+树中叶结点包含全部关键字，非叶结点中出现过的关键字也会出现在叶结点中；B书中各节点的关键字是不重复的。
4.在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。B树的结点中都包含了关键字对应的记录的存储地址。

STL

STL（Standard Template Library）是 C++ 标准库的重要组成部分，提供了一系列通用容器、算法和迭代器。STL 中的容器可以分为三大类：顺序容器、关联容器和无序关联容器。下面将详细介绍每种容器，包括它们的底层数据结构、是否支持随机存取、查找和删除的复杂度、基本用法声明，以及它们的优缺点。

1. 顺序容器（Sequence Containers）

顺序容器存储元素的顺序和插入顺序保持一致，支持按序号访问。常见的顺序容器包括：

1.1 std::vector

• 底层数据结构：动态数组（支持自动扩展的连续内存块）

• 是否支持随机存取：支持，时间复杂度 O(1)

• 查找和删除的复杂度：

  • 插入/删除尾部：O(1)（均摊时间复杂度）
  • 插入/删除中间：O(n)
  • 查找：O(n)

• 用法声明：

  std::vector<int> vec;
  vec.push_back(10);  // 插入元素
  vec.pop_back();     // 删除尾部元素
  int val = vec[0];   // 随机存取
  

• 优点：

  • 支持快速的随机存取（O(1)）。
  • 内存是连续分配的，适合频繁的尾部插入和访问。

• 缺点：

  • 当容量不足时，需要扩展容量，这时涉及重新分配和拷贝元素，开销较大。
  • 在中间插入和删除元素效率较低（O(n)）。

1.2 std::deque

• 底层数据结构：双端队列（由多个连续内存块构成，类似分段的数组）

• 是否支持随机存取：支持，时间复杂度 O(1)

• 查找和删除的复杂度：

  • 插入/删除两端：O(1)
  • 插入/删除中间：O(n)
  • 查找：O(n)

• 用法声明：

  std::deque<int> deq;
  deq.push_front(10);  // 在前端插入
  deq.push_back(20);   // 在尾部插入
  int val = deq[1];    // 随机存取
  

• 优点：

  • 支持两端的高效插入和删除（O(1)）。
  • 支持随机存取，适合频繁的两端操作。

• 缺点：

  • 随机存取稍慢于 vector，因为内存不是连续的。
  • 中间插入和删除操作效率较低（O(n)）。

1.3 std::list

• 底层数据结构：双向链表

• 是否支持随机存取：不支持

• 查找和删除的复杂度：

  • 插入/删除两端：O(1)
  • 插入/删除中间：O(1)
  • 查找：O(n)

• 用法声明：

  std::list<int> lst;
  lst.push_front(10);  // 在前端插入
  lst.push_back(20);   // 在尾部插入
  lst.pop_front();     // 删除前端
  

• 优点：

  • 双向链表，适合频繁的插入和删除操作。
  • 插入和删除操作只需调整指针，效率高。

• 缺点：

  • 不支持随机存取。
  • 查找某个元素时效率低（O(n)）。

1.4 std::forward_list

• 底层数据结构：单向链表

• 是否支持随机存取：不支持

• 查找和删除的复杂度：

  • 插入/删除头部：O(1)
  • 插入/删除中间：O(1)（需通过迭代器找到位置）
  • 查找：O(n)

• 用法声明：

  std::forward_list<int> flist;
  flist.push_front(10);  // 插入到前端
  flist.pop_front();     // 删除前端
  

• 优点：

  • 单向链表结构，内存占用较少。
  • 适合简单的前端插入和删除操作。

• 缺点：

  • 不支持随机存取。
  • 只能前向遍历，不支持双向遍历。

2. 关联容器（Associative Containers）

关联容器通过键值对存储数据，基于平衡树（通常为红黑树）。常见的关联容器包括：

2.1 std::set

• 底层数据结构：红黑树（平衡二叉搜索树）

• 是否支持随机存取：不支持

• 查找和删除的复杂度：

  • 插入/删除：O(log n)
  • 查找：O(log n)

• 用法声明：

  std::set<int> s;
  s.insert(10);  // 插入元素
  s.erase(10);   // 删除元素
  bool found = s.find(10) != s.end();  // 查找元素
  

• 优点：

  • 集合中的元素自动排序。
  • 支持快速的查找、插入和删除操作（O(log n)）。

• 缺点：

  • 不支持随机存取。
  • 插入和删除操作相对 unordered_set 较慢。

2.2 std::map

• 底层数据结构：红黑树

• 是否支持随机存取：不支持

• 查找和删除的复杂度：

  • 插入/删除：O(log n)
  • 查找：O(log n)

• 用法声明：

  std::map<int, std::string> m;
  m[1] = "one";  // 插入键值对
  m.erase(1);    // 删除键值对
  auto it = m.find(1);  // 查找键
  

• 优点：

  • 键值对按键自动排序。
  • 支持高效的查找、插入和删除操作（O(log n)）。

• 缺点：

  • 不支持随机存取。
  • 相比 unordered_map，操作速度较慢。

2.3 std::multiset

• 底层数据结构：红黑树

• 是否支持随机存取：不支持

• 查找和删除的复杂度：

  • 插入/删除：O(log n)
  • 查找：O(log n)

• 用法声明：

  std::multiset<int> ms;
  ms.insert(10);  // 插入元素
  ms.erase(10);   // 删除元素
  

• 优点：

  • 允许元素重复，自动排序。
  • 高效的插入、删除和查找操作。

• 缺点：

  • 不支持随机存取。
  • 相较于 set，查找特定值时可能需要遍历多个相同元素。

2.4 std::multimap

• 底层数据结构：红黑树

• 是否支持随机存取：不支持

• 查找和删除的复杂度：

  • 插入/删除：O(log n)
  • 查找：O(log n)

• 用法声明：

  std::multimap<int, std::string> mm;
  mm.insert({1, "one"});  // 插入键值对
  mm.erase(1);            // 删除键值对
  

• 优点：

  • 允许重复键，自动排序。
  • 支持高效的查找、插入和删除操作。

• 缺点：

  • 不支持随机存取。
  • 插入和删除效率相较于 map 略低。

3. 无序关联容器（Unordered Associative Containers）

无序关联容器基于哈希表实现，常见的无序容器包括：

3.1 std::unordered_set

• 底层数据结构：哈希表

• 是否支持随机存取：不支持

• 查找和删除的复杂度：

  • 插入/删除：O(1)（平均）
  • 查找：O(1)（平均）

• **用法

声明**：

std::unordered_set<int> us;
us.insert(10);  // 插入元素
us.erase(10);   // 删除元素
bool found = us.find(10) != us.end();  // 查找元素

• 优点：

  • 插入、查找和删除操作的平均时间复杂度是 O(1)。
  • 无序存储，效率高。

• 缺点：

  • 元素无序存储，无法进行有序遍历。
  • 最坏情况下，时间复杂度可能退化到 O(n)。

3.2 std::unordered_map

• 底层数据结构：哈希表

• 是否支持随机存取：不支持

• 查找和删除的复杂度：

  • 插入/删除：O(1)（平均）
  • 查找：O(1)（平均）

• 用法声明：

  std::unordered_map<int, std::string> um;
  um[1] = "one";  // 插入键值对
  um.erase(1);    // 删除键值对
  auto it = um.find(1);  // 查找键
  

• 优点：

  • 插入、查找和删除操作的平均时间复杂度是 O(1)。
  • 无序存储，效率高。

• 缺点：

  • 元素无序存储，无法进行有序遍历。
  • 最坏情况下，时间复杂度可能退化到 O(n)。

3.3 std::unordered_multiset

• 底层数据结构：哈希表

• 是否支持随机存取：不支持

• 查找和删除的复杂度：

  • 插入/删除：O(1)（平均）
  • 查找：O(1)（平均）

• 用法声明：

  std::unordered_multiset<int> ums;
  ums.insert(10);  // 插入元素
  ums.erase(10);   // 删除元素
  

• 优点：

  • 允许重复元素，插入、删除和查找的平均时间复杂度为 O(1)。

• 缺点：

  • 元素无序存储，无法有序遍历。
  • 最坏情况下，时间复杂度退化到 O(n)。

3.4 std::unordered_multimap

• 底层数据结构：哈希表

• 是否支持随机存取：不支持

• 查找和删除的复杂度：

  • 插入/删除：O(1)（平均）
  • 查找：O(1)（平均）

• 用法声明：

  std::unordered_multimap<int, std::string> umm;
  umm.insert({1, "one"});  // 插入键值对
  umm.erase(1);            // 删除键值对
  

• 优点：

  • 允许重复键，插入、查找和删除的平均时间复杂度为 O(1)。

• 缺点：

  • 元素无序存储，无法有序遍历。
  • 最坏情况下，时间复杂度退化到 O(n)。