c++ - 我需要使用具有 C++ 的 add() 和 remove() 函数的字符串创建一个优先级队列

Question

所以我在这个 C++ 课上，我似乎不明白如何解决这个问题。

为字符串实现优先级队列。优先级队列与常规队列类似，只是添加到队列中的每个项目也具有关联的优先级。对于这个问题，将优先级设置为一个整数，其中0是最高优先级，值越大优先级越低。

删除函数应返回并删除具有最高优先级的项目，例如:

q.add("X",10);
q.add("Y",1);
q.add("Z",3);

cout << q.remove(); //returns Y
cout << q.remove(); //returns Z
cout << q.remove(); //returns X

.

这是我到目前为止所拥有的。

http://pastebin.com/AgXL9dfq

基本上，我只需要add()和remove()函数，但我不明白如何实现。有什么帮助吗？提前致谢。

Answer 1

这是使用 std::map 的另一个解决方案和std::vector

#include <iostream>
#include <map>
#include <vector>

class priority_queue {
    std::map<int, std::vector<std::string>> queue;
public:
    void add(int priority, std::string str) {
        if(!queue[priority].empty()) {
            queue[priority].push_back(str);
        } else {
            std::vector<std::string> vec;
            vec.push_back(str);
            queue[priority] = vec;
        }
    }
    std::string remove() {
        if(!queue.begin()->second.empty()) {
            std::string temp = queue.begin()->second[0];
            queue.begin()->second.erase(queue.begin()->second.begin());
            if(queue.begin()->second.empty())
                queue.erase(queue.begin());
            return temp;
        }
        std::cout << "ERROR: QUEUE EMPTY!" << std::endl;
        return "";
    }
};


int main() {
    priority_queue pq;

    pq.add(10, "hello");
    pq.add(10, "world");
    pq.add(11, "how");
    pq.add(12, "are");
    pq.add(13, "you?");

    std::cout << pq.remove() << std::endl;
    std::cout << pq.remove() << std::endl;
    std::cout << pq.remove() << std::endl;
    std::cout << pq.remove() << std::endl;
    std::cout << pq.remove() << std::endl;
}

它生成以下输出:

hello
world
how
are
you?

它通过使用键值为 int 的映射来工作。表示优先级， std::vector<std::string>因为它的值，即具有相同优先级的值的集合。

add()方法检查映射中是否已经存在具有给定优先级的值 - 如果存在，它只是将字符串值推到 vector 的后面，如果没有，它会创建一个新 vector ，推回该值，并将其分配给 map[priority] .

remove()方法检查队列是否为空，如果不为空，则从值容器 vector 的前面取出适当的值来返回；如果“弹出”字符串恰好是 vector 中的最后一个，则意味着不再有与其优先级相关的值，并且整个条目将从映射中删除，以免引起进一步的问题。