做类似猪八戒网的网站,用jsp做的网站源代码,开发一款app软件怎么赚钱,百度地图电脑版网页目录 一、priority_queue的介绍和使用
1.1 priority_queue的介绍
1.2 priority_queue的基本接口
二、仿函数的介绍
2.1 基本概念
2.2 适用场景
三、模拟实现priority_queue
3.1 向上调整算法
3.2 向下调整算法
3.3 整体框架 一、priority_queue的介绍和使用
1.1 prio…目录 一、priority_queue的介绍和使用
1.1 priority_queue的介绍
1.2 priority_queue的基本接口
二、仿函数的介绍
2.1 基本概念
2.2 适用场景
三、模拟实现priority_queue
3.1 向上调整算法
3.2 向下调整算法
3.3 整体框架 一、priority_queue的介绍和使用
1.1 priority_queue的介绍 优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的。此上下文类似于堆在堆中可以随时插入元素并且只能检索最大堆元素(优先队列中位于顶部的元素)。优先队列被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出其称为优先队列的顶部。底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问并支持以下操作 empty()检测容器是否为空 size()返回容器中有效元素个数 front()返回容器中第一个元素的引用 push_back()在容器尾部插入元素 pop_back()删除容器尾部元素 5. 标准容器类vector和deque满足这些需求。默认情况下如果没有为特定的priority_queue类 实例化指定容器类则使用vector。 6. 需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用 算法函数make_heap、push_heap和pop_heap来自动完成此操作。
1.2 priority_queue的基本接口
函数声明接口说明 priority_queue()/priority_queue(first, last)构造一个空的优先级队列 empty( ) 检测优先级队列是否为空是返回true否则返 false top( )返回优先级队列中最大(最小元素)即堆顶元素 push(x)在优先级队列中插入元素x pop()删除优先级队列中最大(最小)元素即堆顶元素 如有不清晰的可以去查看http://cplusplus.com具体的文档
二、仿函数的介绍
2.1 基本概念 仿函数是一种可被调用的对象它可以像函数一样被使用。在C中仿函数是一种重载了函数调用运算符 operator() 的类或结构体它可以被当作函数来调用接受参数并返回结果。 在刚刚我们所讲的priority_queue就可以看到仿函数的使用 看这个 less 这个模板参数它其实就是一个仿函数接口这里我们简单的介绍一下less less这个仿函数实现的功能其实就是让我们的优先队列按降序排列即大堆与之相对应的就是greater这个仿函数其被引入进优先队列的作用是让其数据按升序排列即小堆。 大概懂了仿函数是个什么样的东西那我们大概的来模拟实现less一下吧。
class less
{bool opeartor()(int x,int y){return xy;}
} 写仿函数需要注意他一定是用class进行修饰的且其主要是对进行的重载我们写的这个less只适用于整型未免太单调了我们不妨给他加个模板。
templateclass T
class less
{bool opeartor()(T x,T y){return xy;}
}
2.2 适用场景
首先就是priority_queue这个容器需要仿函数这个接口当我们使用自定义类型时需要我们自己编写一个仿函数接口。再比如说使用 sort 时其同样有一个仿函数的接口举例 实现一个升序排序 vectorint st{1,9,8,5,6,7,3,2,1,4}; sort(st.begin(),st.end(),greaterint); 三、模拟实现priority_queue 要知道priority_queue实际上是一个堆既然是堆那就会涉及到我们的向上调整算法和向下调整算法这也是我们的主要编写内容。
3.1 向上调整算法 void adjust_up(int child){int parent (child - 1) / 2;while (parent 0){if (comp(c[parent], c[child])){std::swap(c[parent], c[child]);}elsebreak;child parent;parent (child - 1) / 2;}} 这里可以发现我们的比较方法是使用的仿函数这样就可以根据我们传入的仿函数的不同来定义不同的堆是不是很方便。 这里如果不是很懂的话可以去查看一下堆的知识。
3.2 向下调整算法 void adjust_down(int parent){int child parent * 2 1;while (child size()){if (child1size()comp(c[child], c[child1])){child 1;}if (comp(c[parent], c[child])){std::swap(c[child], c[parent]);}elsebreak;parent child;child parent * 2 1;}}
可不要忘了向下调整算法的边界判断哦。
3.3 整体框架
接口实现方面和之前的内容差不多这里我直接给大家上代码
namespace bit
{template class T, class Container vectorT, class Compare lessT class priority_queue{public:void adjust_up(int child){int parent (child - 1) / 2;while (parent 0){if (comp(c[parent], c[child])){std::swap(c[parent], c[child]);}elsebreak;child parent;parent (child - 1) / 2;}}void adjust_down(int parent){int child parent * 2 1;while (child size()){if (child1size()comp(c[child], c[child1])){child 1;}if (comp(c[parent], c[child])){std::swap(c[child], c[parent]);}elsebreak;parent child;child parent * 2 1;}}priority_queue(){}template class InputIteratorpriority_queue(InputIterator first, InputIterator last):c(first,last){for (int i (size() - 1 - 1) / 2; i 0; i--){adjust_down(i);}}bool empty() const{return c.empty();}size_t size() const{return c.size();}const T top() const{return c[0];}void push(const T x){c.push_back(x);adjust_up(size() - 1);}void pop(){std::swap(c[0], c[size() - 1]);c.pop_back();adjust_down(0);}private:Container c;Compare comp;};};
