序列式容器

vector

概述

vector 是 C++ 标准库中的动态数组，可以自动调整大小，支持随机访问。它存储在连续的内存空间中，类似于普通数组，但提供了更灵活的操作。

头文件

#include <vector>

声明与初始化

std::vector<int> v1;              // 空 vector
std::vector<int> v2(5, 10);       // 5 个元素，每个初始化为 10
std::vector<int> v3 = {1, 2, 3};  // 列表初始化
std::vector<int> v4(v3);          // 拷贝构造

常用操作

1. 添加元素

   v1.push_back(10);       // 在末尾添加元素 10
   v1.emplace_back(20);    // 高效地在末尾构造元素 20
   

2. 访问元素

   int a = v1[0];          // 通过下标访问（不检查越界）
   int b = v1.at(1);       // 通过 at() 访问（检查越界）
   int c = v1.front();     // 访问第一个元素
   int d = v1.back();      // 访问最后一个元素
   

3. 删除元素

   v1.pop_back();          // 删除最后一个元素
   v1.erase(v1.begin());   // 删除指定位置的元素
   v1.clear();             // 清空所有元素
   

4. 容量操作

   int size = v1.size();       // 获取当前元素数量
   bool empty = v1.empty();    // 判断是否为空
   v1.resize(10);              // 调整大小为 10
   int cap = v1.capacity();    // 获取当前容量
   

5. 迭代器

   for (auto it = v1.begin(); it != v1.end(); ++it) {
       std::cout << *it << " ";
   }
   

特点

• 动态扩容：当空间不足时，自动分配更大的内存（通常是原容量的 2 倍）。
• 随机访问：支持 O(1) 时间复杂度的随机访问。
• 尾部操作高效：push_back 和 pop_back 是 O(1) 时间复杂度。
• 中间插入/删除较慢：需要移动后续元素，时间复杂度为 O(n)。

适用场景

• 需要频繁随机访问元素的场景。
• 尾部插入和删除操作较多的场景。
• 不需要频繁在中间插入或删除元素的场景。

---

deque

概述

deque（双端队列）是C++ STL中的一种序列容器，支持在头部和尾部高效地插入和删除元素。与vector类似，但deque在两端操作的时间复杂度为O(1)，而vector仅在尾部高效。

特点

1. 双端操作：支持push_front、pop_front、push_back、pop_back。
2. 随机访问：支持通过下标（[]）或at()访问元素，时间复杂度为O(1)。
3. 动态扩容：内部由多个分段连续空间组成，扩容时无需移动所有元素。
4. 不保证连续存储：与vector不同，deque的物理存储可能是非连续的。

常用操作

• 初始化

  #include <deque>
  std::deque<int> dq1;                  // 空deque
  std::deque<int> dq2(5, 10);           // 5个元素，每个值为10
  std::deque<int> dq3(dq2.begin(), dq2.end()); // 通过迭代器初始化
  

• 插入/删除

  dq.push_front(1);      // 头部插入1
  dq.push_back(2);       // 尾部插入2
  dq.pop_front();        // 删除头部元素
  dq.pop_back();         // 删除尾部元素
  dq.insert(dq.begin() + 1, 3); // 在指定位置插入3
  dq.erase(dq.begin());  // 删除指定位置元素
  

• 访问元素

  int x = dq[0];         // 通过下标访问
  int y = dq.at(1);      // 安全访问，越界抛出异常
  int front = dq.front(); // 头部元素
  int back = dq.back();   // 尾部元素
  

• 容量操作

  bool isEmpty = dq.empty(); // 判断是否为空
  size_t size = dq.size();   // 返回元素数量
  dq.resize(10);             // 调整大小为10
  

适用场景

• 需要频繁在头部和尾部插入/删除元素时。
• 需要随机访问但不需要连续存储时（如实现滑动窗口算法）。

注意事项

• 中间插入/删除效率较低（时间复杂度O(n)）。
• 迭代器可能因扩容而失效（与vector类似）。

---

list

list 是 C++ STL 中的双向链表容器，支持高效的元素插入和删除操作。

特点

