priority

_huguowang_ · 2025-09-07 20:43:04 · 科技·工程

Q：为什么要发明这个头文件？
A：两个原因，一是它解决了priority_queue只能获取堆顶的缺点，二是它快。
Q：既然快，那么时间复杂度是多少？
A：入队O(log n)，查询O(const)常数级。在题目黑匣子中获得AC，没有TLE！
Q：具体如何使用呢？
A：本地的Dev-c++中，放入和源代码相同的目录下，在代码中加上#include"priority"即可。

#ifndef _STL_PRIORITY_H
#define _STL_PRIORITY_H 1
#pragma GCC system_header
#include <debug/debug.h>
#include <algorithm>
#include <bits/stl_function.h>
#include <vector>
#if __cplusplus >= 201103L
#include <bits/uses_allocator.h>
#endif
namespace std _GLIBCXX_VISIBILITY(default){
    _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
    template <typename _Tp, typename _Sequence = vector<_Tp>,
        typename _Compare = less<typename _Sequence::value_type> >
    class priority{
        __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
        __glibcxx_class_requires(_Sequence, _SequenceConcept)
        __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
        __glibcxx_class_requires2(_Tp, _Sequence::value_type, _SameTypeConcept)
        __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp, _BinaryFunctionConcept)
        public:
            typedef typename _Sequence::value_type      value_type;
            typedef typename _Sequence::reference       reference;
            typedef typename _Sequence::const_reference const_reference;
            typedef typename _Sequence::size_type       size_type;
            typedef typename _Sequence::iterator        iterator;
            typedef typename _Sequence::const_iterator  const_iterator;
            typedef          _Sequence                  container_type;
        protected:
            _Sequence  c;
            _Compare   comp;
        public:
#if __cplusplus < 201103L
            explicit priority(const _Sequence& __c = _Sequence()) : c(__c){}
#else
            explicit priority(const _Sequence& __c) : c(__c){}
            explicit priority(_Sequence&& __c = _Sequence()) : c(std::move(__c)){}
#endif
            iterator begin() _GLIBCXX_NOEXCEPT{ return c.begin(); }
            const_iterator begin() const _GLIBCXX_NOEXCEPT{ return c.begin(); }
            iterator end() _GLIBCXX_NOEXCEPT { return c.end(); }
            const_iterator end() const _GLIBCXX_NOEXCEPT{ return c.end(); }
#if __cplusplus >= 201103L
            const_iterator cbegin() const noexcept{ return c.cbegin(); }
            const_iterator cend() const noexcept{ return c.cend(); }
#endif
            bool empty() const{ return c.empty(); }
            size_type size() const{ return c.size(); }
            reference front(){ __glibcxx_requires_nonempty(); return c.front(); }
            const_reference front() const{ __glibcxx_requires_nonempty(); return c.front(); }
            reference back(){ __glibcxx_requires_nonempty(); return c.back(); }
            const_reference back() const{ __glibcxx_requires_nonempty(); return c.back(); }
            void push(const value_type& __x){ c.insert(lower_bound(c.begin(), c.end(), __x, comp), __x); }
#if __cplusplus >= 201103L
            void push(value_type&& __x){ c.insert(lower_bound(c.begin(), c.end(), __x, comp), std::move(__x)); }
            template <typename... _Args>
            void emplace(_Args&&... __args){
                c.emplace_back(std::forward<_Args>(__args)...);
                const_reference __b = c.back(); c.pop_back();
                c.emplace(lower_bound(c.begin(), c.end(), __b, comp), std::forward<_Args>(__args)...);
            }
#endif
            void pop_front(){ __glibcxx_requires_nonempty(); c.erase(c.begin()); }
            void pop_back(){ __glibcxx_requires_nonempty(); c.pop_back(); }
#if __cplusplus >= 201103L
            void swap(priority& __p) noexcept(noexcept(swap(c, __p.c)) && noexcept(swap(comp, __p.comp)))
            { std::swap(c, __p.c), std::swap(comp, __p.comp); }
            reference operator[](const size_type& __n) _GLIBCXX_NOEXCEPT{ return c.at(__n); }
            const reference operator[](const size_type& __n) const _GLIBCXX_NOEXCEPT{ return c.at(__n); }
#endif
            reference at(const size_type& __n) _GLIBCXX_NOEXCEPT{ return c.at(__n); }
            const reference at(const size_type& __n) const _GLIBCXX_NOEXCEPT{ return c.at(__n); }
            void assign(const size_type& __n, const value_type& __x){ c.assign(__n, __x); }
#if __cplusplus >= 201103L
            template <typename _InputIterator, typename = std::_RequireInputIter<_InputIterator> >
            void assign(_InputIterator __f, _InputIterator __l){ c.assign(__f, __l); }
#endif
    };
#if __cplusplus >= 201103L
    template<typename _Tp, typename _Sequence, typename _Compare>
    inline void swap(priority<_Tp, _Sequence, _Compare>& __x, priority<_Tp, _Sequence, _Compare>& __y)
    noexcept(noexcept(__x.swap(__y))){ __x.swap(__y); }
    template<typename _Tp, typename _Sequence, typename _Compare, typename _Alloc>
    struct uses_allocator<priority<_Tp, _Sequence, _Compare>, _Alloc> : public uses_allocator<_Sequence, _Alloc>::type{};
#endif
    template<typename _Tp, typename _Alloc>
    inline bool operator==(const priority<_Tp, _Alloc>& __x, const priority<_Tp, _Alloc>& __y)
    { return (__x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin())); }
    template<typename _Tp, typename _Alloc>
    inline bool operator!=(const priority<_Tp, _Alloc>& __x, const priority<_Tp, _Alloc>& __y){ return !(__x == __y); }
    template<typename _Tp, typename _Alloc>
    inline bool operator<(const priority<_Tp, _Alloc>& __x, const priority<_Tp, _Alloc>& __y)
    { return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); }
    template<typename _Tp, typename _Alloc>
    inline bool operator>(const priority<_Tp, _Alloc>& __x, const priority<_Tp, _Alloc>& __y){ return __y < __x; }
    template<typename _Tp, typename _Alloc>
    inline bool operator<=(const priority<_Tp, _Alloc>& __x, const priority<_Tp, _Alloc>& __y){ return !(__y < __x); }
    template<typename _Tp, typename _Alloc>
    inline bool operator>=(const priority<_Tp, _Alloc>& __x, const priority<_Tp, _Alloc>& __y){ return !(__x < __y); }
    _GLIBCXX_END_NAMESPACE_CONTAINER
}
#endif