C++——priority_queue模拟实现过程中的优化
前言的前言：
大佬写博客给别人看，菜鸟写博客给自己看，我是菜鸟。
前言：
1.priority_queue（优先队列）的底层原理和堆极其相似，因此在模拟实现的过程中，主要借助堆的思想取完成（但是本质还是队列）
2.本篇除了模拟实现优先队列外，还通过仿函数，类模板进行优化。
3.对于类模板的调用问题，系统会根据最匹配原则进行调用，仿函数也是
☆☆☆4.无论是类，还是类模板，都只不过是空中楼阁，是写给你看的，当你不去实例化对象时，他是没有任何意义的，只有在实例化对象后，才可以使用内部公共的函数或成员！！！！！
5.针对4，一个命名空间里可以有很多类模板，就像list迭代器那篇一样(有三个类模板，假设为A、B、C),但是如果你不在C中实例化对象A，是无法使用A中的函数的。所以说，不要被很多行代码吓到，其实没什么，只不过是在C里面需要实例化对象A，和B，方可以对其中的函数进行调用。
5.对于不好好学习前面基础知识的博主（我）而言，简直是一场灾难。
一：优先队列的模拟实现（最初版本）
因为和堆极其类似，这里无需过多的赘述，代码如下：
namespace jc
{
template<class T,class Container = vector<T>,class Compare = less<T>>
class priority_queue
{
public:
//向上调整函数
void AdjustUp(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;
}
}
}
//入数据
void push(const T& x)
{
_con.push_back(x);
AdjustUp(_con.size()-1);
}
//向下调整函数
void AdjustDown(int parent)
{
int child = 2 * parent + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() && _con[child] > _con[child + 1])
{
child++;
}
if (_con[parent] > _con[child])
{
swap(_con[parent], _con[child]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
//出数据
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
//判空
bool empty()
{
return _con.empty();
}
//取堆顶数据
const T& top() const
{
return _con.front();
}
//容器数据个数
size_t size() const
{
return _con.size();
}
private:
Container _con;
};
}注1：
👉：出入数据是借助库函数（vector、list、deque）来实现的
👉：入数据时，要考虑建小堆，还是大堆，因此需要用到向上调整函数
👉：因为vector本身没有实现出堆顶数据，因此这里统一的想法是：交换堆顶和堆尾的数 据，再出数据，出完数据后，为了保持小堆/大堆，需要用到向下调整函数，这和建出数据是一致的。
👉：其他函数，例如top(),size(),empty(),.则能用库函数就用库函数实现
注2：这里还需要注意的一个地方是（其实也不是什么注意点，对于博主我而言比较重要）
👉：想必C++学到这个阶段时，大家对与函数中实参和形参之间的传递，以及类中默认构造的缺省值给如何给定都了然于心。但对于博主我而言，类模板是之前学习中，被我忽视的一个东西，其实类模板在很多地方与函数传参以及缺省值都极其类似，除此之外，这里还需要加深对类，以及类模板的认识，这个我们稍后再说。
先讨论上述代码中的这几段：
namespace jc { template<class T,class Container = vector<T>,class Compare = less<T>> class priority_queue { public: /* .... */ private: }; }我们再来看看主函数中是如何实例化对象的：
int main() { jc::priority_queue<int> pq; return 0; }
结合先前知识，可以总结出以下几点：
①：类模板在实例化对象时，必须显式实例化（这个是先前学的，顺便提一句，函数模板是不需要显式实例化的）
②：类模板声明的固定格式为：template<class T1,class T2,....> （注：T1，T2名字不固定，根据参数的实际意义命名即可，用多了就熟悉了）
③：类模板在实例化对象时，可以缺省参数(这里和默认构造函数中的缺省参数一样的用法)
④：针对③中，缺省值不是随随便便给的！一定要根据参数的实际意义来给定值
注：对④的补充说明（以上述代码为例）：
类模板声明中
class T ：是为了说明，容器中存储的是什么类型的数据。
class Container：是为了说明，这些数据存储在什么容器当中，这里使用了缺省参数，说明默认情况下是vector<int>,（还需补充一点是，类名不是类型！类名<显式实例化> 才是类型）
class Compare = less<T>：这一点是为了代码后续方便维护，新加的参数是用来方便判断是建立小堆还是大堆，这个后续优化的时候会说。
二：优化
优化方向：只需通过传参来实现大小堆之间的切换，而不需要重新写大堆代码或者是小堆代码。
结合上述优化方向以及前言中提到的第4点，做出以下优化：
namespace jc
{
//定义两个个类模板来控制向上和向下调整函数中是建立大堆还是小堆
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;
}
};
//less是库函数自带的函数，因此我们需要调用自己命名空间内的less函数
template<class T,class Container = vector<T>,class Compare = jc::less<T>>
class priority_queue
{
public:
priority_queue() = default;//在我们不写默认构造函数时，系统会自动调用自定义类类型成员
//的默认构造函数，当但我们写了默认构造函数时，系统就不会调
//用，因此这里强制他调用默认构造，是为了其自定义类成员能够
//调用其默认的构造函数。
Compare com; //此处就是前言4所说的，不实例化对象，是没法调用其他类模板中
//的函数的
template<class InputIterator>//函数模板，需要显式实例化,系统会根据最匹配的来
priority_queue(const InputIterator left,const InputIterator right)
:_con(left,right)
{
cout << typeid(InputIterator).name() << endl;//为了观察InputIterator本质是什么
for (int i = _con.size()-1; i >=0; i--)
{
AdjustDown(i);
}
}
private:
Container _con;
};
}上面这串代码涉及的问题很多，我们来一一讨论：
1：类模板参数的缺省参数不是随便命名的
先前就已经提过这一点，我们来看看这里的命名是有多么的巧妙：这串代码的实际意义是，将一串数组按大堆建堆，数据类型是int，容器是vector，为了后续代码维护，所以类目中加了第三个参数 Compare，这个参数是为了控制建立小堆还是大堆，默认情况下是大堆。
less<int> 是系统自带的类，因此这里我们在命名空间中自己定义了一个less类来做比较，
复习：命名空间可以与外界库函数隔绝，避免重命名，通过 命名空间名:: 的方式调用。
我们需要的比较函数，放在这个自定义类当中，因此priority_queue类中，需要对该模板类进行实例化对象后，方可使用，而用来对比的函数是通过运算符重载的方式实现的，具体为 operator(),原本的写法应该为 com.operator()(参数A，参数B),省略后可以写成 com(参数A，参数B)。
2：系统会调用最匹配的函数：
我们在主函数中写下了这么一串代码：该代码中，通过地址来进行默认构造
int main()
{
int arr[] = { 6,1,2,3,7,5 };
jc::priority_queue<int> pq(arr,arr+sizeof(arr)/sizeof(int));
return 0;
}在头文件中，对应这一部分代码：
template<class InputIterator>
priority_queue(const InputIterator left,const InputIterator right)
:_con(left,right)
{
cout << "InputIterator is :" << typeid(InputIterator).name() << endl;
for (int i = _con.size()-1; i >=0; i--)
{
AdjustDown(i);
}
}运行后的结果为：
可以发现模板参数会根据函数中实际参数类型，变为int*型。
3：模板的特化
有时我们实现的对比函数没法实现，就比如当类型是Date*类型时，这时我们需要用到模板特化，具体代码如下：
template<>
struct less<Date*>
{
bool operator()(Date* const&x, Date* const &y)
{
return *x < *y;
}
};
template<>
struct greater<Date*>
{
bool operator()(Date* const& x, Date* const& y)
{
return *x > *y;
}
};注：一定要先有基础模板，才可以使用特化的模板。
原文地址：https://blog.csdn.net/m0_51952310/article/details/143425384
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！