• 双向链表结构：每个元素包含指向前后元素的指针。
• 动态大小：无需预先指定大小，可动态增长或缩小。
• 非连续存储：元素在内存中非连续存储，不支持随机访问（如 operator[]）。
• 高效插入/删除：在任意位置插入或删除元素的时间复杂度为 O(1)。

常用操作

1. 初始化

   #include <list>
   std::list<int> l1;                // 空列表
   std::list<int> l2(5, 10);         // 5 个元素，每个值为 10
   std::list<int> l3 = {1, 2, 3};   // 初始化列表
   

2. 插入元素

   • push_back(val)：在末尾插入。
   • push_front(val)：在头部插入。
   • insert(iterator, val)：在指定迭代器位置插入。

   l1.push_back(10);       // 尾部插入 10
   l1.push_front(5);       // 头部插入 5
   auto it = l1.begin();
   l1.insert(++it, 7);     // 在第二个位置插入 7
   

3. 删除元素

   • pop_back()：删除末尾元素。
   • pop_front()：删除头部元素。
   • erase(iterator)：删除指定迭代器位置的元素。
   • remove(val)：删除所有值为 val 的元素。

   l1.pop_back();          // 删除末尾元素
   l1.erase(l1.begin());   // 删除头部元素
   l1.remove(10);          // 删除所有值为 10 的元素
   

4. 访问元素

   • front()：返回第一个元素。
   • back()：返回最后一个元素。
   • 需用迭代器遍历（无随机访问）：

     for (auto it = l1.begin(); it != l1.end(); ++it) {
         std::cout << *it << " ";
     }
     

5. 其他操作

   • size()：返回元素数量。
   • sort()：排序（默认升序）。
   • reverse()：反转链表。
   • merge(list)：合并两个有序链表。

   l1.sort();              // 升序排序
   l1.reverse();           // 反转链表
   l1.merge(l2);           // 合并 l2 到 l1（需两者有序）
   

注意事项

• 迭代器失效：只有被删除元素的迭代器会失效，其他迭代器不受影响。
• 性能：频繁插入/删除时性能优于 vector，但查找和随机访问较慢。

示例代码

#include <iostream>
#include <list>

int main() {
    std::list<int> nums = {3, 1, 4};
    nums.push_back(2);           // 3, 1, 4, 2
    nums.sort();                 // 1, 2, 3, 4
    for (int n : nums) {
        std::cout << n << " ";  // 输出: 1 2 3 4
    }
    return 0;
}

---

forward_list

定义
forward_list 是 C++ 标准库中的单向链表容器，定义在 <forward_list> 头文件中。它仅支持单向遍历（从头到尾），每个节点只存储下一个节点的指针，因此比 list 更节省内存。

特点

1. 单向链表：仅支持从前向后遍历，不支持反向遍历或随机访问。
2. 高效插入/删除：在已知位置插入或删除元素的时间复杂度为 O(1)。
3. 无 size() 成员函数：为了节省内存，不直接提供 size() 方法，需通过 distance() 计算长度。
4. 内存紧凑：比 list 更节省空间（每个节点少一个指针）。

常用操作

• 插入
  • push_front(val)：在链表头部插入元素。
  • insert_after(pos, val)：在指定位置后插入元素。
• 删除
  • pop_front()：删除头部元素。
  • erase_after(pos)：删除指定位置后的元素。
• 访问
  • front()：访问第一个元素（不提供 back()）。
• 其他
  • before_begin()：返回指向第一个元素前位置的迭代器（用于插入到头部）。

示例代码

#include <forward_list>
#include <iostream>

int main() {
    std::forward_list<int> flist = {2, 3};
    flist.push_front(1);                   // 头部插入：1 -> 2 -> 3
    auto it = flist.insert_after(flist.begin(), 99); // 1 -> 99 -> 2 -> 3
    flist.erase_after(it);                 // 删除 2，结果：1 -> 99 -> 3

    for (int x : flist) {
        std::cout << x << " ";            // 输出：1 99 3
    }
}

适用场景

• 需要频繁在头部或已知位置插入/删除元素。
• 对内存占用敏感且不需要双向遍历的场景。

注意

