STL中有关deque、stack、queue、priority_queue

                    deque

                    deque中的修改类接口STL中有关deque、stack、queue、priority_queue
                    由于deque是双端队列,所以有头插头删和尾插尾删操作。
                    下面的栈和队列的底层都是通过的deque实现的。
                    为什么要用deque作为其底层数据结构呢?
                    主要是因为:栈和队列都只需在一头进行操作,故不需要迭代器,只要具有pushback和popback的功能即可,在元素增长时deque比vector效率更高、内存使用率高,所以用deque作为底层数据结构更合适。

                    stack

                    STL中有关deque、stack、queue、priority_queue
                    根据文档里的内容我们可以看到stack中有这些接口。
                    在使用时要包含stack头文件
                    因为其底层是用deque实现的:所以有关它的模拟实现也就是对deque的一个封装。
                    例如:

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


                    queue

                    STL中有关deque、stack、queue、priority_queue
                    注意队列不同的是由front和back操作,分别是队首和队尾元素。



                    priority_queue优先队列

                    底层使用堆实现的!
                    创建优先队列的默认是按照大堆(比较参数是less)方式!也就是说每个根节点都大于它的孩子节点。

                    构造函数:std::priority_queue<int, std::vector<int>, std::greater<int> >
                    third (myints,myints+4);
                    上例是构造了一个小堆类型的优先级队列
                    它的模板参数列表:template&lt;class T, class Container=vector&lt;T&gt;, class Compare=less&lt;T&gt;&gt;
                    所以如果想要用小堆创建对象时要把第三个参数改为great。

                    这里我们把库函数中的less这个函数拿来看一下:

                    template<class _Ty = void>
                        struct less
                            : public binary_function<_Ty, _Ty, bool>
                        {   // functor for operator<
                        bool operator()(const _Ty& _Left, const _Ty& _Right) const
                            {   // apply operator< to operands
                            return (_Left < _Right);
                            }
                        };

                    如果在优先级队列内存放自定义类型数据,需要需要用户提供<、>的重载,有时也要对提供比较器规则,参考less和greater在库函数中的实现,即对()进行重载。


                    模拟实现优先级队列:

                    namespace mine
                        {
                            template <class T, class Container = vector<T>, class Compare = less<T>>//默认(less)创建的是大堆
                            class priority_queue
                            {
                            public:
                                priority_queue()
                                    :c()
                                {}
                    
                                template<class Iterator>
                                priority_queue(Iterator first, Iterator last)//区间构造,将root进行向下调整
                                    : c(first, last)
                                {
                                    // 将c中的元素调整成堆的结构
                                    int count = c.size();
                                    int root = ((count - 2) >> 1);
                                    for (; root >= 0; root--)
                                        AdjustDown(root);
                                }
                    
                                void push(const T & data)
                                {
                                    c.push_back(data);
                                    AdjustUP(c.size()-1);//传入下标
                                }
                    
                                void pop()//头删的话先将头元素与最后一个元素交换,把最后一个元素删掉后再执行向下排序
                                {
                                    if (empty())
                                        return;
                                    else
                                    {
                                        swap(c.front(), c.back());
                                        c.pop_back();
                                        AdjustDown(0);
                                    }
                                }
                                int size()const
                                {
                                    return c.size();
                                }
                                bool empty()const
                                {
                                    return c.empty();
                                }
                                const T & top()const
                                {
                                    return c.front();
                                }
                    
                            private:
                    
                                //这里的向上调整和向下调整都是大堆模式
                                void AdjustDown(int parent)//向下调整算法,把较小元素调整下去
                                {
                                    int child = parent * 2 + 1;//child代表下标
                                    while (child < c.size())
                                    {
                                        //找到以parent为根的较大的孩子
                                        //如果根有右孩子并且左孩子比右孩子小,让child等于右孩子
                                        //即child此时为较大的孩子
                                        if (child + 1 < c.size() && com(c[child], c[child + 1]))
                                        {
                                            child = child + 1;
                                        }
                                        //如果孩子节点比父亲节点大则交换
                                        if (com(c[parent], c[child]))
                                        {
                                            swap(c[child], c[parent]);
                                            parent = child;
                                            child = parent * 2 + 1;
                                        }
                                        else
                                            return;
                                    }
                                }
                    
                                void AdjustUP(int child)//向上调整算法,将较大元素调整上去
                                {
                                    int parent = (child - 1) >> 1;
                                    while (child)//没有到根的话继续循环
                                    {
                                        //如果父亲节点比孩子节点小,交换
                                        //将较大节点调整到根位置
                                        if (com(c[parent], c[child]))
                                        {
                                            swap(com(c[parent], c[child]));
                                            child = parent;
                                            parent = (child - 1) >> 1;
                                        }
                                        else
                                        {
                                            return;
                                        }
                                    }
                                }
                            private:
                                Container c;
                                Compare com;
                            };
                        }

                    这里最重要的就是向上调整和向下调整算法,同时也要注意比较规则在其中的用法。详细过程见代码注释。

                    相关文章
                    相关标签/搜索
                    今期管家婆大图 玄机图六合宝典2020年香港马会正版挂牌免费资料大全开奖历史记录在线查询网