前言

回顾string

string类我们初步见识了STL容器的接口，比如size,capacity,push_back等。

回顾vector

vector类是我们正式学习了第一个容器。

重点是见识到了多种初始化的方式，特别是用着非常舒服的initializer-list初始化；

除此之外的接口其实和string非常相似，不过在reserve函数中我们见识到了容器存储数据扩容的问题，也就是深拷贝的浅拷贝问题，毕竟vector是真正的容器，可以存储任意类型的数据，对于自定义类型的数据，不能简单的memcpy解决任务；

第一次见识了现代化写法的拷贝构造和赋值重载，简单来说就是复用代码，避免自己手动申请内存和赋值。

回顾list

list类中的接口其实完全可以类比，并且由于链表（双向链表）的特殊性，只要拿到指定位置的迭代器，就可以实现O(1)时间下的任意位置的插入删除操作。

最重要的点就是list中的嵌套，list_node，list_iterator。

list_node

list不是一次申请一段连续的空间来存放数据，而是一个一个结点的申请，这样就导致必须用_prev和_next指针使得每个结点建立联系；

站在链表的角度，链表的每个元素应该是结点。

综合以上两点干脆写了一个类封装结点，在list中只暴露结点（头结点）。

list_iterator

迭代器是允许遍历的容器的必备品，但是简简单单的typedef T*并不能帮助我们舒服的使用迭代器，迭代器是模拟数组指针访问的产物；

站在链表的角度，我们使用迭代器访问的不是每个结点，而是结点里存储的数据；迭代器++--可以实现迭代器指向的结点后移前移……

为了实现这么多操作，不利用简简单单的typedef T*做迭代器，而是包装成一系列的赋值运算符重载，在list_iterator这个类中实现。

一、stack类

容器为了储存不同类型元素，肯定都设计成类模板，这个不用多说；

LIFO代表last-in first-out，栈的特性，后进先出。

唯一一个重点是适配器，第一句介绍就说，stack是一种适配器容器。

不过适配器这个问题还是留到模拟实现再来见识，毕竟使用的时候我们只跟接口打交道，会用接口是很重要的。

二、stack类的接口

接口非常少，大部分就是因为LIFO，比如增删查改，只有栈顶压入数据栈顶弹出数据，难道还能搞个insert push_back push_front吗？人家都没这个概念，而且也不允许这种操作，所以增删查改就减少到了push pop；

不止是增删查改，stack只让访问栈顶的元素，除了栈顶元素什么都没有，所以没有迭代器，也不允许实现迭代器，最后呈现出来的只有top;

除此之外，与算法相关的操作，reverse sort，stack里存储的元素数据都是严格有顺序的，根本不允许这样操作，故而最后就只有这么多接口。

而且push pop top size empty哪里还用学？

最多咱看看构造函数：

看看stack的构造函数，发现我们没有能插上收的基本，要不然就是传容器类型，要不然就是传内存池的内存开辟，或者就是C++17的右值引用，也就最下面的拷贝构造我们能插上手，其它纯当默认构造用就行。

好了，就这么多，stack的接口认识完了。

三、queue类

类模板

FIFI先进先出

适配器

俩人真是好兄弟，保持一致。

四、queue类的接口

还是老生常谈，size empty都不用说吧。

需要注意的就是push是入队尾，pop是出队头，同理，front是拿到队头的元素，back是拿到队尾的元素，毕竟严格遵循先进先出。

构造函数也是一个尿性：

咱们基本上插不上手。

五、模拟实现

不要因为stack和queue的接口少而且简单就非常松懈，接口少不代表用stack少，说简单的，二叉树的层序遍历就是非常经典的例子借助队列，还做过一个好像是括号匹配的题，用了两个栈，一个栈入左括号，一个栈入右括号。

接口简单但是应用范围还是挺广的，而且模拟实现可不一定随随便便就能实现。

1.理解什么是适配器容器

不管是string、vector、list，底层其实就是申请一块块内存，并且在内存中存储容器，它们的功能都必须从底层一点点实现，难道说能让vector代替list吗？显然是不可能的。