• 不支持 size()，计算长度需遍历链表（std::distance(flist.begin(), flist.end())）。
• 迭代器失效规则与 list 类似，删除操作仅影响被删除元素的迭代器。

---

array

C++中的array是固定大小的顺序容器，包含在<array>头文件中。它在栈上分配内存，大小在编译时确定。

基本特性

• 固定大小，创建后不能改变
• 连续内存存储
• 支持随机访问迭代器
• 知道自己的大小（通过size()成员函数）

声明和初始化

#include <array>

// 声明一个包含5个int的array
std::array<int, 5> arr;

// 初始化方式
std::array<int, 3> arr1 = {1, 2, 3};  // 初始化列表
std::array<int, 3> arr2 {4, 5, 6};     // 统一初始化(C++11)

常用操作

1. 访问元素：

arr[0] = 10;          // 不检查边界
arr.at(1) = 20;       // 检查边界，越界抛出异常
int front = arr.front();  // 第一个元素
int back = arr.back();    // 最后一个元素

2. 容量相关：

bool empty = arr.empty();  // 是否为空
size_t size = arr.size();  // 元素数量
size_t max_size = arr.max_size();  // 最大可能大小(通常等于size)

3. 填充：

arr.fill(42);  // 将所有元素设置为42

4. 交换：

std::array<int, 3> arr3 = {7, 8, 9};
arr1.swap(arr3);  // 交换两个array的内容

迭代器支持

for(auto it = arr.begin(); it != arr.end(); ++it) {
    // 使用迭代器访问
}

for(auto& elem : arr) {
    // 范围for循环(C++11)
}

与C风格数组比较

• 更安全（知道自己的大小，边界检查）
• 可以作为函数参数和返回值
• 支持STL算法
• 可以使用成员函数

注意事项

• 大小必须是编译时常量
• 不能动态调整大小
• 性能与C风格数组相当

---

关联式容器

set

概述

set 是 C++ STL 中的关联容器，用于存储唯一的元素，并按照升序（默认）自动排序。基于红黑树实现，插入、删除和查找操作的时间复杂度均为 O(log n)。

特点

1. 唯一性：不允许重复元素。
2. 自动排序：默认按升序排列，可通过自定义比较器修改排序规则。
3. 不可修改元素：元素是 const，不能直接修改，需先删除再插入新值。

常用操作

#include <set>
using namespace std;

set<int> s;

// 插入元素
s.insert(10);
s.insert(20);

// 删除元素
s.erase(10); // 按值删除
s.erase(s.begin()); // 按迭代器删除

// 查找元素
auto it = s.find(20);
if (it != s.end()) {
    // 元素存在
}

// 遍历
for (auto& num : s) {
    cout << num << endl;
}

// 其他操作
s.size();   // 元素个数
s.empty();  // 判断是否为空
s.clear();  // 清空集合

自定义排序

struct Compare {
    bool operator()(int a, int b) const {
        return a > b; // 降序排列
    }
};

set<int, Compare> s;
s.insert(10);
s.insert(20); // 顺序为 20, 10

注意事项

• 插入重复元素时会被忽略。
• 迭代器失效：仅删除当前元素时迭代器不会失效，但删除其他元素可能导致未定义行为。

---

multiset

概述

multiset 是 C++ STL 中的一个关联容器，允许存储多个相同值的元素，并按特定顺序（默认升序）自动排序。它基于红黑树实现，提供高效的插入、删除和查找操作。

头文件

#include <set>

声明与初始化

std::multiset<int> ms; // 空 multiset
std::multiset<int> ms = {1, 2, 2, 3}; // 初始化含重复元素
std::multiset<int, std::greater<int>> msDesc; // 降序排列

常用操作

1. 插入元素

   ms.insert(4); // 插入单个元素
   ms.insert({4, 5, 5}); // 插入多个元素
   

2. 删除元素

   ms.erase(2); // 删除所有值为 2 的元素
   auto it = ms.find(3);
   if (it != ms.end()) ms.erase(it); // 删除迭代器指向的元素
   

3. 查找元素

   auto it = ms.find(3); // 返回第一个匹配的迭代器
   size_t count = ms.count(5); // 返回值为 5 的元素个数
   

