STL之stack、queue、priority-创新互联
容器适配器
标题名称：STL之stack、queue、priority-创新互联
文章转载：http://myzitong.com/article/dephsd.html
容器适配器，简言之是可以用不同容器来快速实现自己的工具。像stack、queue、priority_queue都是容器适配器。
- 主要接口定义如下：
namespace lz
{template>class stack
{public:
//元素入栈
void push(const T& x)
{ _con.push_back(x);
}
//元素出栈
void pop()
{ _con.pop_back();
}
//获取栈顶元素
T& top()
{ return _con.back();
}
const T& top() const
{ return _con.back();
}
//获取栈中有效元素个数
size_t size() const
{ return _con.size();
}
//判断栈是否为空
bool empty() const
{ return _con.empty();
}
//交换两个栈中的数据
void swap(stack& st)
{ _con.swap(st._con);
}
private:
Container _con;
};
}
分析：
1. 因为是容器适配器，所以我们用容器模板参数即可。如果使用库中的原生stack，底层容器是deque（queue也一样）。
+ 构造函数和析构函数：
因为使用容器，所以内部不需要自己申请任何空间，扩容等一系列问题都不需要考虑。
+ push：
栈push需要给容器底部插，所以用push_back()。
```cpp
// push：const T& x：用_con做push，也就是deque，const保护，&防止改变
void push(const T& x)
{_con.push_back(x); // _con.push_back();
} - pop：
涉及出栈，要删最后一个，所以pop_back()。
// _con的pop()
void pop()
{_con.pop_back();
}- top：
// top：T& 是因为我们调用的deque使用了back()，back()可以改变，所以deque的back()返回值本身是个引用，所以这里可以使用引用，且我们要的就是得到top()也能做修改。
T& top()
{return _con.back();
}- size：
_con的size。
size_t size() const
{return _con.size();
}- empty：
bool empty() const
{return _con.empty();
}//#pragma once
//#include//#include//using namespace std;
//
//namespace lz
//{// template>// class stack
// {// public:
// //元素入栈
// void push(const T& x)
// {// _con.push_back(x);
// }
// //元素出栈
// void pop()
// {// _con.pop_back();
// }
// //获取栈顶元素
// T& top()
// {// return _con.back();
// }
// const T& top() const
// {// return _con.back();
// }
// //获取栈中有效元素个数
// size_t size() const
// {// return _con.size();
// }
// //判断栈是否为空
// bool empty() const
// {// return _con.empty();
// }
// //交换两个栈中的数据
// void swap(stack& st)
// {// _con.swap(st._con);
// }
// private:
// Container _con;
// };
//}
// cpp
//#include"l3stack.h"
//
//int main()
//{// lz::stackst;
// st.push(1);
// st.push(2);
// st.push(3);
// st.push(4);
// st.push(5);
// cout<< "st.size() = "<< st.size()<< endl;
// while (!st.empty())
// {// cout<< st.top()<< " ";
// st.pop();
// }
//
// return 0;
//}
- queue的主要接口：
template>class queue
{public:
queue();
void push(const T& x);
void pop();
T& back();
const T& back()const;
T& front();
const T& front()const;
size_t size()const;
bool empty()const;
private:
Con _c;
};
}; - queue和stack的区别
区别在queue有front()、back()和queue的pop()必须出头。 - pop()
void pop()
{_con.pop_front();
}- front()
T& front()
{return _con.front();
}- back()
T& back()
{return _con.back();
}
//#pragma once
//#include//#include//#include//using namespace std;
//
//namespace lz
//{// template>// class queue
// {// public:
// //元素入栈
// void push(const T& x)
// {// _con.push_back(x);
// }
// //元素出栈
// void pop()
// {// _con.pop_front();
// }
//
// T& back()
// {// return _con.back();
// }
//
// T& front()
// {// return _con.front();
// }
//
// //获取栈顶元素
// T& top()
// {// return _con.back();
// }
//
// //获取栈中有效元素个数
// size_t size() const
// {// return _con.size();
// }
// //判断栈是否为空
// bool empty() const
// {// return _con.empty();
// }
// //交换两个栈中的数据
// void swap(queue& q)
// {// _con.swap(q._con);
// }
// private:
// Container _con;
// };
//}
// queue.cpp
//#include"l3queue.h"
//
//int main()
//{// lz::queue>q;
// q.push(1);
// q.push(2);
// q.push(3);
// q.push(4);
// cout<< "queue.size = "<< q.size()<< endl;
// while (!q.empty())
// {// cout<< q.front()<< endl;
// q.pop();
// }
//
// return 0;
//}
- 关于原生priority_queue：
STL原生底层实现使用：默认是大根堆，仿函数是：less<>。且底层数据结构是：vector，因为拿数组建堆方便。
用法如下：
priority_queue, less>q1; - 全部代码：
#pragma once
#include#includeusing namespace std;
// 默认是大根堆，就写大根堆
namespace lz
{// 仿函数：
templateclass less
{public:
bool operator()(const T& l, const T& r)const
{ return l< r;
}
};
templateclass greater
{public:
bool operator()(const T& l, const T& r)const
{ return l >r;
}
};
// compare：进行比较的仿函数
template, class Compare = std::less>class priority_queue
{public:
void adjust_up(size_t child)
{ Compare com;
int parent = (child-1)/2;
// 孩子>0也可
while (parent >= 0)
{ if (com(_con[parent], _con[child])) // 大根堆， 调< :孩子>父亲，就换所以父亲在前面
{std::swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
// 向下调整
void adjust_down(size_t parent)
{ Compare com;
// 每次都用右孩子
size_t child = parent * 2 + 1;
// 允许孩子最多是 size-1 合理
while (child< _con.size())
{ // 右孩子存在且更大 则child 变右孩
if (child + 1< _con.size() && com(_con[child], _con[child + 1])) // 大根 比如 less< ，小的放前面 ：
child++;
if (com(_con[parent], _con[child]))
{std::swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
priority_queue()
{ // 函数体不写就可以，
// 会自动调用容器构造，
// 但是不写不写，下面有迭代器构造函数
// 编译器就不会自己生成pq的默认构造函数。
}
templatepriority_queue(InputIteartor first, InputIteartor last)
{ // 迭代器模板中，会自动往后
while (first != last)
{ _con.push_back(*first);
++first;
}
// 数组已经好了，但是不符合堆， 向下调整规范堆：从倒数第一个父节点开始到堆顶做向下调整
for (int i = (_con.size()-1-1)/2; i >= 0; --i)
{ adjust_down(i);
}
}
size_t empty()
{ return _con.size() == 0;
}
T& top()
{ return _con.front();
}
void push(const T& x)
{ _con.push_back(x);
adjust_up(_con.size()-1);
}
void pop()
{ std::swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
_con,adjust_down(0);
}
size_t size()const
{ return _con.size();
}
private:
Container _con;
};
} 代码分析
- 构造函数
实现迭代器构造函数和无参的默认构造函数，因为我们写了迭代器构造函数，编译器发现你有自己写构造函数，就不会生成无参构造函数了，所以需要自己再写无参构造函数。
- 构造函数
- 仿函数less、greater
- less用在大顶堆，使用<。
- greater用在小顶堆，使用>。
- 发现中文名字和大小顶堆的英文相反，而英文和符号又相符。
仿函数都使用模板参数，重载()。重载()是规定，这个仿函数起比较作用，返回值即可。
- 向上向下调整算法
void adjust_up(size_t child)
{Compare com;
int parent = (child-1)/2;
// 孩子>0也可
while (parent >= 0)
{if (com(_con[parent], _con[child])) // 大根堆， 调< :孩子>父亲，就换所以父亲在前面
{ std::swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
// 向下调整
void adjust_down(size_t parent)
{Compare com;
// 每次都用右孩子
size_t child = parent * 2 + 1;
// 允许孩子最多是 size-1 合理
while (child< _con.size())
{// 右孩子存在且更大 则child 变右孩
if (child + 1< _con.size() && com(_con[child], _con[child + 1])) // 大根 比如 less< ，小的放前面 ：
child++;
if (com(_con[parent], _con[child]))
{ std::swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
} 向上调整是给当前孩子位置，不断求爹，向上调。因为开头从1个节点开始，所以后续用向上调整都能使得堆条件满足。
向下调整是给当前爹位置，不断求儿子，向下调。
- 重要函数：
- push：给堆底尾插，然后向上调整。
void push(const T& x)
{_con.push_back(x);
adjust_up(_con.size()-1);
//adjust_down(_)
}
- pop：我们要做弹出堆顶，交换堆顶和最后一个元素，利用底层容器deque的pop_back()，相当于做了删尾，为什么用最后一个和堆顶交换，因为最后一个一定是比较小（大顶堆时，小顶堆相反），符合在叶子节点的条件，所以我们再做向下调整，
void pop()
{std::swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
_con,adjust_down(0);
}#pragma once
#include#includeusing namespace std;
// 默认是大根堆，就写大根堆
namespace lz
{// 仿函数：
templateclass less
{public:
bool operator()(const T& l, const T& r)const
{ return l< r;
}
};
templateclass greater
{public:
bool operator()(const T& l, const T& r)const
{ return l >r;
}
};
// compare：进行比较的仿函数
template, class Compare = std::less>class priority_queue
{public:
void adjust_up(size_t child)
{ Compare com;
int parent = (child-1)/2;
// 孩子>0也可
while (parent >= 0)
{ if (com(_con[parent], _con[child])) // 大根堆， 调< :孩子>父亲，就换所以父亲在前面
{std::swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
// 向下调整
void adjust_down(size_t parent)
{ Compare com;
// 每次都用右孩子
size_t child = parent * 2 + 1;
// 允许孩子最多是 size-1 合理
while (child< _con.size())
{ // 右孩子存在且更大 则child 变右孩
if (child + 1< _con.size() && com(_con[child], _con[child + 1])) // 大根 比如 less< ，小的放前面 ：
child++;
if (com(_con[parent], _con[child]))
{std::swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
priority_queue()
{ // 函数体不写就可以，
// 会自动调用容器构造，
// 但是不写不写，下面有迭代器构造函数
// 编译器就不会自己生成pq的默认构造函数。
}
templatepriority_queue(InputIteartor first, InputIteartor last)
{ // 迭代器模板中，会自动往后
while (first != last)
{ _con.push_back(*first);
++first;
}
// 数组已经好了，但是不符合堆， 向下调整规范堆：从倒数第一个父节点开始到堆顶做向下调整
for (int i = (_con.size()-1-1)/2; i >= 0; --i)
{ adjust_down(i);
}
}
size_t empty()
{ return _con.size() == 0;
}
T& top()
{ return _con.front();
}
void push(const T& x)
{ _con.push_back(x);
adjust_up(_con.size()-1);
//adjust_down(_)
}
void pop()
{ std::swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
_con,adjust_down(0);
}
size_t size()const
{ return _con.size();
}
private:
Container _con;
};
}
==main.cpp==
#include"l4heap.h"
#includevoid testpq()
{lz ::priority_queue, greater>pq;
//priority_queuepq;
pq.push(3);
pq.push(1);
pq.push(2);
pq.push(5);
pq.push(0);
pq.push(1);
while (!pq.empty())
{cout<< pq.top()<< " ";
pq.pop();
}
cout<< endl<< "排序 a"<< endl;
int a[] = {3, 2 , 1 , 4 , 56, 7 , 8, 4, 0 ,5 };
lz::priority_queuepq2(a, a+ sizeof(a)/sizeof(int));
while (!pq2.empty())
{cout<< pq2.top()<< " ";
pq2.pop();
}
}
int main()
{testpq();
return 0;
} 寻找topK
优先队列只能通过把vector遍历一次全放进来才行。
这个题快排最好。
记忆一下STL规律：
队列类的如priority_queue、queue都只有pop()，而没有pop_back()，而其它的如vector、list、deque（它是双端，所以有尾删很正常）都是pop_back()，可以想象，一个vector数组，删尾巴容易删，删顶不好删，所以也不留这个接口。
选择题：
下列代码的运行结果是（ ）
int main()
{
priority_queue a;
priority_queue
priority_queue b;
for (int i = 0; i< 5; i++)
{
a.push(i);
c.push(i);
}
while (!a.empty())
{
cout<< a.top()<< ’ ';
a.pop();
}
cout<< endl;
while (!c.empty())
{
cout<< c.top()<< ’ ';
c.pop();
}
cout<< endl;
b.push(“abc”);
b.push(“abcd”);
b.push(“cbd”);
while (!b.empty())
{
cout<< b.top()<< ’ ';
b.pop();
}
cout<< endl;
return 0;
}
A.4 3 2 1 0 0 1 2 3 4 cbd abcd abc
B.0 1 2 3 4 0 1 2 3 4 cbd abcd abc
C.4 3 2 1 0 4 3 2 1 0 abc abcd cbd
D.0 1 2 3 4 4 3 2 1 0 cbd abcd abc
其中，字典序：c>a，所以选ACD中一个，剩下都是大小堆判断，好说。仿函数比起一般函数具有很多优点，以下描述错误的是( )
A.在同一时间里，由某个仿函数所代表的单一函数，可能有不同的状态
B.仿函数即使定义相同，也可能有不同的类型
C.仿函数通常比一般函数速度快
D.仿函数使程序代码变简单
仿函数是一种模板函数，因为使用了模板，要做匹配、实例化等，速度比一般函数满。此外，仿函数定义相同， 也可以有不同类型，因为实例化后可以存不同类型值。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
标题名称：STL之stack、queue、priority-创新互联
文章转载：http://myzitong.com/article/dephsd.html