而stack底层实现的时候其实还是说选择数组、链表来实现，queue类似，虽然不能直接用数组链表来代替它们，但是注意到只需要数组链表的部分接口即可实现stack、queue的接口，即：

需要自己选择底层内存的申请方式，数据的维护方式->发现其实本质还是数组和链表->为何不直接用已经实现的vector/list实现呢？->封装好vector/list以后，对接口稍加选择与修改即可实现对应的操作

特别是最后这个对接口的选择与修改，非常体现适配（或者说配接）的理念。

完全可以借助已有的容器的接口通过选择修改使其适合用来配置现在设计的stack、queue。

至于选择什么样的容器来适配实现现有的容器，取决于你的需求和容器的特性。

2.stack类的实现        

	template <class T>
	class stack
	{
	public:
		void push(const T& x)
		{
			_v.push_back(x);
		}

		void pop()
		{
			_v.pop_back();
		}

		bool empty()const
		{
			return _v.empty();
		}

		T& top()
		{
			return _v.back();
		}
		const T& top()const
		{
			return _v.back();
		}
	
		size_t size()
		{
			return _v.size();
		}

	private:
		vector<T> _v;
	};

按照我们之前学习的vector的特性以及stack的特性，很容易得到这些接口，通过这个例子我们就能看出来，只将vector的尾端暴露出来作为栈顶，保证了压栈和出栈等操作的时间复杂度为O(1)。

并且stack我们一般只要求默认构造，stack不需要什么initializer-list、n-val，而底层封装的容器就有默认构造，还是我们说的，初始化列表里未显式初始化或者有缺省值的，内置类型取决于编译器，自定义类型直接调用自己的默认构造。

析构同理，拷贝构造同理。

这只是我们初步看到的，借助内部容器的封装实现容器，但是看库里面的：

人家的类模板有两个参数，第一个参数肯定就是stack里存储的数据，第二个参数是容器，默认为deque，我们现在暂时不知道啥叫deque，但是vector我们总知道吧，就相当于是：

	template <class T,class Container = vector<T>>
	class stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

		void pop()
		{
			_con.pop_back();
		}

		bool empty()const
		{
			return _con.empty();
		}

		T& top()
		{
			return _con.back();
		}
		const T& top()const
		{
			return _con.back();
		}
	
		size_t size()
		{
			return _con.size();
		}

	private:
		Container _con;
	};

这样只需要这个容器满足push_back、pop_back、empty等这些所有接口即可实现stack，通过这个例子我们也能看出来，接口设计成一样的还能降低适配器容器底层对容器的要求。

模板参数的Container可以修改底层的容器，这也是适配器的一大特点，那么为什么要设计成底层可变的容器呢？

每个人使用容器的操作不一样，也就导致默认的deque实现可能存在不足之处，所以设计成适配器模式，使得人们可以根据不同需求用不同的容器实现stack。

比如就拿我们熟悉的vector和list来比较，如果数据足够大，我们选谁？其实公说公有理，婆说婆有理，为什么这么说呢？
vector管理底层内存数据，数据是一个一个push进去的吧，扩容需要申请新空间、拷贝数据，那么好，这么搞来我问你，是不是时间和空间的浪费；

list管理底层内存数据，不存在内存空间的浪费，但是申请的一个一个结点很容易造成内存碎片化的问题，并且读取数据的时候非常容易污染CPU缓存。

在实际应用中也难免出现某种操作造成时间空间的浪费，所以提供为可供选择的容器模式，不失为一种好的解决办法。

当然，一般默认还是用deque做容器的默认值：

	template <class T,class Container = deque<T>>
	class stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

		void pop()
		{
			_con.pop_back();
		}

		bool empty()const
		{
			return _con.empty();
		}

		T& top()
		{
			return _con.back();
		}
		const T& top()const
		{
			return _con.back();
		}
	
		size_t size()
		{
			return _con.size();
		}

	private:
		Container _con;
	};

差点忘了，测试代码：