4. 遍历元素

   for (auto& num : ms) {
       std::cout << num << " ";
   }
   

5. 其他操作

   bool empty = ms.empty(); // 判断是否为空
   size_t size = ms.size(); // 返回元素数量
   ms.clear(); // 清空所有元素
   

特性

• 允许重复值：与 set 不同，multiset 可以存储多个相同的值。
• 自动排序：元素始终按指定排序规则（默认 std::less）维护顺序。
• 时间复杂度：插入、删除、查找均为 O(log n)。

示例代码

#include <iostream>
#include <set>
int main() {
    std::multiset<int> ms = {1, 3, 3, 2};
    ms.insert(2);
    for (int num : ms) {
        std::cout << num << " "; // 输出: 1 2 2 3 3
    }
    return 0;
}

注意事项

• 迭代器或引用在插入/删除后可能失效（除被删除元素的迭代器）。
• 自定义排序规则需满足严格弱序（如 std::greater）。

---

map

map 是 C++ STL 中的关联容器，用于存储键值对（key-value），并根据键（key）自动排序。底层通常由红黑树实现，保证元素有序且查找高效。

特点

• 唯一键：每个键只能出现一次。
• 自动排序：默认按键升序排列（可通过比较函数自定义）。
• 高效查找：基于红黑树，查找、插入、删除操作的时间复杂度为 O(log n)。

基本用法

#include <map>
#include <string>

std::map<int, std::string> myMap;

常用操作

1. 插入元素

   • 使用 insert 或 emplace：

     myMap.insert({1, "Apple"});
     myMap.emplace(2, "Banana");
     

   • 使用 [] 操作符（若键存在则覆盖）：

     myMap[3] = "Cherry";
     

2. 访问元素

   • 通过键访问值（若键不存在会插入默认值）：

     std::string fruit = myMap[1]; // "Apple"
     

   • 使用 at（键不存在时抛出异常）：

     fruit = myMap.at(2); // "Banana"
     

3. 查找元素

   • 使用 find（返回迭代器，未找到时指向 end()）：

     auto it = myMap.find(3);
     if (it != myMap.end()) {
         std::cout << it->second; // "Cherry"
     }
     

4. 删除元素

   • 通过迭代器或键：

     myMap.erase(1); // 删除键为1的元素
     myMap.erase(it); // 删除迭代器指向的元素
     

5. 遍历

   • 使用迭代器（按键顺序遍历）：

     for (const auto& pair : myMap) {
         std::cout << pair.first << ": " << pair.second << std::endl;
     }
     

自定义排序

通过传递比较函数（如降序排列）：

std::map<int, std::string, std::greater<int>> descMap;
descMap[1] = "A";
descMap[2] = "B"; // 顺序: 2->B, 1->A

注意事项

• 键的类型必须支持 < 操作符或提供自定义比较函数。
• 插入/删除操作可能使迭代器失效（但指向其他元素的迭代器仍有效）。

---

multimap

概述

multimap 是 C++ STL 中的关联容器，允许存储键值对（key-value），且支持重复的键。基于红黑树实现，元素按键自动排序。

特点

• 允许重复键：同一个键可以关联多个值。
• 自动排序：默认按键升序排列（可通过比较函数自定义）。
• 双向迭代器：支持正向和反向遍历。

头文件

#include <map>

声明与初始化

multimap<KeyType, ValueType> mm; // 空 multimap
multimap<KeyType, ValueType> mm = {{key1, val1}, {key2, val2}}; // 初始化列表

常用操作

1. 插入元素

   mm.insert({key, value}); // 插入单个键值对
   mm.emplace(key, value);  // 原地构造插入（C++11）
   

2. 查找元素

   auto range = mm.equal_range(key); // 返回匹配键的迭代器范围 [first, last)
   auto it = mm.find(key);           // 返回第一个匹配键的迭代器
   

3. 删除元素

   mm.erase(key);    // 删除所有匹配键的元素
   mm.erase(iter);   // 删除指定迭代器位置的元素
   

