企业官网建设流程全解析

一.stack 的介绍和使用

1.stack 的介绍

https://cplusplus.com/reference/stack/stack/?kw=stack#google_vignette

1.stack是一种容器适配器，专门设计用来处理LIFO（后进先出）的场景。在这种数据结构中，元素的插入和删除都只能在容器的一端进行。

2.stack 本身并不管理数据，而是作为容器适配器存在的——它把某个底层容器包起来，只暴露出一组特定的接口：从尾部（栈顶）压入数据、从尾部弹出数据。这组受限的接口，正好满足了栈“后进先出”的行为特征。

3.stack 的底层容器不是固定的，可以是任何符合要求的容器类。这个容器至少需要支持以下四个操作：

• empty()：判断是否为空
• back()：获取尾部元素（即栈顶）
• push_back()：在尾部插入元素（入栈）
• pop_back()：从尾部删除元素（出栈）

4.常见的容器如 vector、deque、list 都满足这些要求。如果你不指定底层容器，stack 默认会使用 deque。

2.stack 的使用

在STL的stack 是没有迭代器的，因为如果有了迭代器就可以随意访问元素了，这样就无法保证后进先出的性质了。

3.stack 的模拟实现

从栈的接口中可以看出，栈实际是一种特殊的vector，因此使用vector完全可以模拟实现stack。

#pragma once #include <vector> // vector 也可以作为底层容器 #include <deque> // deque 是默认底层容器 #include <iostream> using namespace std; namespace hjq { // stack 容器适配器 // T：栈中存储的数据类型 // Container：底层容器类型，默认为 deque，把 Container 的尾部当作栈顶 template<class T, class Container = deque<T>> class stack { public: // 构造函数（默认即可，底层容器会自己初始化） stack() {} // 容量相关 // 判断栈是否为空 bool empty() const { return _con.empty(); } // 返回栈中元素个数 size_t size() const { return _con.size(); } // 元素访问 // 返回栈顶元素（可修改） T& top() { return _con.back(); // 尾部就是栈顶 } // 返回栈顶元素（只读） const T& top() const { return _con.back(); } // 修改操作 // 入栈：在尾部插入元素 void push(const T& x) { _con.push_back(x); // 尾部插入 → 入栈 } // 出栈：删除尾部元素 void pop() { _con.pop_back(); // 尾部删除 → 出栈 } // 交换两个栈的内容（C++11） void swap(stack<T, Container>& st) { std::swap(_con, st._con); } private: Container _con; // 底层容器，所有操作都转发给它 }; void test() { // 可以用 vector 做底层容器 // stack<int, vector<int>> st; // 可以用 list 做底层容器 // stack<int, list<int>> st; // 默认用 deque 做底层容器 stack<int> st; st.push(1); st.push(2); st.push(3); // 遍历栈（后进先出） while (!st.empty()) { cout << st.top() << " "; // 输出栈顶元素 st.pop(); // 弹出栈顶 } cout << endl; } } int main() { hjq::test(); return 0; }

在这里的代码里不需要写构造函数，因为在默认构造函数的初始化列表阶段，自定义类型成员 _con 会自动调用它的默认构造函数。

二.queue 的介绍和使用

1. queue的介绍

http://www.cplusplus.com/reference/queue/queue/

​

1.队列（queue） 是一种容器适配器，专门用在 FIFO（先进先出） 的场景中。数据从容器的一端进入，从另一端出去，就像排队一样——先来的先服务。

2.队列本身不管理数据，而是作为容器适配器存在的——它把某个底层容器包起来，只暴露一组特定的接口：从队尾入队、从队头出队。这组受限的接口，正好满足了队列“先进先出”的行为特征。

3.队列的底层容器不是固定的，可以是任何符合要求的容器。这个容器至少需要支持以下六个操作：

• empty()：判断队列是否为空
• size()：返回队列中元素的个数
• front()：获取队头元素的引用
• back()：获取队尾元素的引用
• push_back()：在队尾插入元素（入队）
• pop_front()：在队头删除元素（出队）