void Teststack1()
{
	xx::stack<int> st1;
	st1.push(1);
	st1.push(2);
	st1.push(3);
	st1.push(4);

	while (!st1.empty())
	{
		cout << st1.top() << " ";
		st1.pop();
	}
	cout << endl;

	xx::stack<int> st2;
	st2.push(1);
	st2.push(2);
	while (!st2.empty())
	{
		cout << st2.top() << " ";
		st2.pop();
	}
	st2.push(3);
	st2.push(4);

	while (!st2.empty())
	{
		cout << st2.top() << " ";
		st2.pop();
	}
	cout << endl;
}

3.queue类的实现

怎么说呢，queue类的道理和stack一样，只不过由于队列需要在底层内存的头和尾分别pop和push，所以vector来实现队列就非常拉了，一般就用list和deque来实现。

	template <class T,class Container = deque<T>>
	class queue
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

		void pop()
		{
			_con.pop_front();
		}

		T& front()
		{
			return _con.front();
		}

		const T& front()const
		{
			return _con.front();
		}

		T& back()
		{
			return _con.back();
		}

		const T& back()const
		{
			return _con.back();
		}

		bool empty()const
		{
			return _con.empty();
		}

		size_t size()const
		{
			return _con.size();
		}

	private:
		Container _con;
	};

测试代码：

void Testqueue1()
{
	xx::queue<int> q1;

	q1.push(1);
	q1.push(2);
	q1.push(3);
	q1.push(4);

	while (!q1.empty())
	{
		cout << q1.front() << " ";
		q1.pop();
	}
	cout << endl;

	xx::queue<int> q2;

	q2.push(1);
	q2.push(2);
	while (!q2.empty())
	{
		cout << q2.front() << " ";
		q2.pop();
	}

	q2.push(3);
	q2.push(4);

	while (!q2.empty())
	{
		cout << q2.front() << " ";
		q2.pop();
	}
	cout << endl;
}

六、deque

deque不是我们重点学习的对象，但是好多特性，比如说：deque底层结构是什么？为什么deque可以同时兼顾vector和list？deque头尾插入删除的时间复杂度如何？等等。

deque类模板还是常规的，接口也还是那几个：

其中最让我们注目的：

查看库里的接口可知，deque确实做到了既兼顾vector的接口，也兼顾了list的接口。

其中：

vector

优点：

        支持O(1)的随机位置的访问（最大的优点）

        尾插尾删效率高都是O(1)

        顺序存储数据对CPU缓存友好

缺点：

        需要扩容，扩容会造成时间的消耗以及可能造成空间的浪费

        头部或者中间的插入和删除效率低下

list

优点：

        支持任意位置O(1)下的插入和删除操作

        底层以链式结构存储内存，用一个申请一个，不存在内存的浪费

缺点：

        不支持或者说随机位置的访问效率低

        对CPU缓存不友好，容易造成内存碎片化的问题

要研究deque的优缺点，还得学习学习底层。

1.deque简单介绍

deque双端队列是一种两端开口的连续的数据结构，支持两端以O(1)插入和删除数据。

由此可知，与vector相比，头部的插入和删除效率更高；与list相比，内存使用更加连续。

2.deque的底层结构

deque的图都是网上搜deque底层结构的时候的老包浆图，基本搜到的文章都在用。

其实deque底层并不是完全连续的空间，而是申请一块又一块的连续空间，可以说连续一次申请固定元素长度的数组的内存空间，并且用map数组（指针数组）存放所有的数组指针（以一定的顺序）。

3.deque的迭代器

其实deque的结构也好理解：

重点是它的迭代器如何实现的operator*、++、[]。

①迭代器的成员变量

迭代器的成员如下：

对照着上面的图看，四个元素都是指针，分别指向：

cur是当前迭代器指向的元素；容易得到T*

first是cur指向元素所在数组的首元素地址；容易得到T*

last是cur指向元素所在数组的size()位置地址；容易得到T*

node是存储在中控数组map中cur所在数组的地址；容易得到等于node是数组的指针的指针，T**

②迭代器的相关操作

T& operator()

{

        return *cur;

}

依旧用SGI的源码：