4. 遍历

   for (const auto& pair : mm) {
       cout << pair.first << " : " << pair.second << endl;
   }
   

5. 容量查询

   mm.size();     // 元素数量
   mm.empty();    // 判断是否为空
   mm.count(key); // 返回匹配键的元素数量
   

示例代码

#include <iostream>
#include <map>
using namespace std;

int main() {
    multimap<int, string> mm = {{1, "apple"}, {2, "banana"}, {1, "apricot"}};
    mm.insert({3, "cherry"});

    // 输出所有元素
    for (auto& p : mm) {
        cout << p.first << " : " << p.second << endl;
    }

    // 查找键为1的所有值
    auto range = mm.equal_range(1);
    for (auto it = range.first; it != range.second; ++it) {
        cout << "Found: " << it->second << endl;
    }
    return 0;
}

应用场景

• 需要一键多值的映射（如电话簿中同名不同号码）。
• 需保持键有序且允许重复的情况。

复杂度

• 插入/删除/查找：平均 O(log n)（红黑树特性）。

---

无序关联式容器

unordered_set

unordered_set 是 C++ 标准库中的一种无序关联容器，基于哈希表实现，用于存储唯一的元素。它提供高效的插入、删除和查找操作，平均时间复杂度为 O(1)。

特点

1. 无序存储：元素不按特定顺序存储，而是根据哈希值分布。
2. 唯一性：不允许重复元素，插入重复元素会被忽略。
3. 高效操作：插入、删除和查找操作的平均时间复杂度为 O(1)。

常用操作

1. 插入元素：

   unordered_set<int> us;
   us.insert(10); // 插入元素 10
   

2. 查找元素：

   if (us.find(10) != us.end()) {
       // 元素 10 存在
   }
   

3. 删除元素：

   us.erase(10); // 删除元素 10
   

4. 遍历元素：

   for (const auto& elem : us) {
       cout << elem << " ";
   }
   

示例代码

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    unordered_set<int> us = {1, 2, 3, 4, 5};
    us.insert(6); // 插入 6
    us.erase(3);  // 删除 3

    for (int num : us) {
        cout << num << " "; // 输出顺序不确定
    }
    return 0;
}

注意事项

1. 哈希冲突：性能依赖于哈希函数的质量，冲突过多会降低效率。
2. 内存占用：由于哈希表的实现，内存占用可能较高。
3. 无序性：不适用于需要有序遍历的场景。

---

unordered_multiset

概述

unordered_multiset 是 C++ STL 中的无序关联容器，允许存储重复的元素。基于哈希表实现，插入、删除和查找操作的平均时间复杂度为 O(1)。不保证元素的顺序。

头文件

#include <unordered_set>

声明与初始化

std::unordered_multiset<int> ums; // 空 unordered_multiset
std::unordered_multiset<int> ums = {1, 2, 2, 3}; // 初始化含重复元素

常用操作

1. 插入元素

   ums.insert(4); // 插入单个元素
   ums.insert({5, 5, 6}); // 插入多个元素
   

2. 删除元素

   ums.erase(2); // 删除所有值为 2 的元素
   auto it = ums.find(3);
   if (it != ums.end()) ums.erase(it); // 删除迭代器指向的元素
   

3. 查找元素

   auto it = ums.find(3); // 返回指向第一个匹配元素的迭代器
   size_t count = ums.count(5); // 返回值为 5 的元素个数
   

4. 遍历

   for (const auto& elem : ums) {
       std::cout << elem << " ";
   }
   

5. 容量查询

   bool isEmpty = ums.empty(); // 判断是否为空
   size_t size = ums.size(); // 返回元素数量
   

特性

• 允许重复元素：与 unordered_set 不同，可以存储多个相同值。
• 无序存储：元素顺序由哈希函数决定，遍历时顺序不确定。
• 自定义哈希与比较函数：支持通过模板参数自定义哈希函数和相等比较逻辑。

示例代码

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_multiset<int> ums = {1, 2, 2, 3};
    ums.insert(2); // 插入后包含三个 2

    std::cout << "Count of 2: " << ums.count(2) << std::endl; // 输出 3

    for (int num : ums) {
        std::cout << num << " "; // 输出顺序可能为 3 1 2 2 2
    }
    return 0;
}

