C++ 容器适配器深度解析：stack / queue / priority_queue 底层原理、deque 与 vector/list 性能对比及仿函数实现
·
class MinStack {
public:
MinStack() {
}
void push(int val) {
_st.push(val);
if(_min_st.empty()||val<=_min_st.top())
{
_min_st.push(val);
}
}
void pop() {
if(_min_st.top()==_st.top()) //1
{
_min_st.pop(); //注意先写1再写2，如果先写1会导致top发生变化，比较的时候就不准了
}
_st.pop(); //2
}
int top() {
return _st.top();
}
int getMin() {
return _min_st.top();
}
private:
std::stack<int> _st;
std::stack<int> _min_st;
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
思路：
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pushV int整型vector
* @param popV int整型vector
* @return bool布尔型
*/
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
// write code here
stack<int> st;
size_t pushi = 0,popi = 0;
while(pushi<pushV.size())
{
st.push(pushV[pushi++]);
while(!st.empty()&&st.top()==popV[popi]) //st.top() 必须在栈非空的情况下调用。
{
popi++;
st.pop();
}
}
return st.empty();
}
};
思路：
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> s;
for(auto& e:tokens) //e 的类型是 std::string&（字符串引用）
{
if(e=="+"||e=="-"||e=="*"||e=="/")
{
int right=s.top();
s.pop();
int left = s.top();
s.pop();
switch(e[0]) //switch括号里面必须加整形，字符也属于整形，e 是 string&（引用），e[0]代表的是字符
{
case '+': //‘+’代表的是字符+，这里面也是必须加整形
s.push(left+right);
break;
case '-':
s.push(left-right);
break;
case '*':
s.push(left*right);
break;
case '/':
s.push(left/right);
break;
default:
break;
}
}
else
{
s.push(stoi(e));
}
}
return s.top();
}
};
思路：
创建一个队列，把根节点插入队列，定义size为1，先定义一个vector<vector> vv , while(size–)循环，再定义一个vector v ，我们创建一个TreeNode* front拷贝旧的队列头部 q.front()，然后就可以放心出队列头部也就是q.pop()，此时判断front有没有左右节点，然后 v.push_back(front->val) ,如果有就把左右节点插入队列，此时我们就考虑如何结束，这是我们就会想到当队列为空的时候就结束循环，我是怎么想到的呢，因为有出有入，一旦没有入也就是没有左右节点入队列，那么只有出，我们的队列就会走向空，此时就循环结束，所以我们在最外层加上while(!q.empty()),回到之前，此时第一次的size已经走到0了，也就意味着当前层要插进数据到v已经结束———— vv.push_back(v)，此时队列里面可能还有左右节点插进去的，所以我们就可以刷新新的size，也就是size = q.size()，此时再次进入while(size–)这个循环，开启第二轮或者说是第二层插入到v，然后又把v给到vv，也就是vv.push_back(v)，直到q队列为空的时候停止，最后返回vv
栈可以用vector，也可以用List实现，但是推荐用vector，为什么呢？这就要从数组跟链表的优缺点讲起，因为栈只在同一端（栈顶）插入和删除，数组的连续内存和CPU缓存友好，性能极高。唯一缺点是可能会涉及动态扩容。链表实现（链式栈）：也可以，但每个节点需要额外存储指针，内存占用更大，实际工程中一般只在“需要极高分摊性能”或“语言/环境限制”时才用。
队列不“绝对推荐 list”。链表缓存不友好；高性能工程实现通常用循环数组。
普通数组的错误用法：
如果直接用 vector 并在出队时调用 pop(begin()) 或 erase，会导致后面所有元素向前移动，出队操作变为 O(n)，性能很差。
这是你提到的“低效情况”，理解完全正确。
高性能方案（实际工程中最常用）：
使用 循环数组（底层依然是 vector，但维护 head 和 tail 指针），
入队和出队都是 O(1)，且内存连续、CPU 缓存友好，没有链表指针开销。
这是大多数高性能队列（如 Java ArrayDeque）的底层思想。
总结：链表对 CPU 缓存不友好，是因为节点内存不连续，导致缓存频繁失效；数组内存连续，一次加载可多次命中，因此缓存友好。
是因为CPU太快了，内存太慢了，所以中间就需要一个缓存，CPU访问内存不是直接访问，而是内存先读入缓存，然后CPU直接去缓存中取
_stack.h
#pragma once
#include<vector>
#include<list>
#include<deque>
namespace shasha
{
template<class T,class Container = deque<T>>
class stack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
size_t size()const
{
return _con.size();
}
bool empty()const
{
return _con.empty();
}
T& top()
{
return _con.back();
}
const T& top()const
{
return _con.back();
}
private:
Container _con;
};
}
_queue.h
#include<list>
#include<deque>
namespace shasha
{
template<class T,class Container = deque<T>>
class queue
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_front();
}
bool empty()const
{
return _con.empty();
}
size_t size()const
{
return _con.size();
}
T& front()
{
return _con.front();
}
const T& front()const
{
return _con.front();
}
T& back()
{
return _con.back();
}
const T& back()const
{
return _con.back();
}
private:
Container _con;
};
}
test.cpp
#include<iostream>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
#include"queue.h"
#include"stack.h"
void test_stack()
{
shasha::stack<int, list<int>> s;
s.push(1);
s.push(2);
cout << s.top() << endl;
s.pop();
s.push(3);
s.push(4);
while (!s.empty())
{
cout << s.top() << endl;
s.pop();
}
cout << endl;
}
void test_queue()
{
shasha::queue<int,list<int>> q;
q.push(1);
q.push(2);
cout << q.front() << endl;
q.pop();
q.push(3);
q.push(4);
while (!q.empty())
{
cout << q.front() << endl;
q.pop();
}
cout << endl;
}
//测试vector和deque的排序时间
void test_op1()
{
srand(time(0));
const int N = 1000000;
deque<int> dq;
vector<int> v;
for (int i = 0; i < N; ++i)
{
auto e = rand() + i;
v.push_back(e);
dq.push_back(e);
}
int begin1 = clock();
sort(v.begin(), v.end());
int end1 = clock();
int begin2 = clock();
sort(dq.begin(), dq.end());
int end2 = clock();
printf("vector:%d\n", end1 - begin1);
printf("deque:%d\n", end2 - begin2);
}
void test_op2()
{
srand(time(0));
const int N = 1000000;
deque<int> dq1;
deque<int> dq2;
for (int i = 0; i < N; ++i)
{
auto e = rand() + i;
dq1.push_back(e);
dq2.push_back(e);
}
int begin1 = clock();
sort(dq1.begin(), dq1.end(), less<int>());
int end1 = clock();
int begin2 = clock();
// vector
vector<int> v(dq2.begin(), dq2.end());
sort(v.begin(), v.end());
dq2.assign(v.begin(), v.end());
int end2 = clock();
printf("deque sort:%d\n", end1 - begin1);
printf("deque copy vector sort, copy back deque:%d\n", end2 - begin2);
}
int main()
{
test_stack();
test_queue();
test_op1();
test_op2();
return 0;
}
数组：
/优点：
1.下标随机访问快，尾插尾删效率高
2.CPU高速缓存命中率高
/缺点：
3. 头部或者中间插入删除效率低
4. 插入空间不够要扩容，扩容有一定性能消耗，若果是倍数级扩容可能存在一定的空间浪费
链表：
/优点：
1.任意位置O(1)的插入删除
2.按需申请释放内存
/缺点：
3.不支持下标随机访问
4.CPU高速缓存命中率低，还存在缓存污染
下面来看看deque
上面涉及适配器，下面我将描述关于仿函数
首先，我们先讲优先队列:
priority_queue
他的头文件跟queue一样都是#include<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来自动完成此操作。
仿函数定义：一个类，如果重载了 operator()，那么用这个类创建出来的对象，在使用上就像函数一样，我们就称这个类为“仿函数类”，它的对象叫“仿函数对象”，或者直接叫“仿函数”。
priority_queue.h
#pragma once
template<class T>
class Less
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
class Greater
{
public:
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
namespace shasha
{
template<class T,class Container,class Compare = Less<T>>
class priority_queue
{
public:
priority_queue() = default;
template<class InputIterator>
priority_queue(InputIterator first,InputIterator last)
:_con(first,last)
{
for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
{
adjust_down(i);
}
}
void push(const T& x)
{
_con.push_back(x);
adjust_up(_con.size() - 1);
}
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}
const T& top()
{
return _con[0];
}
bool empty()
{
return _con.empty();
}
bool size()
{
return _con.size();
}
private: //设置成私有的原因：adjust_up 和 adjust_down 只是 priority_queue 内部维护堆结构的工具函数，不是提供给用户使用的公有接口。
void adjust_up(int child)
{
Compare com;
int parent = (child - 1) / 2;
while (child > 0)
{
if(com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void adjust_down(int parent)
{
Compare com;
int child = parent * 2 + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() && com(_con[child], _con[child+1]))
{
child = child + 1;
}
if (com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
private:
Container _con;
};
}
test.cpp
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
//int main()
//{
// //类加模板加仿函数
// // 默认是大的优先级高
// priority_queue<int> pq;
//
// //如果要改成小的优先级高 这里的设计有点不合理，就是刚好跟sort里面的less跟greater相反的
// //priority_queue<int, vector<int>, greater<int>> pq;
//
// pq.push(2);
// pq.push(3);
// pq.push(5);
// pq.push(1);
// pq.push(0);
//
// while (!pq.empty())
// {
// cout << pq.top() << " ";
// pq.pop();
// }
// cout << endl;
//
// vector<int> v = { 3,4,6,2,1,9,0 };
// //< 升序
// sort(v.begin(), v.end());
//
// //>降序
// sort(v.begin(), v.end(), greater<int>()); //跟上面的priority_queue刚好相反
// sort(v.rbegin(), v.rend());
//
// for (auto& e : v)
// {
// cout << e << " ";
// }
// cout << endl;
//
// return 0;
//}
//开始自己写
#include"priority_queue.h"
//int main()
//{
// shasha::priority_queue<int, vector<int>> pq;
// pq.push(1);
// pq.push(2);
// pq.push(3);
// pq.push(4);
// pq.pop();
// while (!pq.empty())
// {
// cout << pq.top() << " ";
// pq.pop();
// }
// cout << endl;
//
// return 0;
//}
// < 升序 小堆
// > 降序 大堆
template<class T, class Compare>
void BubbleSort(T* a, int n, Compare com)
{
int exchange = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n - i - 1; j++)
{
//if (a[j + 1] > a[j])
if (com(a[j + 1], a[j]))
{
exchange = 1;
swap(a[j], a[j + 1]);
}
}
if (exchange == 0)
{
break;
}
}
}
//int main()
//{
// Less<int> lessFunc; //用Less类创建了一个对象lessFunc
// cout << lessFunc(1, 2) << endl;
// cout << lessFunc.operator()(1, 2) << endl;
//
// Greater<int> greaterFunc; //用 greater类创建了一个对象greaterFunc
// cout << greaterFunc(1, 2) << endl;
// cout << greaterFunc.operator()(1, 2) << endl;
//
// int a[] = { 1,23,4,5,2,3,4,6,9 };
// //BubbleSort(a, 9, lessFunc); //有名对象
// BubbleSort(a, 9, Less<int>()); //匿名对象
// BubbleSort(a, 9, greaterFunc); //有名对象
// //BubbleSort(a, 9, Greater<int>()); //匿名对象
//
// for (auto& e : a)
// {
// cout << e << " ";
// }
// cout << endl;
// return 0;
//}
//int main()
//{
// shasha::priority_queue<int, vector<int>> pq;
// pq.push(1);
// pq.push(2);
// pq.push(3);
// pq.push(4);
// pq.pop();
// while (!pq.empty())
// {
// cout << pq.top() << " ";
// pq.pop();
// }
// cout << endl;
//
// return 0;
//}
class Date
{
public:
Date(int year = 1900, int month = 1, int day = 1)
: _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);
private:
int _year;
int _month;
int _day;
};
ostream& operator<<(ostream& _cout, const Date& d)
{
_cout << d._year << "-" << d._month << "-" << d._day;
return _cout;
}
struct PDateLess
{
bool operator()(const Date* p1,const Date* p2)
{
return *p1 < *p2;
}
};
//int main()
//{
// shasha::priority_queue<Date*, vector<Date*>,PDateLess> q1;
// q1.push(new Date(2018, 10, 29));
// q1.push(new Date(2018, 10, 28));
// q1.push(new Date(2018, 10, 30));
//
// while (!q1.empty())
// {
// cout << *q1.top() << " ";
// q1.pop();
// }
// cout << endl;
// return 0;
//}
struct OP1
{
bool operator()(int x)
{
return x % 2 == 0;
}
};
struct OP2
{
int operator()(int x)
{
if (x % 2 == 0)
{
return x * 2;
}
else
{
return x;
}
}
};
int main()
{
int a[] = { 1,3,2,4,5,2,1 };
//查找第一个偶数
auto it = find_if(a, a + 7, OP1());
cout << *it << endl;
vector<int> v = { 1,2,3,4,5,6,7 };
for (auto& e : v)
{
cout << e << " ";
}
cout << endl;
//偶数值*2
transform(v.begin(), v.end(), v.begin(), OP2());
for (auto& e : v)
{
cout << e << " ";
}
cout << endl;
return 0;
}
更多推荐
9
0- 0
已为社区贡献6条内容
所有评论(0)