没毛病。

---

++就比较麻烦了，看这图来说：

!=很容易实现，就是对比cur ? cur相等不相等，类比list很容易得到，默认就实现了：

源码也就是这么比的。

if(it != last)

        ++cur

else

//能走到这里说明it == last也就是it遍历到所在数组的尾了已经，那么应该去找逻辑上的下一个数组的第一个位置，怎么找呢？这个时候node就起到作用了。

{

        //node指向的是当前数组的指针，node + 1指向的逻辑上紧邻的下一个数组的指针把node = node+1，并且根据node + 1更新cur first last即可

}

另外猜也能猜出来：

后面这个什么difference肯定是给buffer的长度的，记住这个。

---

operator[]

如果是vector那种真正连续的数组，我们直接把偏移量，或者说下标给底层的数组就行了，但是deque的底层不是连续的数组，很明显还得经过计算，计算的方法也很简单，假如说我们现在要取下标18的元素，那么很容易知道有：

但是底层实现有出入：

这是deque类里封装的[]，里面又封装了一层iterator[]

现在往下就开始进入iterator类了。

从start开始算偏移量，没毛病昂，然后继续找：

等于借助的是iterator实现的operator+实现：

又复用的+=：

上来先算了个offset，offset干啥的？

比如我们现在的情况：

我们可是一路从start开始的，也就是说这里的cur和first是start的，一看，感觉不老对啊，这不是脱裤子放屁吗？

现在cur和first明明指向的是同一个位置，那是因为这是预防这种情况的发生的：

在原来的基础上头插两个数据，先别管为什么是这样的头插，你就看，此时cur - first是在干什么，其实多少还是有点看不懂，那这样，还是举个例子，我现在要pos为10位置的数，从哪开始算呢？

按道理其实就是从，cur开始嘛，数数也就是：

按道理来说是这样的吧，但是读源码可以得知：

offset肯定大于一个buff的长度了，最后只能进else，进else以后offset也是正的（因为我看了，+ += -= -都是复用的+=，只不过-是+个负数而已，所以需要判断是正是负），那就计算offset / buff_size，通过set_node函数找到其对应的数组，然后再计算剩下的值（offset % buff_size，只不过比较特殊的是，底层%效率太低了，所以干脆就用了个什么offset - node * buff_size）。得到偏移量。

如果我们没有cur - first，是谁？10 / 8 = 1；10 % 8 = 2，我去，这是啥玩意？

第一个数组的下标为2的元素2，这不错完了吗？

所以为了能够迎合/ %运算，还需要考虑补齐，为什么最后定位错了，因为按照我们的逻辑相当于从first开始算偏移量了，仔细想想是不是，但是第一个数组不是满的肯定不能直接模啊，因此先补齐了第一个数组，借助偏移量。

这个时候再计算就是16 / 8 = 2，16 % 8 = 0，没毛病了吧。

不信再套个[0]，一看就知道该访问-1，但是如果还是不管的话，根据源码的计算逻辑，访问的是first位置的数据，所以必须计算cur - first。

4.deque的增删查改

简单的就直接口述了，随便找一张图：

尾插就往finish的last位置尾插，如果last - first == buff_size，就扩容后再在新数组头插就行。

尾删也是找finish，找last - 1位置，就行，需要注意的是可能需要更新finish，如果最后一个数组只有一个数据的话。

头插我们已经见识过了，为什么要倒着头插呢，为了契合++操作：

很明显++就是认为你的数据是完全连续的，如果头插是从左往右的，那头插就炸了，因为访问了为初始化的地方。

头删类比就行了。

随机位置的插入和删除：

拿出来insert看，不细讲了，随机位置就是最后一个else，跳转到可以看到：

就一句话，随机位置的插入和删除数据肯定需要挪动数据，时间复杂度也挺高的。

所以双端队列双端队列，最经常用的就是头尾的插入和删除数据。

这就是为什么stack和queue默认底层实现容器是deque。

5.deque简单总结