---

unordered_map

概述

unordered_map 是 C++ STL 中的关联容器，基于哈希表实现，用于存储键值对（key-value）。它提供平均 O(1) 时间复杂度的插入、删除和查找操作，但不保证元素的顺序。

特点

1. 无序存储：元素顺序由哈希函数决定，不按键值排序。
2. 唯一键：每个键只能出现一次（重复插入会覆盖原有值）。
3. 高效操作：平均情况下插入、删除和查找均为 O(1) 时间复杂度。

头文件

#include <unordered_map>

声明与初始化

std::unordered_map<KeyType, ValueType> map;

// 初始化示例
std::unordered_map<std::string, int> ages = {
    {"Alice", 25},
    {"Bob", 30}
};

常用操作

1. 插入元素

   • 使用 insert 或 emplace：

     map.insert({"Charlie", 28});
     map.emplace("David", 22); // 更高效
     

   • 使用 [] 运算符（若键不存在会自动插入）：

     map["Eve"] = 31;
     

2. 访问元素

   • 使用 [] 或 at（at 会检查键是否存在，不存在时抛出异常）：

     int age = map["Alice"];    // 不存在时插入默认值
     int age = map.at("Bob");   // 不存在时抛出 std::out_of_range
     

3. 删除元素

   • 使用 erase：

     map.erase("Alice"); // 删除键为 "Alice" 的元素
     

4. 查找元素

   • 使用 find（返回迭代器，若未找到则返回 end()）：

     auto it = map.find("Bob");
     if (it != map.end()) {
         std::cout << "Found: " << it->second << std::endl;
     }
     

5. 遍历

   • 使用迭代器或范围循环：

     for (const auto& pair : map) {
         std::cout << pair.first << ": " << pair.second << std::endl;
     }
     

容量查询

• size()：返回元素数量。
• empty()：检查是否为空。
• count(key)：返回键出现的次数（0 或 1）。

哈希策略

• load_factor()：返回当前负载因子（元素数/桶数）。
• rehash(n)：调整桶的数量为至少 n。

示例代码

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> scores = {{"Math", 90}, {"Physics", 85}};
    scores.emplace("Chemistry", 88);
    scores["Biology"] = 92;

    for (const auto& subject : scores) {
        std::cout << subject.first << ": " << subject.second << std::endl;
    }

    if (scores.find("Math") != scores.end()) {
        std::cout << "Math score: " << scores["Math"] << std::endl;
    }
    return 0;
}

---

unordered_multimap

概述

unordered_multimap 是 C++ STL 中的关联容器，基于哈希表实现，允许存储键值对（key-value），且支持多个相同键的条目。与 unordered_map 不同，它不要求键的唯一性。

特点

1. 无序存储：元素顺序由哈希函数决定，不按键排序。
2. 允许重复键：同一键可对应多个值。
3. 高效查找：平均时间复杂度为 O(1)，最坏情况 O(n)。
4. 动态大小：支持插入和删除操作，自动调整容量。

基本用法

#include <unordered_map>
#include <string>

std::unordered_multimap<std::string, int> umm;

常用操作

1. 插入元素

   umm.insert({"apple", 1});
   umm.insert({"apple", 2}); // 允许重复键
   

2. 查找元素

   auto range = umm.equal_range("apple");
   for (auto it = range.first; it != range.second; ++it) {
       std::cout << it->first << ": " << it->second << std::endl;
   }
   

3. 删除元素

   umm.erase("apple"); // 删除所有键为 "apple" 的条目
   

4. 遍历容器

   for (const auto& pair : umm) {
       std::cout << pair.first << " => " << pair.second << std::endl;
   }
   

注意事项

• 哈希冲突：性能可能受哈希函数质量影响。
• 内存占用：比有序容器（如 multimap）更占内存。
• 迭代器稳定性：插入操作可能导致迭代器失效。

---

容器适配器

stack

概述

stack 是 C++ 标准库中的一种容器适配器，遵循 后进先出（LIFO） 的原则。它基于其他容器（如 deque 或 list）实现，默认使用 deque 作为底层容器。

