创建一个基于单向线性列表的 "具有整数优先级的队列"。

Question

当一个元素被插入时，它的优先级被设置，有三个固定值：低、中、高。一旦被放入队列，元素的优先级就不能改变。
如果没有具有任何优先级的元素，那么指向尾部的相应指针必须为空。
无参数的构造函数，复制，移动。
复制和移动分配运算符。
确定队列中具有特定优先级的元素的数量和元素的总数量。
检查是否有空队列。
插入一个具有价值和优先权的元素。
从队列中删除一个元素。
获得关于队列头部元素的优先级和价值的信息。
通过菜单实现的头部程序应检查上述所有方法的操作。

Answer 1

#include <iostream>
#include <list>
#include <algorithm>

enum class Priority
{
    Low,
    Medium,
    High
};

template <typename T, typename List = std::list<std::pair<T, Priority>>>
class PriorityQueue
{
public:
    typedef List list_type;
    typedef typename List::value_type value_type;
    typedef typename List::size_type size_type;
    typedef typename List::iterator iterator;
    typedef typename List::const_iterator const_iterator;

    PriorityQueue() : _high_end(_list.end()), _medium_end(_list.end()) {}
    PriorityQueue(const PriorityQueue &other) : _list(other._list)
    {
        init();
    }
    PriorityQueue(PriorityQueue &&other)
        : _list(std::move(other._list))
    {
        init();
        other._high_end = other._list.end();
        other._medium_end = other._list.end();
    }
    PriorityQueue(const std::initializer_list<value_type> &list) : _high_end(_list.end()), _medium_end(_list.end())
    {
        for (const auto &[value, priority] : list)
            insert(value, priority);
    }
    ~PriorityQueue() {}

    PriorityQueue &operator=(const PriorityQueue &other)
    {
        if (this != &other)
        {
            _list = other._list;
            init();
        }
        return *this;
    }

    PriorityQueue &operator=(PriorityQueue &&other)
    {
        _list = std::move(other._list);
        init();
        other._high_end = other._list.end();
        other._medium_end = other._list.end();
        return *this;
    }

    iterator begin(Priority priority)
    {
        iterator it;
        switch (priority)
        {
        case Priority::Low:
            it = _medium_end;
            break;
        case Priority::Medium:
            it = _high_end;
            break;
        case Priority::High:
            it = _list.begin();
            break;
        }
        return it;
    }

    iterator end(Priority priority)
    {
        iterator it;
        switch (priority)
        {
        case Priority::Low:
            it = _list.end();
            break;
        case Priority::Medium:
            it = _medium_end;
            break;
        case Priority::High:
            it = _high_end;
            break;
        }
        return it;
    }

    const_iterator begin(Priority priority) const
    {
        const_iterator it;
        switch (priority)
        {
        case Priority::Low:
            it = _medium_end;
            break;
        case Priority::Medium:
            it = _high_end;
            break;
        case Priority::High:
            it = _list.begin();
            break;
        }
        return it;
    }

    const_iterator end(Priority priority) const
    {
        const_iterator it;
        switch (priority)
        {
        case Priority::Low:
            it = _list.end();
            break;
        case Priority::Medium:
            it = _medium_end;
            break;
        case Priority::High:
            it = _high_end;
            break;
        }
        return it;
    }

    bool empty() const { return _list.empty(); }

    size_type size() const { return _list.size(); }

    size_type size(Priority priority) const
    {
        size_type sz = 0;
        switch (priority)
        {
        case Priority::Low:
            sz = std::distance(const_iterator(_medium_end), _list.end());
            break;
        case Priority::Medium:
            sz = std::distance(_high_end, _medium_end);
            break;
        case Priority::High:
            sz = std::distance(_list.begin(), const_iterator(_high_end));
            break;
        }
        return sz;
    }