• deque头尾的插入和删除数据的效率很高
• deque中间位置的插入删除效率很低，需要大量挪动数据
• 下标随机访问效率可观，但是较vector低（大量数据下）

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();

	cout << "vector:" << end1 - begin1 << endl;
	cout << "deque:" << end2 - begin2 << endl;
}

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();

	cout << "deque sort:" << end1 - begin1 << endl;
	cout << "deque copy vector sort, copy back deque:" << end2 - begin2 << endl;
}

这段代码第一段体现，相同数据相同算法下由于vector随机访问（直接访问）快于deque的随机访问（计算偏移量访问），当然，大量数据下体现。

第二段同样体现vector随机访问快于deque，但除此之外，还能体现出来拷贝的代价对于大量数据其实还能接受。

七、priority_queue

1.简单了解

queue这个头文件里除了我们常用的queue队列FIFO，还有优先级队列priority_queue，priority代表着根据一定的优先级选择性的出队列里的数据。

类模板第一个参数不用多说，priority_queue存储的数据类型T；

第二个参数说明priority_queue也是适配器模式实现的容器；

第三个参数就不知道了，没见过呢还，模拟实现阶段再看。

可能一进来就看见说，优先级队列按照一定的优先级出数据，还不知道优先级是什么，慢慢往下看介绍就发现，说优先级队列底层类似于堆，默认出最大的数据，等于啥吧，默认优先级队列是个大根堆，每次出就出堆顶数据，就算还没学模板里第三个参数，大概也知道，第三个参数大概率是用来修改priority_queue底层是大根堆还是小根堆，从而决定pop的是队列里的最大的数据还是最小的数据。

真不用很介绍了吧，就这么点接口，一般也就用个empty top push pop，偶尔用size，其它的都不咋用，就不介绍了。

具体看眼构造有没有啥幺蛾子：

一个默认构造，一个迭代器区间构造。太乘了实在是。

测试一下接口：

确实就按照大根堆来整的。

2.模拟实现

如果我们想模拟实现，歪路子就不用想了，手撕建堆，入堆的向上调整，出堆的向下调整是避不开了。

也就是，堆底层我们不是用数组来实现的嘛，当时我们C语言阶段学数据结构的时候说过，堆是特殊的完全二叉树，特点就是根节点大于等于孩子结点（大根堆），根节点小于等于孩子结点（小根堆），对于堆的数据我们可以选择用数组存放，也可以用链表存放。这里我们依旧用数组实现。

①push和adjust_up

如果实现push接口，那么上来不管三七二十一，肯定先往数组上尾插，也就是往底层容器push_back，重点是回忆我们手撕的逻辑：

就说我们现在建大根堆，parent = (child - 1)/2，比较parent和child的值，要求parent的值大于child。

比较一次：

左下角那棵树肯定是没毛病了，但是由于swap，可能破坏其它的堆的特性，所以必须循环：

child = parent;

parent = (child - 1) / 2; 

重点是最后结束循环的条件，最后一次循环应该是这样的：

child被改成0，特别注意，此时的parent = (0 - 1) / 2 = 0，所以绝对不能以parent >= 0为循环条件，因为最后一次循环以后按说parent已经越界了，但是根据计算结果没有，最后循环条件以child为基准。

最后的代码：

	template <class T,class Container = vector<T>>
	class priority_queue
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
			
			adjust_up(_con.size() - 1);
		}

	private:
		void adjust_up(int child)
		{
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				//大根堆
				if (_con[parent] < _con[child])
				{
					swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
					break;
			}
		}

	private:
		Container _con;
	};

大概讲讲：

• 向上调整不能暴露出来，能够暴露出来的接口就库里面那几个，所以private修饰
• push的逻辑就是底层数组push_back完以后，只要能保证堆的性质就行，所以调用一次adjust_up，既起到检查又起到了调整的作用

另外就是依旧命名空间包裹，防止与标准库的冲突，这里不想截了。

检验：

确实大根堆，没毛病嗷。

另外改一下：

也没毛病嗷。

②top、pop和adjust_down

假设现在push完了，我们上面写的代码，自然会将它们调整成默认的大根堆，那么我现在想遍历输出呢？