头文件

#include <stack>

常用操作

1. push()
   将元素压入栈顶。

   stack<int> s;
   s.push(10); // 栈顶元素变为 10
   

2. pop()
   移除栈顶元素（不返回该元素）。

   s.pop(); // 移除栈顶元素
   

3. top()
   返回栈顶元素的引用（不移除）。

   int x = s.top(); // 获取栈顶元素
   

4. empty()
   检查栈是否为空，返回布尔值。

   if (s.empty()) { /* 栈为空 */ }
   

5. size()
   返回栈中元素的个数。

   int count = s.size();
   

示例代码

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);

    cout << "Top element: " << s.top() << endl; // 输出 3
    s.pop(); // 移除 3
    cout << "Top element after pop: " << s.top() << endl; // 输出 2

    return 0;
}

注意事项

• 不支持随机访问或遍历，只能操作栈顶元素。
• 底层容器可以通过模板参数指定：

  stack<int, list<int>> s; // 使用 list 作为底层容器
  

---

queue（队列）

概念
队列是一种**先进先出（FIFO）**的线性数据结构，元素从队尾（back）插入，从队头（front）移除。

特点

• 插入操作称为 push（入队）。
• 删除操作称为 pop（出队）。
• 不支持随机访问，只能操作队头和队尾元素。

头文件

#include <queue>

常用操作

方法	功能	示例
push(val)	将元素 val 插入队尾	q.push(10);
pop()	移除队头元素（无返回值）	q.pop();
front()	返回队头元素（不删除）	int x = q.front();
back()	返回队尾元素（不删除）	int y = q.back();
empty()	判断队列是否为空	if (q.empty()) {...}
size()	返回队列中元素个数	int len = q.size();

示例代码

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    q.push(1);    // 队尾插入 1
    q.push(2);    // 队尾插入 2
    cout << q.front() << endl; // 输出队头 1
    q.pop();      // 移除队头 1
    cout << q.front() << endl; // 输出新队头 2
    return 0;
}

应用场景

• 广度优先搜索（BFS）
• 任务调度（按顺序处理请求）
• 缓冲区管理（如打印队列）

注意

• 队列没有 clear() 方法，清空队列需循环调用 pop() 或重新初始化。
• 访问 front() 或 pop() 前需确保队列非空（否则未定义行为）。

---

priority_queue

概述

priority_queue 是 C++ STL 中的一种容器适配器，基于堆数据结构实现，默认情况下是一个最大堆（即队首元素总是当前优先级最高的元素）。它不提供随机访问功能，仅支持在队尾插入元素和从队首移除元素。

头文件

#include <queue>

声明与初始化

// 默认构造（最大堆）
priority_queue<int> pq1;

// 最小堆（使用 greater 比较器）
priority_queue<int, vector<int>, greater<int>> pq2;

// 使用已有数据初始化
vector<int> vec = {3, 1, 4};
priority_queue<int> pq3(vec.begin(), vec.end());

核心操作

1. 插入元素
   push() 将元素插入堆，并自动调整堆结构。

   pq1.push(10); // 插入元素 10
   

2. 访问队首元素
   top() 返回优先级最高的元素（不删除）。

   int val = pq1.top(); // 获取最大元素
   

3. 删除队首元素
   pop() 移除优先级最高的元素。

   pq1.pop(); // 删除最大元素
   

4. 其他操作

   • empty()：检查队列是否为空。
   • size()：返回队列中元素数量。

   if (pq1.empty()) cout << "队列为空";
   cout << pq1.size(); // 输出元素个数
   

自定义比较器

通过重载 operator() 或使用 lambda 表达式定义优先级规则：

struct Compare {
    bool operator()(int a, int b) {
        return a > b; // 最小堆
    }
};
priority_queue<int, vector<int>, Compare> pq4;

时间复杂度

• 插入 (push)：O(log n)
• 删除 (pop)：O(log n)
• 访问队首 (top)：O(1)

应用场景

• 需要动态获取当前最大/最小值的场景（如任务调度、Dijkstra 算法）。
• 数据流中的 Top K 问题。

---