stl的stack怎么用,stl基本容器

　　Yyds干货库存

　　写在这前面应该是我们STL的最后一篇博客了。今天，有三种数据结构，即堆栈、队列和优先级队列。从某种意义上说，它们不叫容器，而是容器适配器。我们先互相了解一下。

　　容器适配器。当我们看他们的模板参数时，你会明白第二个参数是一个容器。所谓容器适配器，就是我们自己不实现，而是用另一种数据结构来实现。

　　在这里，我想给你解释一下什么是适配器。在我们的日常生活中，我们知道mainland China的民用电压是220v，但当你给手机充电时，它不是200v。这是因为你的手机充电器改变了电压。这个充电器是一个适配器。也就是说，一个东西可以用，但可能功能多一点，我们只需要拿出一小部分。

　　计算机也是如此。我们可以用一种封装另一种。我们直接重用他们原来的方法，就不自己写了。

　　这里我们不会演示如何使用堆栈。一切都很简单。让我们看看它们是如何实现的。

　　这里，我们直接用一个数据结构来模拟实现栈。至于下面的德缺，暂且不提。

　　模板类T，类容器=std:deque T

　　类堆栈

　　{

　　公共：

　　无效推送(常数x) {

　　_ con . push _ back(x)；

　　}

　　void pop() {

　　_ con . pop _ back()；

　　}

　　const T top() {

　　return _ con . back()；

　　}

　　bool empty() {

　　return _ con . empty()；

　　}

　　size_t size() {

　　return _ con . size()；

　　}

　　私人：

　　Container _ con

　　};在这里测试一下吧。我们使用标准库来测试它。

　　#包括堆栈

　　int main()

　　{

　　stack int，vector int s；

　　s . push；

　　s . push(2)；

　　s . push(3)；

　　s . push(4)；

　　而(！s.empty()

　　{

　　cout s . top()endl；

　　s . pop()；

　　}

　　返回0；

　　}

　　是的，你没有看错。如果你不想用deque做容器，我们也可以选择其他的。但是你选择的数据结构必须有对应的函数，这也是STL中数据结构的函数名大多相同的优势。

　　这和stack是一样的，stack是使用的另一种数据结构。排队没什么好谈的。

　　模板类T，类容器=std:deque T

　　类别队列

　　{

　　公共：

　　无效推送(常数x) {

　　_ con . push _ back(x)；

　　}

　　void pop() {

　　_ con . pop front()；

　　}

　　const T top() {

　　return _ con . front()；

　　}

　　bool empty() {

　　return _ con . empty()；

　　}

　　size_t size() {

　　return _ con . size()；

　　}

　　T back() {

　　return _ con . back()；

　　}

　　const back()const {

　　return _ con . back()；

　　}

　　T front() {

　　return _ con . front()；

　　}

　　const T front()const

　　return _ con . front()；

　　}

　　私人：

　　Container _ con

　　};Priority_queue使用这个优先级队列，它本质上是一个底层的堆。我们今天的重点就是这个内容。

　　我们可以先看看他们的接口。都比较简单。

　　先简单用一下。这个默认好像是大优先，就是建一个大堆。

　　#包括iostream

　　#包括队列

　　使用命名空间std

　　int main()

　　{

　　priority _ queue int p；

　　p . push(1)；

　　p . push(2)；

　　p . push(0)；

　　p . push(-1)；

　　p . push(1100)；

　　而(！p.empty())

　　{

　　cout p . top()“”；

　　p . pop()；

　　}

　　返回0；

　　}

　　我们想知道我们是否能建一个小堆。标准库中有一个模仿函数更大，可以帮助我们建立一个小堆。至于模仿功能，我们只需要先知道它的用法就可以了。以后再分享。

　　int main()

　　{

　　priority_queue int，vector int，greater int p；

　　p . push(1)；

　　p . push(2)；

　　p . push(0)；

　　p . push(-1)；

　　p . push(1100)；

　　而(！p.empty())

　　{

　　cout p . top()“”；

　　p . pop()；

　　}

　　返回0；

　　}

　　Priority_queue模拟现在我们还可以模拟priority_queue是如何实现的。它的本质是一个数组，也就是一个堆。这里不讨论如何向上或向下调整。我们已经在数据结构里和大家分享过了，这里就不赘述了。我们主要看模仿功能的使用。

　　优先级队列也是一个容器适配器。

　　模板类T

　　无结构