top和pop并用，top不用说，_con[0]；

回忆一下堆的pop，我们知道底层是数组，难道要按照数组的方式：

直接前移覆盖--size吗？很明显这么做的话，可以说一般情况下又得重新建堆，毕竟堆只保证根节点和孩子结点的大小关系，这样顺位继承，大概率原来的兄弟变父子，就破坏了堆的特性。

我们当时选择的方式就是swao(0,size()-1)，--size。

剩下的操作就是adjust_down，这里的adjust_down明显是我们需要知父求子。

左孩子：parent * 2 + 1

右孩子：parent * 2 + 2

不过一般我们采取只算左孩子，默认左孩子比右孩子大（大根堆下噢），只不过需要多一步检查，看看左孩子和右孩子到底谁更大。

到这里我们大概就知道谁最大，跟根节点swap以后再一直循环下去。

直到child越界：

		T top()
		{
			return _con[0];
		}

		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}
		void adjust_down(int parent)
		{
			int child = parent * 2 + 1;
			while (child < _con.size())
			{
				//while循环只能检查child<_con.size
				//做不到检查child + 1，我们自己还得检查一下，也就是可能没有右孩子
				if (child + 1 < _con.size()&&_con[child] < _con[child + 1])
					child = child + 1;
				//大根堆
				if (_con[parent] < _con[child])
				{
					swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
					break;
			}
		}           

另外为了测试代码能跑起来，顺手搞个empty：

		bool empty()
		{
			return _con.empty();
		}

		size_t size()
		{
			return _con.size();
		}

empty都怼好了，size也是顺手的事。

改成小根再试试：

③实现迭代器区间初始化构造函数

很容易写出来，但是这个时候就涉及到建堆的问题了，向上向下调整分别都怎么写呢？

向上调整建堆的思路是什么？当成push

啥叫当成push呢？

如果push数据，我们刚写过，肯定是往堆里面push数据，也就是说push的前提是push的对象是堆，而初始情况下我们把数组第一个元素当成堆（一个元素肯定是堆），后面每遍历调整一个元素都当成它是push进去的，这样的话，就符合向上调整的情景了，往堆里push数据，并且向上调整。

把整个数组遍历一遍，每次把下标的++当成push进一个数据，不断的向上调整建堆，直至遍历完整个数组：

有点抽象，但大致意思就是检测每个结点所在的子树是不是都符合根的特性。

代码表达：

			//向上调整建堆
			for (size_t i = 0; i < _con.size(); i++)
			{
				adjust_up(i);
			}

向下调整建堆的默认条件是，除了根结点的子树其它子树均符合堆的特性，因为向下调整就是在swap+pop以后的产物，此时只有根结点的子树不符合堆的特性，因此向下调整不能类比push，给出的解决办法就是从最后一个子树开始，将所有子树变的都符合堆的特性。

有点类似于递归的思想，因为叶子结点本身肯定符合堆的特性，而叶子结点所在的子树不符合堆的特性，这就刚好符合向下调整的条件，也就是子树（最开始将单个的叶子结点看成子树）是堆，根结点所在的子树不是多，循环遍历完所有子树，最后一次修改的就是整个堆的根节点所在的子树，由于前面的循环，此时除了整个堆所在的根结点的所有子树都符合堆的特性。

			//向下调整建堆
			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
			{
				adjust_down(i);
			}

需要注意的是一定把i搞成int，因为到时候跳出循环其实是i = -1，但size_t可没有-1之说，直接干成整型最大值了，也就是无限循环下去了。

当然，当时推算过时间复杂度，向下调整建堆的时间复杂度是O(n)，向上调整建堆的时间复杂度是O(nlogn)，当时是用满二叉树的最坏情况推理出来的情况。

如果还想看那就去找我的：数据结构（7）树-二叉树-堆_数据结构 树 高清大图-CSDN博客

这篇文章我特别说明了推导两种建堆方式的时间复杂度。

④仿函数

priority_queue的基础架构已经写完了，底层是堆嘛，让我写什么我写什么，向上调整建堆向下调整建堆我都已经完成了，但是其实还是有不足之处的。

回想我们当时怎么引出类模板的需要的？

	class stack
	{
	public:
		//......
	private:
		int* _arr;
		size_t _size;
		size_t _capacity;
	};

重点就在于底层存储的数据，如果我们写死成int，中间很多的malloc了，或者swap就得用int的参数，因此我们C语言阶段是这么解决的：

	typedef int STDataType;
	class stack
	{
	public:
		//......
	private:
		STDataType* _arr;
		size_t _size;
		size_t _capacity;
	};

这样在类内部确实是高枕无忧了，只要STDatatype被换了，那就可以换成其它类型的栈，但是我问你，一个项目里的STDataType是不是只有一个，如果同时创建一个int栈，一个double栈，那怎么办呢？

其实根本没办法，所以就出现模板这个玩意：

	template <class T>
	class stack
	{
	public:
		//......
	private:
		T* _arr;
		size_t _size;
		size_t _capacity;
	};

当然，我们如果用C++的习惯的话，肯定直接用适配器模式来设计stack栈了。

为什么在这里提出来模板的出现呢？
原因是我们底层代码中比较大小出现了这样的情况：

建什么样的堆内部就得改成相应的代码，但是使用者是不允许操控这部分的啊，所以就想，能不能通过传参数来控制创建大小关系从而控制创建大根堆还是小根堆。

在C语言阶段我们倒是见识过一个：

qsort函数最后一个参数就是我们自己写的，用来控制大小关系从而控制升序降序。

问题是我们现在设计的是什么？

类模板啊，类模板接收的参数是类型，设想一下，我们能做的是什么：

//main函数

int cmp(int,int)

priority_queue<int,int (*) (int,int)>

//底层类

template <class T,class Container = vector<T>,class ptr>
class priority_queue

{
        //...
};

如果传函数指针的话只能传类型，但只传函数指针变量的类型有屁用啊，我们qsort为什么能用：

因为函数指针可以说就是函数名，顺着函数名就可以找到大小比较的逻辑。

而一个单独的函数指针类型有这样的功能吗？
根本没有啊，当然，也不是说完全就限定死了，我查了查：

不过还是我们说的，用起来实在是太麻烦了，

讲这么多，终于讲到今天的重点了，既然类模板传函数指针来控制逻辑不方便，那我写成什才能传类型并且用得上呢？

不如先看这样一段代码：

template <class T>
void BubbleSort(T* arr,int n)
{
	for (size_t i = 0; i < n - 1; i++)
	{
		int flag = 1;
		for (size_t j = 0; j < n - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				swap(arr[j], arr[j + 1]);
				flag = 0;
			}
		}
		if (flag)
			break;
	}
}

