目录前言一、stack 栈1.定义及初始化2.常用操作1empty 成员函数2pop 成员函数3push 成员函数4size 成员函数5top 成员函数二、queue 队列1. 定义及初始化2.常用操作1back 成员函数2empty 成员函数3front 成员函数4pop 成员函数5push 成员函数6size 成员函数三、priority queue 优先级队列1.定义及初始化2.常用操作1empty 成员函数2pop 成员函数3push 成员函数4size 成员函数5top 成员函数3.深入 priority queue四、 bitset 位图1.初始化方法2.常用的符号和方法1位操作符2成员函数前言本文介绍了C标准库中的四种容器适配器1.stack栈后进先出LIFO包含初始化方法和常用操作push/pop/top等2.queue队列先进先出FIFO说明其特点和基本操作push/pop/front/back等3.priority_queue优先级队列自动排序详细讲解其堆实现原理和自定义比较方法4.bitset位图固定大小位集合介绍位操作方法和转换函数。一、stack 栈1.定义及初始化stack 是一种后进先出LIFO, Last-In-First-Out的数据结构它只允许在栈顶进行插入和删除操作。stack 只是很单纯地把各项操作转化为内部容器对应的函数调用。你可以使用任何支持 back()、push_back()和pop_back()成员函数的标准容器支持 stack。使用push(入栈)将数据放入stack,使用pop(出栈)将元素从容器中移除。使用stack,必须包含头文件stack:#include stack#include stack // 默认初始化使用deque作为底层容器 std::stackint s1; // 使用自定义底层容器初始化 std::stackint, std::vectorint s2; // 使用已有的容器初始化 std::vectorint v {1, 2, 3}; std::stackint, std::vectorint s3(v);2.常用操作1empty 成员函数检查栈是否为空返回布尔值。std::stackint s; bool is_empty s.empty(); // true2pop 成员函数移除栈顶元素无返回值。std::stackint s; s.push(1); s.push(2); s.pop(); // 移除栈顶元素23push 成员函数向栈顶添加元素。std::stackint s; s.push(1); s.push(2);4size 成员函数返回栈中元素的数量。std::stackint s; s.push(1); s.push(2); s.push(3); size_t size s.size(); // 35top 成员函数返回栈顶元素的引用不修改栈。std::stackint s; s.push(1); s.push(2); int top_val s.top(); // 2二、queue 队列1. 定义及初始化queue 是一种先进先出FIFO, First-In-First-Out的数据结构它允许在队尾插入元素在队首删除元素。使用queue,必须引用头文件queue#include queue#include queue // 默认初始化使用deque作为底层容器 std::queueint q1; // 使用自定义底层容器初始化 std::queueint, std::listint q2; // 使用已有的容器初始化 std::listint l {1, 2, 3}; std::queueint, std::listint q3(l);2.常用操作1back 成员函数返回队尾元素的引用不修改队列。std::queueint q; q.push(1); q.push(2); int back_val q.back(); // 22empty 成员函数检查队列是否为空返回布尔值。std::queueint q; bool is_empty q.empty(); // true3front 成员函数返回队首元素的引用不修改队列。std::queueint q; q.push(1); q.push(2); int front_val q.front(); // 14pop 成员函数移除队首元素无返回值。std::queueint q; q.push(1); q.push(2); q.pop(); // 移除队首元素15push 成员函数向队尾添加元素。std::queueint q; q.push(1); q.push(2);6size 成员函数返回队列中元素的数量。std::queueint q; q.push(1); q.push(2); q.push(3); size_t size q.size(); // 3三、priority queue 优先级队列1.定义及初始化priority queue 是一种特殊的队列它会根据元素的优先级自动排序这里的第一个元素并不是第一个放入的元素,而是优先级最高的元素。默认情况下最大元素会位于队首。其内部数据结构为:大根堆不能使用list作为其容器。priority queue也是定义在头文件queue中#includequeue#include queue // 默认初始化使用vector作为底层容器默认使用less比较器 std::priority_queueint pq1; // 使用自定义比较器初始化最小元素位于队首 std::priority_queueint, std::vectorint, std::greaterint pq2; // 使用已有的容器初始化 std::vectorint v {3, 1, 4}; std::priority_queueint pq3(v.begin(), v.end()); // 队首元素是42.常用操作1empty 成员函数检查优先级队列是否为空返回布尔值。std::priority_queueint pq; bool is_empty pq.empty(); // true2pop 成员函数移除队首元素优先级最高的元素无返回值。std::priority_queueint pq; pq.push(1); pq.push(3); pq.push(2); pq.pop(); // 移除元素33push 成员函数向优先级队列中添加元素会自动调整以保持优先级顺序。std::priority_queueint pq; pq.push(1); pq.push(3); pq.push(2);4size 成员函数返回优先级队列中元素的数量。std::priority_queueint pq; pq.push(1); pq.push(2); pq.push(3); size_t size pq.size(); // 35top 成员函数返回队首元素优先级最高的元素的引用不修改队列。std::priority_queueint pq; pq.push(1); pq.push(3); pq.push(2); int top_val pq.top(); // 33.深入 priority queuepriority queue 的底层实现通常是二叉堆它具有以下特点时间复杂度push 操作O(log n)pop 操作O(log n)top 操作O(1)自定义类型的优先级对于自定义类型需要重载比较运算符或提供自定义比较器。struct Person { std::string name; int age; // 重载小于运算符使年龄大的人优先级更高 bool operator(const Person other) const { return age other.age; } }; std::priority_queuePerson pq; pq.push({Alice, 30}); pq.push({Bob, 25}); pq.push({Charlie, 35}); Person top_person pq.top(); // Charlie, 35使用自定义比较器struct CompareByAge { bool operator()(const Person a, const Person b) { // 返回true表示a应该在b之后即b的优先级更高 return a.age b.age; // 年龄小的人优先级更高 } }; std::priority_queuePerson, std::vectorPerson, CompareByAge pq;四、 bitset 位图1.初始化方法bitset 是一种固定大小的位集合它提供了位级别的操作。位图,是一个类模板它类似array类具有固定的大小。当我们定义一个bitset 时需要声明它包含多少个二进制位。例如:bitset32bitvec(1);//32位;低位为1其他位为0#include bitset // 默认初始化所有位为0 std::bitset8 b1; // 00000000 // 使用整数初始化 std::bitset8 b2(42); // 0010101042的二进制表示 // 使用字符串初始化 std::bitset8 b3(10101010); // 10101010 // 使用部分字符串初始化 std::bitset8 b4(1010, 0, 4); // 00001010只取前4位2.常用的符号和方法1位操作符按位与|按位或^按位异或~按位取反左移右移2成员函数set()设置所有位为1set(pos)设置指定位置的位为1reset()设置所有位为0reset(pos)设置指定位置的位为0flip()翻转所有位flip(pos)翻转指定位置的位test(pos)检查指定位置的位是否为1any()检查是否有任何位为1none()检查是否所有位都为0count()返回为1的位的数量size()返回位集合的大小to_ulong()转换为unsigned longto_ullong()转换为unsigned long longto_string()转换为字符串示例std::bitset8 b(10101010); // 检查位 bool bit0 b.test(0); // false第0位是0 bool bit1 b.test(1); // true第1位是1 // 设置位 b.set(0); // 10101011 b.reset(1); // 10101001 b.flip(); // 01010110 // 检查状态 bool has_any b.any(); // true bool has_none b.none(); // false int count b.count(); // 4有4位为1 // 转换 unsigned long ul b.to_ulong(); // 86 std::string s b.to_string(); // 01010110位操作示例std::bitset4 a(1010); // 1010 std::bitset4 b(1100); // 1100 std::bitset4 c a b; // 1000按位与 std::bitset4 d a | b; // 1110按位或 std::bitset4 e a ^ b; // 0110按位异或 std::bitset4 f ~a; // 0101按位取反 std::bitset4 g a 1; // 0100左移1位 std::bitset4 h a 1; // 0101右移1位