　　{

　　布尔运算符()(常数t1，常数t2)常数

　　{

　　返回t1 t2

　　}

　　};

　　模板类T

　　结构更大

　　{

　　布尔运算符()(常数x，常数y)常数

　　{

　　返回x y；

　　}

　　};

　　模板类T，类容器=std:vector T，类比较=bit:less T

　　类别优先级_队列

　　{

　　公共：

　　优先级队列()

　　{

　　}

　　私人：

　　Container _ con

　　};推到堆里

　　无效推送(常数x)

　　{

　　_ con . push _ back(x)；

　　adjustUp(_ con . size()-1)；

　　}从堆中弹出()

　　无效弹出()

　　{

　　断言(！_ con . empty())；

　　std:swap(_con[0]，_ con[size()-1])；

　　_ con . pop _ back()；

　　adjust dwon(0)；

　　}top()查看堆叠的元素

　　const T top()

　　{

　　return _ con[0]；

　　}调整我们的数据进出堆需要调整，如果我们写下堆中元素的优先级，代码的灵活性就不行了。比如我们要一个小堆，你给我一个现成的堆。这是一个问题。我们无法控制它。早期可能用函数指针实现，但是函数指针的可读性太差。我们逐渐把它改成了模仿功能。

　　仿函数我们先来了解一下仿函数。我们来看看这样的结构。

　　结构我的结构

　　{

　　布尔运算符()(常量整数x，常量整数y)

　　{

　　返回x y；

　　}

　　};我们重载了()操作符，这使得我们的调用看起来像是函数调用，所以我们称之为模仿函数。

　　int main()

　　{

　　MyStruct comfunc

　　cout comfunc(1，2)endl；

　　返回0；

　　}

　　void adjust won(size _ t parent)