int main()
{
	int arr[] = { 1,5,2,38,9,51,4 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	BubbleSort(arr,sz);

	for (auto& e : arr)
	{
		cout << e << " ";
	}
	cout << endl;

	return 0;
}

可以看到冒泡排序我们内层设计成升序的就取决于：

其实也是如果想要修改升降序必须触及底层代码，如果传参可改变这样的麻烦就好了：

template <class T>
class Less
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};

设计了一个类，什么属性都没有，有的仅仅是一个operator()，重载了一个操作符，重载的还是括号，C++的奇葩还真多啊，重载++ -- + -重载* ->我都忍了，还能重载个括号，重载的括号有什么用呢？

套到冒泡排序里：

template <class T,class Compare>
void BubbleSort(T* arr,int n)
{
	Compare cmp;
	for (size_t i = 0; i < n - 1; i++)
	{
		int flag = 1;
		for (size_t j = 0; j < n - 1 - i; j++)
		{
			//if(arr[j] > arr[j + 1])
			if (cmp(arr[j + 1],arr[j]))
			{
				swap(arr[j], arr[j + 1]);
				flag = 0;
			}
		}
		if (flag)
			break;
	}
}

当然，库里面的优先级队列采取的是Less创建大根堆，如果按照堆排序的逻辑，是升序的序列。