    iterator insert(const T &value, Priority priority)
    {
        iterator it;
        switch (priority)
        {
        case Priority::Low:
        {
            auto sz_medium = size(Priority::Medium);
            auto sz_low = size(Priority::Low);
            it = _list.insert(_list.end(), std::make_pair(value, priority));
            if (sz_low == 0)
            {
                _medium_end = it;
                if (sz_medium == 0)
                    _high_end = it;
            }
            break;
        }
        case Priority::Medium:
        {
            auto sz_medium = size(Priority::Medium);
            it = _list.insert(_medium_end, std::make_pair(value, priority));
            if (sz_medium == 0)
                _high_end = it;
            break;
        }
        case Priority::High:
            it = _list.insert(_high_end, std::make_pair(value, priority));
            break;
        }
        return it;
    }

    iterator erase(iterator pos)
    {
        iterator it = _list.erase(pos);
        if (pos == _high_end)
            _high_end = it;
        if (pos == _medium_end)
            _medium_end = it;
        return it;
    }

    void remove(const T &value)
    {
        auto it = _list.begin();
        while (1)
        {
            it = find_if(it, _list.end(), [value](const auto &v)
                         { return v.first == value; });
            if (it == _list.end())
                break;
            it = erase(it);
        }
    }

    value_type front() const
    {
        return _list.front();
    }

private:
    void init()
    {
        _high_end = std::find_if(_list.begin(), _list.end(), [](const auto &v)
                                 { return v.second != Priority::High; });
        _medium_end = std::find_if(_high_end, _list.end(), [](const auto &v)
                                   { return v.second != Priority::Medium; });
    }

    list_type _list;
    iterator _high_end;
    iterator _medium_end;
};

std::ostream &operator<<(std::ostream &os, Priority priority)
{
    switch (priority)
    {
    case Priority::Low:
        os << "Low";
        break;
    case Priority::Medium:
        os << "Medium";
        break;
    case Priority::High:
        os << "High";
        break;
    }
    return os;
}

template <typename T, typename List>
std::ostream &operator<<(std::ostream &os, const PriorityQueue<T, List> &q)
{
    os << "{ ";
    for (auto priority : {Priority::High, Priority::Medium, Priority::Low})
    {
        if (priority != Priority::High)
            os << ", ";
        os << priority << ": [";
        for (auto it = q.begin(priority); it != q.end(priority); ++it)
        {
            if (it != q.begin(priority))
                os << ", ";
            os << it->first;
        }
        os << "]";
    }
    os << "}";
    return os;
}

int main()
{
    PriorityQueue<int> q = {{1, Priority::Low}, {2, Priority::Medium}, {3, Priority::High}, {4, Priority::High}, {5, Priority::Medium}, {6, Priority::Low}};
    std::cout << "q = " << q << std::endl;

    PriorityQueue<int> p1 = q;
    std::cout << "after p1 = q:\n";
    std::cout << "p1 = " << p1 << std::endl;

    PriorityQueue<int> p2 = std::move(p1);
    std::cout << "after p2 = std::move(p1):\n";
    std::cout << "p2 = " << p2 << std::endl;
    std::cout << "p1 = " << p1 << std::endl;

    q.insert(5, Priority::High);
    std::cout << "after q.insert(5, Priority::Hight):\n";
    std::cout << "q = " << q << std::endl;

    q.remove(5);
    std::cout << "after q.remove(5):\n";
    std::cout << "q = " << q << std::endl;

    std::cout << "q.front(): {" << q.front().first << ", " << q.front().second << "}" << std::endl;
    return 0;
}

$ g++ -Wall -std=c++17 main.cpp
$ ./a.out
q = { High: [3, 4], Medium: [2, 5], Low: [1, 6]}
after p1 = q:
p1 = { High: [3, 4], Medium: [2, 5], Low: [1, 6]}
after p2 = std::move(p1):
p2 = { High: [3, 4], Medium: [2, 5], Low: [1, 6]}
p1 = { High: [], Medium: [], Low: []}
after q.insert(5, Priority::Hight):
q = { High: [3, 4, 5], Medium: [2, 5], Low: [1, 6]}
after q.remove(5):
q = { High: [3, 4], Medium: [2], Low: [1, 6]}
front: {3, High}