目录
1、Deque(了解)
1.1 起源
1.2 结构
1.3 优缺点
1.4 应用
2、Stack
3、Queue
4、Priority_Queue
注意：stack，queue，priority_queue是容器适配器(container adaptor) ，封装一个容器，按照某种规则使用，一般不实现迭代器。
1、Deque(了解)
1.1 起源
vector和list优缺点，挺互补的，能不能实现一个容器，都具备他们的优点，就这样，deque诞生了，但是从现在来看，deque，并不算成功 。
1.2 结构
中控数组(map)，是一个指针数组，指针指向一个buffer数组的地址，通过迭代器遍历。
细节：
1. map中的指针，一开始放在中间位置，方便头插数据。
2. 使用两个迭代器，start，finish。
3. 通过，取模，除，找到是在第几个buffer数组的第几个位置。
1.3 优缺点
优点：
1. 头插尾插效率高。
2. 随机下标访问也不错。
缺点：
3. 中部位置插入删除，需挪动数据，效率低。
4. 遍历数据，需频繁检查，效率低。
1.4 应用
STL中对stack和queue默认选择deque作为其底层容器，主要是因为：
1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；
在queue中元素增长时，deque不仅效率高，而且内存使用率高。(一次开更多的空间，只存数据，不存节点)
2、Stack
#pragma once
#include <deque>
using namespace std;
namespace Lzc
{
template<class T, class Container = deque<T>>
class stack
{
public:
void push(const T& val)
{
_con.push_back(val);
}
void pop()
{
_con.pop_back();
}
const T& top() const
{
return _con.back();
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
Container _con;
};
}3、Queue
#pragma once
#include <deque>
using namespace std;
namespace Lzc
{
template<class T,class Container = deque<T>>
class queue
{
public:
void push(const T& val)
{
_con.push_back(val);
}
void pop()
{
_con.pop_front();
}
const T& front() const
{
return _con.front();
}
const T& back() const
{
return _con.back();
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
Container _con;
};
}4、Priority_Queue
容器适配器，封装vector，采用堆的结构。堆+堆排序+topK问题_大顶堆小顶堆java-CSDN博客
先介绍一下仿函数：本质是一个类，这个类重载operator()，他的对象可以像函数一样使用。
如：Less le; le.operator()(x,y) 等价于 le(x,y);
#include <algorithm>
#include <vector>
using namespace std;
// less(<) 升序
// greater(>) 降序
template<class T>
struct Less
{
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
struct Greater
{
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
int main()
{
vector<int> v = {3,2,4,5,1,6,7,8,9};
// void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
sort(v.begin(),v.end(),Less<int>()); // 升序 函数模板，传对象(匿名对象)
sort(v.begin(),v.end(),Greater<int>()); // 降序
return 0;
}#pragma once
#include <vector>
using namespace std;
namespace Lzc
{
template<class T, class Container = vector<T>, class Compare = less<T>> // 使用std中的less<T>和greater<T>
class priority_queue
{
public:
void AdjustUp(size_t child)//建大堆，child为插入元素的下标
{
size_t parent = (child - 1) / 2;
Compare com;
while (child > 0)
{
//if (_con[parent] < _con[child])
if (com(_con[parent], _con[child])) //建大堆
{
swap(_con[parent], _con[child]);
child = parent;
parent = (parent - 1) / 2;
}
else
break;//没有交换，则就是在这个位置
}
}
void AdjustDown(size_t parent)//建大堆,n为a的元素个数，parent为要向下调整的元素下标
{
size_t child = 2 * parent + 1;
Compare com;
while (child < size())
{
//if (_con[child] < _con[child + 1] && child + 1 < n) // 假设法，建大堆
if (com(_con[child], _con[child + 1] && child + 1 < size()))
child++;
// if (_con[parent] < _con[child]) // 建大堆
if (com(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
parent = child;
child = 2 * child + 1;
}
else
break;
}
}
void push(const T& val)
{
_con.push_back(val);
AdjustUp(size() - 1);
}
void pop()
{
swap(_con[0], _con[size() - 1]);
_con.pop_back();
AdjustDown(0);
}
const T& top() const
{
return _con.front();
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
Container _con;
};
}