4. 常见的容器如 deque 和 list 都满足这些要求。如果你不指定底层容器，queue 默认会使用 dequ

2.queue 的使用

queue 是没有迭代器的，因为有了迭代器就可以随意访问元素了，就无法保证先进先出的性质了。

3.queue的模拟实现

因为queue的接口中存在头删和尾插，因此使用vector来封装效率太低，故可以借助list来模拟实现queue，具体如下：

#pragma once #include <deque> // deque 是默认底层容器 #include <iostream> using namespace std; namespace hjq { // queue 容器适配器 // T：队列中存储的数据类型 // Container：底层容器类型，默认为 deque // 特点：尾部当作队尾（入队），头部当作队头（出队） template<class T, class Container = deque<T>> class queue { public: // 构造函数（默认即可，底层容器会自己初始化） queue() {} // 容量相关 // 判断队列是否为空 bool empty() const { return _con.empty(); } // 返回队列中元素个数 size_t size() const { return _con.size(); } // 元素访问 // 返回队头元素（可修改） T& front() { return _con.front(); // 头部就是队头 } // 返回队尾元素（可修改） T& back() { return _con.back(); // 尾部就是队尾 } // 返回队头元素（只读） const T& front() const { return _con.front(); } // 返回队尾元素（只读） const T& back() const { return _con.back(); } //修改操作 // 入队：在尾部插入元素 void push(const T& val) { _con.push_back(val); // 尾部插入 --> 入队 } // 出队：在头部删除元素 void pop() { _con.pop_front(); // 头部删除 --> 出队 } private: Container _con; // 底层容器，所有操作都转发给它 }; void test() { // 可以用 list 做底层容器 // queue<int, list<int>> q; // 默认用 deque 做底层容器 queue<int> q; q.push(1); q.push(2); q.push(3); // 遍历队列（先进先出） while (!q.empty()) { cout << q.front() << " "; // 输出队头元素 q.pop(); // 弹出队头 } cout << endl; } } int main() { hjq::test(); return 0; }

跟stack一样不需要写构造函数，因为在默认构造函数的初始化列表阶段，自定义类型成员 _con 会自动调用它的默认构造函数。

三. priority_queue的介绍和使用

1.priority_queue的介绍

http://www.cplusplus.com/reference/queue/priority_queue/

1.优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：

• empty()：检测容器是否为空
• size()：返回容器中有效元素个数
• front()：返回容器中第一个元素的引用
• push_back()：在容器尾部插入元素
• pop_back()：删除容器尾部元素

5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue
类实例化指定容器类，则使用vector。
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

2.priority_queue的使用

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。

priority_queue 中的元素按权值大小排列，只有堆顶元素（权值最高）才能被访问或取出。它不提供遍历功能，所以也没有迭代器。

【注意】
1. 默认情况下，priority_queue是大堆。

#include <vector> #include <queue> #include <functional> // greater算法的头文件 void TestPriorityQueue() { // 默认情况下，创建的是大堆，其底层按照小于符号(<)比较 vector<int> v{3, 2, 7, 6, 0, 4, 1, 9, 8, 5}; priority_queue<int> q1; for (auto& e : v) { q1.push(e); } cout << q1.top() << endl; // 如果要创建小堆，将第三个模板参数换成greater比较方式即可 priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end()); cout << q2.top() << endl; }

2. 如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重
载。