也就是Less表示升序，其实有点反我们平常写代码的习惯了，不过大概率库里比较的意思是：

if(arr[j + 1]  < arr[j])

这样可不就小于代表升序嘛。

冒泡排序函数模板多个Compare类型，也就代表了一个重载了比较大小逻辑的类，实例化对象可以调用所有public成员函数，唯一一个就是operator()，也就是说：cmp(arr[j + 1],arr[j])相当于cmp.operator()(arr[j + 1],arr[j])，也就相当于升序的意思。

这样的话最后我们可以通过实例化传比较逻辑：

来代表是升序。

同样道理：

template <class T>
class Greater
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x > y;
	}
};

此时：

函数逻辑我可没改昂，纯纯传参数了，结果就能控制比较的逻辑。

最核心的就是：

重载了operator()，使得类的实例化对象可以像函数一样去实现对应的逻辑，实际上还是调用了函数，只不过是调用了类的成员函数。

将此逻辑快速运用的优先级队列：

	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;
		}
	};

	template <class T,class Container = vector<T>,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);
		}

		T top()
		{
			return _con[0];
		}

		bool empty()
		{
			return _con.empty();
		}

		size_t size()
		{
			return _con.size();
		}

	private:
		//向上调整
		void adjust_up(int child)
		{
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				//大根堆
				//if (_con[child] > _con[parent])
				//大根堆，孩子大就得调整
				//小根堆，孩子小就得调整
				if(cmp(_con[parent],_con[child]))
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (parent - 1) / 2;
				}
				else
					break;
			}
		}
		//向下调整
		void adjust_down(int parent)
		{
			int child = parent * 2 + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && cmp(_con[child],_con[child + 1]))
					++child;
				//大根堆
				if (cmp(_con[parent],_con[child]))
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = child * 2 + 1;
				}
				else
					break;
			}
		}

	private:
		Container _con;
		Compare cmp;
	};

重点：

这样就可以：

注意昂，含缺省值的参数从左往右一定一个一个传，可不能间隔传。

形参写缺省值一定要从右至左不要空。

这里体现了仿函数的一大特性，灵活性和定制化：

普通函数的行为是固定的。如果你想改变一个函数的行为，通常需要修改其内部代码或定义多个功能相似但略有不同的函数。​​仿函数可以通过构造函数参数、模板参数或不同的成员函数来配置其行为​​，一个仿函数类可以产生多种行为各异的具体对象。

⑤仿函数拓展

后续我们还能见到多种行为的仿函数。

class Date
{
public:
	Date(int year = 1, 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;
}


void test_priority_queue3()
{
	xx::priority_queue<Date> pq1;
	pq1.push(Date(2025, 9, 1));
	pq1.push(Date(2024, 9, 1));
	pq1.push(Date(2025, 6, 1));

	while (!pq1.empty())
	{
		cout << pq1.top() << " ";
		pq1.pop();
	}
	cout << endl;

}

要点：
Date类有对应的逻辑运算符的重载：

priority_queue有仿函数实现默认的排序：

由此便可实现从大到小输出：

但是如果这么搞呢：

你会发现想象中的其实是根据Date的值来进行出，但是实质上存的是Date*，到时候访问的还是：

Date*，等于按照内存地址来比了，那会行吗，肯定就炸了啊。

所以这种情况，不要用默认的比较逻辑了，完全可以自己写嘛：

class Cmp
{
public:
	bool operator()(const Date* p1,const Date* p2)
	{
		return *p1 < *p2;
	}
};

void test_priority_queue3()
{
	xx::priority_queue<Date*,vector<Date*>,Cmp> pq1;
	pq1.push(new Date(2025, 9, 1));
	pq1.push(new Date(2024, 9, 1));
	pq1.push(new Date(2025, 6, 1));

	while (!pq1.empty())
	{
		cout << *pq1.top() << " ";
		pq1.pop();
	}
	cout << endl;

}

所以仿函数除了可以替代某些行为逻辑，还能修改为我要求的正常的行为逻辑出来。

后续我们继续见识多种行为的仿函数，不止是比较大。