priority_queue.hpp

浏览该文件的文档.

#ifndef NEFORCE_CORE_CONTAINER_PRIORITY_QUEUE_HPP__
#define NEFORCE_CORE_CONTAINER_PRIORITY_QUEUE_HPP__

 
#include "NeForce/core/algorithm/heap.hpp"
#include "NeForce/core/container/vector.hpp"
NEFORCE_BEGIN_NAMESPACE__


template <typename T, typename Sequence = vector<T>, typename Compare = less<typename Sequence::value_type>>
class priority_queue : public icollector<priority_queue<T, Sequence, Compare>> {
    static_assert(is_object_v<T>, "priority queue only contains object types.");
    static_assert(is_same_v<T, typename Sequence::value_type>, "priority queue require consistent types.");
 
public:
    using value_type = typename Sequence::value_type;           
    using difference_type = typename Sequence::difference_type; 
    using size_type = typename Sequence::size_type;             
    using reference = typename Sequence::reference;             
    using const_reference = typename Sequence::const_reference; 
 
private:
    compressed_pair<Compare, Sequence> pair_{default_construct_tag{}}; 

    NEFORCE_ALWAYS_INLINE void make_heap_inside() {
        _NEFORCE make_heap(pair_.value.begin(), pair_.value.end(), pair_.get_base());
    }
 
public:
    priority_queue() = default;

    explicit priority_queue(const Compare& comp) noexcept(is_nothrow_default_constructible_v<Sequence> &&
                                                          is_nothrow_copy_constructible_v<Compare>) :
    pair_(exact_arg_construct_tag{}, comp) {}

    priority_queue(const Compare& comp, const Sequence& seq) :
    pair_(exact_arg_construct_tag{}, comp, seq) {
        make_heap_inside();
    }

    priority_queue(const Compare& comp, Sequence&& seq) noexcept(is_nothrow_move_constructible_v<Sequence> &&
                                                                 is_nothrow_copy_constructible_v<Compare>) :
    pair_(exact_arg_construct_tag{}, comp, _NEFORCE move(seq)) {
        make_heap_inside();
    }

    template <typename Iterator, enable_if_t<is_iter_v<Iterator>, int> = 0>
    priority_queue(Iterator first, Iterator last, const Sequence& seq) :
    pair_(default_construct_tag{}, seq) {
        pair_.value.insert(pair_.value.end(), first, last);
        make_heap_inside();
    }

    template <typename Iterator, enable_if_t<is_iter_v<Iterator>, int> = 0>
    priority_queue(Iterator first, Iterator last) :
    pair_(default_construct_tag{}, first, last) {
        make_heap_inside();
    }

    template <typename Iterator, enable_if_t<is_iter_v<Iterator>, int> = 0>
    priority_queue(Iterator first, Iterator last, const Compare& comp) :
    pair_(exact_arg_construct_tag{}, comp, first, last) {
        make_heap_inside();
    }

    template <typename Iterator, enable_if_t<is_iter_v<Iterator>, int> = 0>
    priority_queue(Iterator first, Iterator last, const Compare& comp, const Sequence& seq) :
    pair_(exact_arg_construct_tag{}, comp, seq) {
        pair_.value.insert(pair_.value.end(), first, last);
        make_heap_inside();
    }

    template <typename Iterator, enable_if_t<is_iter_v<Iterator>, int> = 0>
    priority_queue(Iterator first, Iterator last, const Compare& comp, Sequence&& seq) :
    pair_(exact_arg_construct_tag{}, comp, _NEFORCE move(seq)) {
        pair_.value.insert(pair_.value.end(), first, last);
        make_heap_inside();
    }

    NEFORCE_NODISCARD bool empty() const noexcept(noexcept(_NEFORCE declval<Sequence>().empty())) {
        return pair_.value.empty();
    }

    NEFORCE_NODISCARD size_type size() const noexcept(noexcept(_NEFORCE declval<Sequence>().size())) {
        return pair_.value.size();
    }

    NEFORCE_NODISCARD const_reference top() const noexcept(noexcept(_NEFORCE declval<Sequence>().front())) {
        return pair_.value.front();
    }

    void push(const value_type& value) {
        pair_.value.push_back(value);
        _NEFORCE push_heap(pair_.value.begin(), pair_.value.end(), pair_.get_base());
    }

    void push(value_type&& value) {
        pair_.value.push_back(_NEFORCE move(value));
        _NEFORCE push_heap(pair_.value.begin(), pair_.value.end(), pair_.get_base());
    }

    void pop() {
        _NEFORCE pop_heap(pair_.value.begin(), pair_.value.end(), pair_.get_base());
        pair_.value.pop_back();
    }

    template <typename... Args>
    void emplace(Args&&... args) {
        pair_.value.emplace_back(_NEFORCE forward<Args>(args)...);
        _NEFORCE push_heap(pair_.value.begin(), pair_.value.end(), pair_.get_base());
    }

    void swap(priority_queue& other) noexcept(is_nothrow_swappable_v<Sequence> && is_nothrow_swappable_v<Compare>) {
        pair_.swap(other.pair_);
    }

    NEFORCE_NODISCARD bool operator==(const priority_queue& rhs) const
            noexcept(noexcept(pair_.value == rhs.pair_.value)) {
        return pair_.value == rhs.pair_.value;
    }

    NEFORCE_NODISCARD bool operator<(const priority_queue& rhs) const
            noexcept(noexcept(pair_.value < rhs.pair_.value)) {
        return pair_.value < rhs.pair_.value;
    }
};
 
#ifdef NEFORCE_STANDARD_17
template <typename Compare, typename Sequence>
priority_queue(Compare, Sequence) -> priority_queue<typename Sequence::value_type, Sequence, Compare>;
 
template <typename Iterator, typename Compare = less<iter_value_t<Iterator>>,
          typename Sequence = vector<iter_value_t<Iterator>>>
priority_queue(Iterator, Iterator, Compare = Compare(), Sequence = Sequence())
        -> priority_queue<iter_value_t<Iterator>, Sequence, Compare>;
#endif
 // Container
 
NEFORCE_END_NAMESPACE__
#endif // NEFORCE_CORE_CONTAINER_PRIORITY_QUEUE_HPP__