class Date { public: Date(int year = 2026, int month = 8, int day = 27) : _year(year) , _month(month) , _day(day) {} bool operator<(const Date& d) const // < 运算符重载 { return (_year < d._year) || (_year == d._year && _month < d._month) || (_year == d._year && _month == d._month && _day < d._day); } bool operator>(const Date& d) const // > 运算符重载 { return (_year > d._year) || (_year == d._year && _month > d._month) || (_year == d._year && _month == d._month && _day > d._day); } friend ostream& operator<<(ostream& _cout, const Date& d) { _cout << d._year << "-" << d._month << "-" << d._day; return _cout; } friend struct DateLess; private: int _year; int _month; int _day; }; void test_priority_queue1() { // 大堆，需要用户在自定义类型中提供 < 的重载 priority_queue<Date> q1; q1.push(Date(2026, 8, 27)); q1.push(Date(2026, 8, 26)); q1.push(Date(2026, 8, 28)); cout << q1.top() << endl; // 输出：2026-8-28（最大日期） // 小堆，需要用户在自定义类型中提供 > 的重载 priority_queue<Date, vector<Date>, greater<Date>> q2; q2.push(Date(2026, 8, 27)); q2.push(Date(2026, 8, 26)); q2.push(Date(2026, 8, 28)); cout << q2.top() << endl; // 输出：2026-8-26（最小日期） } // 自定义仿函数：按小于比较日期 struct DateLess { bool operator()(const Date& d1, const Date& d2) { return (d1._year < d2._year) || (d1._year == d2._year && d1._month < d2._month) || (d1._year == d2._year && d1._month == d2._month && d1._day < d2._day); } }; void test_priority_queue2() { // 大堆，第3个模板参数传自定义仿函数 DateLess priority_queue<Date, vector<Date>, DateLess> q1; q1.push(Date(2026, 8, 27)); q1.push(Date(2026, 8, 26)); q1.push(Date(2026, 8, 28)); cout << q1.top() << endl; // 输出：2026-8-28（最大日期） }

3.priority_queue的模拟实现

通过对priority_queue的底层结构就是堆，因此此处只需对对进行通用的封装即可。

#pragma once #include <iostream> #include <vector> #include <functional> using namespace std; // priority_queue 本质上就是堆 // 底层默认用 vector 存数据，通过向上/向下调整维护堆结构 namespace hjq { //仿函数 less：用于建大堆 // 判断 left 是否小于 right template<class T> struct less { bool operator()(const T& left, const T& right) { return left < right; } }; // 仿函数 greater：用于建小堆 // 判断 left 是否大于 right template<class T> struct greater { bool operator()(const T& left, const T& right) { return left > right; } }; // priority_queue 类模板 // T：存储的数据类型 // Container：底层容器，默认 vector // Compare：比较方式，默认 less（建大堆） template<class T, class Container = vector<T>, class Compare = std::less<T>> class priority_queue { public: // 默认构造 priority_queue() {} //迭代器区间构造 // 用 [first, last) 区间构造堆 template <class InputIterator> priority_queue(InputIterator first, InputIterator last) { // 1. 先把数据全部插入底层容器 while (first != last) { _con.push_back(*first); ++first; } // 2. 建堆：从最后一个非叶子节点开始向下调整 // 最后一个非叶子节点 = (size - 2) / 2 int child = _con.size() - 1; int parent = (child - 1) / 2; for (int i = parent; i >= 0; i--) { adjust_down(i); } } // adjust_up：向上调整 // 用于 push：尾部插入新元素后，向上调整恢复堆结构 void adjust_up(size_t child) { Compare com; // 仿函数对象，决定是大堆还是小堆 size_t parent = (child - 1) / 2; while (child > 0) { // 如果父节点不满足堆序要求，交换父子 if (com(_con[parent], _con[child])) { std::swap(_con[child], _con[parent]); child = parent; parent = (child - 1) / 2; } else { break; // 满足堆序，停止调整 } } } // 插入元素 void push(const T& x) { _con.push_back(x); // 尾插 adjust_up(_con.size() - 1); // 从尾部向上调整 } // adjust_down：向下调整 // 用于 pop 和建堆：从某个节点向下调整恢复堆结构 // 前提：左右子树都已经满足堆序 void adjust_down(size_t parent) { Compare com; size_t child = parent * 2 + 1; // 左孩子 while (child < _con.size()) { // 1. 选出左右孩子中更符合堆序的那个 if (child + 1 < _con.size() && com(_con[child], _con[child + 1])) { child++; // 右孩子更符合 } // 2. 父节点与孩子比较，不满足堆序就交换 if (com(_con[parent], _con[child])) { std::swap(_con[child], _con[parent]); parent = child; child = parent * 2 + 1; } else { break; // 满足堆序 } } // 删除堆顶 void pop() { std::swap(_con[0], _con[_con.size() - 1]); // 堆顶换到尾部 _con.pop_back(); // 删除尾部 adjust_down(0); // 从根向下调整 } //获取堆顶（只读）不能返回可修改的引用，否则会破坏堆结构 const T& top() { return _con[0]; } // 容量相关 bool empty() const { return _con.empty(); } size_t size() const { return _con.size(); } private: Container _con; // 底层容器 }; } void test_queue_priority() { // 大堆测试 hjq::priority_queue<int> q1; q1.push(5); q1.push(1); q1.push(4); q1.push(2); q1.push(3); q1.push(6); cout << q1.top() << endl; q1.pop(); q1.pop(); cout << q1.top() << endl; // 小堆测试 vector<int> v{5, 1, 4, 2, 3, 6}; hjq::priority_queue<int, vector<int>, hjq::greater<int>> q2(v.begin(), v.end()); cout << q2.top() << endl; q2.pop(); q2.pop(); cout << q2.top() << endl; }

4.仿函数

（1）仿函数的定义：

仿函数又称为函数对象，本质上是一个重载了operator()运算符的类对象。它让一个类用起来像函数一样，可以直接通过对象调用。

语法上，仿函数的调用方式和普通函数几乎一样。但实际上，调用仿函数时，背后执行的是类中重载的operator()函数，只不过这种写法看起来和函数调用没区别。

// 仿函数（函数对象）：重载了 operator() 的类 // 让对象可以像函数一样被调用 // 定义一个仿函数类 Less，用来比较两个整数的大小 struct Less { // 重载 operator()，接收两个 int 参数，返回比较结果 // 这个类有了这个函数，就可以像函数一样调用了 bool operator()(const int& x, const int& y) { return x < y; } }; void test_functor() { // 方式一：先创建对象，再通过对象调用 Less less; // 实例化一个 Less 对象 cout << less(1, 2) << endl; // 调用 less.operator()(1, 2) // 输出1 // 方式二：用匿名对象直接调用 cout << Less()(1, 2) << endl; // Less() 构造匿名对象 // 再调用 operator()(1, 2) // 输出1 }

https://cplusplus.com/reference/functional/greater/

https://cplusplus.com/reference/functional/less/

// 仿函数（函数对象）：重载了 operator() 的类，对象可以像函数一样使用 //小于比较仿函数 // 功能：判断 x 是否小于 y template<class T> struct Less { bool operator()(const T& x, const T& y) { return x < y; // 调用类型自身的 < 运算符 } }; //大于比较仿函数 // 功能：判断 x 是否大于 y template<class T> struct Greater { bool operator()(const T& x, const T& y) { return x > y; // 调用类型自身的 > 运算符 } }; void test_functor() { // 使用 Less 仿函数 Less<int> less; // 实例化对象 cout << less(1, 2) << endl; // 1 < 2 → true --> 输出 1 // 使用 Greater 仿函数 Greater<int> greater; // 实例化对象 cout << greater(1, 2) << endl; // 1 > 2 → false --> 输出 0 }

仿函数 less 和 greater 是继承的 binary_function，可以看作是对于一类函数的总体声明，而且这是函数做不到的。

// greater：标准库中的大于比较仿函数 // 继承 binary_function 只是为了兼容旧版适配器 // 实际比较逻辑就是x > y template <class T> struct greater : binary_function<T, T, bool> { bool operator()(const T& x, const T& y) const { return x > y; }; // less：标准库中的小于比较仿函数 // 继承 binary_function 只是为了兼容旧版适配器 // 实际比较逻辑就是x < y template <class T> struct less : binary_function<T, T, bool> { bool operator()(const T& x, const T& y) const { return x < y; } };

（2）模板实例化时，仿函数的使用

类模板和函数模板在使用仿函数时，传的东西不一样：

类模板是显式实例化，在 <> 中指定模板参数的实际类型，所以传的是类型。比如 priority_queue：

//第1个模板参数是：存储数据的类型 //第2个模板参数是：基础容器的类型 //第3个模板参数是：仿函数的类型 template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type>> class priority_queue; void test() { // 建小堆 priority_queue<int, vector<int>, greater<int>> pq; // 传仿函数greater<int>类型 }

函数模板是隐式实例化，编译器根据实参推演模板参数，所以传的是对象。比如 sort：

// 第1个模板参数：迭代器的类型 // 第2个模板参数是：仿函数的类型 template <class RandomAccessIterator, class Compare> // 函数的第1,2个参数是：迭代器对象 // 函数的第3个参数是：仿函数类的对象 void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp); void test() { vector<int> v { 5,3,2,4,1 }; // 排降序(>) sort (v.begin(), b.end(), greater<int>()); // 传仿函数类greater<int>的匿名对象 for (const auto& x : v) cout << x << " "; cout << endl; }

给大家小结一下就是：类模板用类型造对象，函数模板拿对象推类型。给 priority_queue 的是类型 greater<int>，给 sort 的是对象 greater<int>()。

四.容器适配器

1.什么是适配器

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

2.STL标准库中stack和queue 的底层结构

虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque，比如：

3.deque的简单介绍(了解)

https://cplusplus.com/reference/deque/deque/

deque的原理介绍:

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

vector、list、deque 对比

vector 是一段连续的物理空间。

优点：

• 支持随机访问，O(1) 就能拿到任意位置的元素。

• 空间利用率高，底层是连续空间，不容易产生内存碎片。

• CPU 高速缓存命中率高，遍历时性能好。

缺点：

• 空间不够时需要增容，增容代价很大（重新分配空间、搬移元素、释放旧空间），还有一定的空间浪费。

• 头部和中间插入删除效率低，O(N)。

---

list 不是连续空间，由一个个独立的节点通过指针链接起来。

优点：

• 按需申请释放空间，不会浪费。

• 任意位置插入删除都是 O(1)，不需要搬移数据。

缺点：

• 不支持随机访问，只能顺着指针一个个找。

• 空间利用率低，每个节点还要额外存两个指针，小节点容易造成内存碎片。

• CPU 高速缓存命中率低，节点在内存中分散分布。

---

deque 介于两者之间，并不是真正连续的空间，而是由一段段连续的小空间拼接而成，底层类似一个动态的二维数组。

它的特点：

• 支持头插头删，vector 做不了的事它行。

• 支持随机访问，list 做不了的事它也行。

• 看起来像是融合了 vector 和 list 的优点。

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个
动态的二维数组，其底层结构如下图所示：

当deque需要增容时，不需要像vector那样经历重新配置空间、搬移元素、释放旧空间等一系列操作。它只需要新增一个buffer（缓冲区），把新数据存进去，然后让中控数组（map）新增一个指针指向这个新buffer，将其管理起来即可。

deque的底层实际上是一段分段连续的空间，并非真正的连续空间。为了维护整体连续以及随机访问的假象，这个重任就落在了deque的迭代器身上。因此，deque的迭代器设计非常复杂，内部包含了4 个指针，用来在多个缓冲区之间跳转和定位。下图展示了deque的中控数组、缓冲区、迭代器三者之间的关系：

deque 的优缺点：

deque优点：

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。
与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。

---

queue缺点：
但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

4.为什么选择deque作为stack和queue的底层默认容器

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：

1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。

结合了deque的优点，而完美的避开了其缺陷。