　　{

　　比较comFunc

　　size _ t child=2 * parent 1；

　　while(子尺寸())

　　{

　　if(child 1 _ con . size()com func(_ con[child]，_con[child 1])

　　{

　　孩子；

　　}

　　if(com func(_ con[父级]，_ con[子级]))

　　{

　　STD:swap(_ con[父级]，_ con[子级])；

　　父母=孩子；

　　child=2 * child 1；

　　}

　　其他

　　{

　　打破；

　　}

　　void adjustUp(int child)

　　{

　　//先建一个大堆

　　比较comFunc

　　size _ t parent=(child-1)/2；

　　while(子0)

　　{

　　if(com func(_ con[父级]，_ con[子级]))

　　{

　　STD:swap(_ con[父级]，_ con[子级])；

　　孩子=父母；

　　parent=(child-1)/2；

　　}

　　其他

　　{

　　打破；

　　}

　　}仿函数最大的好处就是代替了函数指针。对于自定义类型，我们也可以单独编写它们的模仿函数，但是要求自定义类型重载等号运算符。但是我们也知道C支持C语言。我们之前学习qsort的时候用到了函数指针，那么这里也可以传入函数指针吗？可以，但是需要一些方法。

　　我们先假设可以像最初的qsort一样使用它。

　　bool comFare(int x，int y)

　　{

　　返回x y；

　　}

　　int main()

　　{

　　bit:priority_queue int，vector int，bool(*)(int，int)p；

　　p . push(1)；

　　p . push(3)；

　　p . push(2)；

　　返回0；

　　}

　　现在我们要困惑了。我们的第三个模板参数是函数指针类型，可以看作是内置类型。编译器为自动调用它的构造函数初始化nullptr。所以编译器会报错。这里我们开始尴尬了。我们应该怎么做才能传入我们想要的比较函数？我们在这里不能使用模板参数，但是构造函数可以。

　　我们把模板参数可以实例化的对象看作是类中的一个成员变量，所以在构造函数的时候初始化它。我们需要修改函数。

　　这样，我们可以像这样使用优先级队列。

　　bool comFare(int x，int y)

　　{

　　返回x y；

　　}

　　int main()

　　{

　　bit:priority_queue int，vector int，bool(*)(int，int)p(com fare)；

　　//bit:priority _ queue int p(com fare)；

　　p . push(1)；

　　p . push(3)；

　　p . push(2)；

　　p . push(0)；

　　p . push(-1)；

　　而(！p.empty())

　　{

　　cout p . top()“”；

　　p . pop()；

　　}

　　返回0；

　　}

　　我们来试试之前的用法。能用吗？可以找到，后面需要解释原理。

　　int main()

　　{

　　//bit:priority_queue int，vector int，bool(*)(int，int)p(com fare)；

　　bit:priority _ queue int p；

　　p . push(1)；

　　p . push(3)；

　　p . push(2)；

　　p . push(0)；

　　p . push(-1)；

　　而(！p.empty())

　　{

　　cout p . top()“”；

　　p . pop()；

　　}

　　返回0；

　　}

　　我先解释一下传入的函数指针的类型。我们知道，实例化对象将调用默认的构造函数，如下所示。而且我们实例化对象的时候传入参数，第三个模板参数的类型就变成了函数指针的类型。这里的类型互相匹配。

　　这样我们就可以理解为，如果不传入函数指针类型，那么第三个模板参数默认是它的默认值，也就是仿函数类型west。编译器自动调用构造函数，并实例化模仿函数类型的对象，这就是为什么它可以被使用。我们知道我们可以使用函数指针，但如果有一个简单的函数指针，为什么还要用它呢？

　　这里的Sort，我们还想看看仿函数的应用，最好的体现就是这个sort函数，这是STL算法库中提供的一个函数。当我们看迭代器类型时，我们让你看到它。这里不做详细介绍，只说模仿功能相关的知识。

　　int main()

　　{

　　向量int v；

　　五. push _ back(1)；

　　五. push _ back(2)；

　　五. push _ back(3)；

　　五、push _ back(13)；

　　v . push _ back(-1)；

　　sort(v.begin()、v . end())；

　　for (int val : v)

　　{

　　cout val“”；

　　}

　　返回0；

　　}

　　我们注意到默认是升序。我们能把它们按降序排列吗？是的，需要使用模仿功能。

　　int main()

　　{

　　向量int v；

　　五. push _ back(1)；

　　五. push _ back(2)；

　　五. push _ back(3)；

　　五、push _ back(13)；

　　v . push _ back(-1)；

　　sort(v.begin()，v.end()，greater int())；

　　for (int val : v)

　　{

　　cout val“”；

　　}

　　返回0；

　　}

　　看上面排序中的参数，我们发现传入的是仿函数的匿名对象，和前面的有点不一样。我们可以反过来理解模仿函数的具体用途，即作为判断是上升还是下降的条件。

　　为什么在这里传入对象，我们需要解释为什么传入对象而不是简单的传入类型。第一点是，我们可能必须自己定义变量，这意味着如果我们传入类型，我们需要在类型中重载一些运算符。而且，我们的比较方法是固定的。

　　结构货物

　　{

　　string _ name

　　双_价；

　　size _ t _ saleNum

　　//.

　　布尔运算符(常量商品g)常量

　　{

　　return _ price g. _ price

　　}

　　布尔运算符(常量商品g)常量

　　{

　　return _ price g. _ price

　　}

　　};

　　int main()

　　{

　　商品gds[4]={{ 苹果，2.1，1000}，{ 香蕉，3.0，200}，{ 橘子，2.2，300}，{ 菠萝，1.5，50 } }；

　　sort(gds，gds 4，greater Goods())；

　　返回0；

　　}

　　但是这里的比较规则已经确定了，只能按价格来比较，那么如果要按销量来比较呢？这是一个问题。所以这里我们传入对象，我们可以将每个比较规则封装到一个类中，并实例化它。一般来说，小于就是小于，对应升序。

　　结构货物

　　{

　　string _ name

　　双_价；

　　size _ t _ saleNum

　　//.

　　};

　　无结构价格

　　{

　　布尔运算符()(常数商品g1，常数商品g2)常数

　　{

　　返回g1。_price g2。_价格；

　　}

　　};

　　构建更高的价格

　　{

　　布尔运算符()(常数商品g1，常数商品g2)常数

　　{

　　返回g1。_price g2。_价格；

　　}

　　};

　　struct LessSaleNum

　　{

　　布尔运算符()(常数商品g1，常数商品g2)常数

　　{

　　返回g1。_saleNum g2。_ saleNum

　　}

　　};

　　巨大结构

　　{

　　布尔运算符()(常数商品g1，常数商品g2)常数

　　{

　　返回g1。_saleNum g2。_ saleNum

　　}

　　};

　　int main()

　　{

　　商品gds[4]={{ 苹果，2.1，1000}，{ 香蕉，3.0，200}，{ 橘子，2.2，300}，{ 菠萝，1.5，50 } }；