C++语法·十伞
目录
仿函数
1.定义
2.作用
3.实现
deque（双端队列）
优点：
缺点：
stack（栈）
1.使用
2.模拟实现
queue（队列）
1.使用
2.模拟实现
priority_queue（优先级队列）
介绍
使用
注意：
模拟实现
小知识
仿函数
1.定义
本质上是一个类，通过重载operator() ，使其对象可以像普通函数一样被调用。
2.作用
（1）提供比普通函数更加灵活的行为，仿函数可以携带状态
（2）支持动态行为。
（3）与STL算法紧密配合
3.实现
仿函数的实现较为简单，只需要在一个类中重载（）运算符即可，根据不同的场景有不同的实现，以下为一个例子：
template<class T>
struct less
{
bool operator()(const T& left, const T& right)
{
return left > right;
}
};template<class T>
struct greater
{
bool operator()(const T& left, const T& right)
{
return left < right;
}
};
deque（双端队列）
一种双开口的“连续”空间的数据结构，可以在头尾两段插入删除，且时间复杂度为O（1），“连续”指的是由一段段连续的小空间拼接而成，对于维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，所以迭代器设计较复杂。
优点：
1.与vector比较，deque的优势是头部插入和删除时，不需要搬移元素，效率特别高，而且在扩 容时，也不需要搬移大量的元素，因此其效率是必vector高的。
2.与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
缺点：
不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其 是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实 际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看 到的一个应用就是，STL用其作为stack和queue的底层数据结构。
stack（栈）
1.使用
stack() 构造空的栈
empty() 检测stack是否为空size() 返回stack中元素的个数
top() 返回栈顶元素的引用
push() 将元素val压入stack中
pop() 将stack中尾部的元素弹出
2.模拟实现
#include <iostream>
#include <cstdbool>
#include <vector>using namespace std;
namespace Stack
{
template<class T>
class stack
{
std::vector<T> _v;//这里使用了vector，标准库里使用的是deque
public:
stack()
{}void push(const T& tmp)
{
_v.push_back(tmp);
}void pop()
{
_v.pop_back();
}T& top()
{
return _v.back();
}const T& top() const
{
return _v.back();
}size_t size() const
{
return _v.size();
}bool empty() const
{
return _v.empty();
}};
}
queue（队列）
1.使用
queue() 构造空的队列
empty() 检测队列是否为空，是返回true，否则返回false
size() 返回队列中有效元素的个数
front() 返回队头元素的引用
back() 返回队尾元素的引用
push() 在队尾将元素val入队列
pop() 将队头元素出队列
2.模拟实现
#include <iostream>
#include <cstdbool>
#include <list>using namespace std;
namespace Queue
{
template<class T>
class queue
{
std::list<T> _l;//使用list实现,标准库使用deque实现
public:
queue()
{}void push(const T& tmp)
{
_l.push_back(tmp);
}void pop()
{
_l.pop_front();
}T& back()
{
return _l.back();
}const T& back() const
{
return _l.back();
}T& front()
{
return _l.front();
}const T& front() const
{
return _l.front();
}size_t size() const
{
return _l.size();
}bool empty() const
{
return _l.empty();
}};
}
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来自动完成此操作。
使用
priority_queue()/priority_queue(first,last) 构造一个空的优先级队列
empty( ) 检测优先级队列是否为空，是返回true，否则返回false
top( ) 返回优先级队列中最大(最小元素)，即堆顶元素
push(x) 在优先级队列中插入元素x
pop() 删除优先级队列中最大(最小)元素，即堆顶元素
注意：
1.默认情况下，priority_queue 是大堆
2. 如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重
载。
模拟实现
#include <iostream>
#include <cstdbool>
#include <vector>using namespace std;
namespace Priority_queue
{
template<class T>
struct less
{
bool operator()(const T& left, const T& right)
{
return left > right;
}
};template<class T>
struct greater
{
bool operator()(const T& left, const T& right)
{
return left < right;
}
};template<class T,class container = std::vector<T>,class compare = less<T>>
class priority_queue
{
container _c;
public:
priority_queue()
:_c()
{}template<class Iterator>
priority_queue(Iterator first, Iterator last)
:_c(first,last)
{
//建堆
int root = (_c.size() - 2) / 2;
for (; root >= 0; --root)
Adjust_down(root);
}void push(const T& tmp)
{
_c.push_back(tmp);
Adjust_up(_c.size() - 1);
}void pop()
{
if (!_c.empty())
return;
std::swap(_c.front(), _c.back());
_c.pop_back();
Adjust_down(0);
}const T& top() const
{
return _c.front();
}size_t size() const
{
return _c.size();
}bool empty() const
{
return _c.empty();
}private:
void Adjust_up(int child)
{
int parent = (child - 1) / 2;while (child)
{
if (compare()(_c[child],_c[parent]))
{
std::swap(_c[child], _c[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
return;
}
}void Adjust_down(int parent)
{
size_t child = (parent << 1) + 1;while (child < _c.size())
{
if (child + 1 < _c.size() && compare()(_c[child + 1], _c[child]))
child += 1;if (compare()(_c[parent], _c[child]))
{
std::swap(_c[parent], _c[child]);
parent = child;
child = parent * 2 + 1;
}
else
return;
}
}
};}
小知识
1.（）为调用运算符。
2..cout打印指针时，对于char* 的指针要强制转化才可以打印地址，否则打印出来的会是字符串。
3.rand（）最多产生3万多个不重复的值，之后就会重复了。
