如何防止优先级队列在 C++ 中有重复值

Question

现在我正在尝试像这样在 C++ 中使用优先级队列

struct compare
{
    bool operator()(const int &a, const int &b)
    {
        return weight[a] < weight[b];
    }
};
priority_queue<int, vector<int>, compare> q;

但我希望它忽略任何重复值

是否可以使用任何技术来做到这一点？

或者我应该构建我的 priority_queue DS

Answer 1

答案是为 std::priority_queue 创建自定义容器：

template <typename T>
class Vector : public std::vector<T>
{
public:
    using std::vector<T>::vector;

    void push_back(const T &value)
    {
        if (std::find(this->begin(), this->end(), value) == this->end()) std::vector<T>::push_back(value);
    }
};

int main()  //
{
    std::vector<int> data = {0, 4, 1, 2, 2, 1, 3, 4};
    std::vector<float> weight = {.3, .1, .6, .2, .5};
    auto comp = [&weight](int first, int second) { return weight[first] < weight[second]; };

    std::priority_queue<int, Vector<int>, decltype(comp)> queue(comp);

    for (auto item : data) queue.push(item);

    while (!queue.empty())
    {
        cout << queue.top() << ", ";
        queue.pop();
    }
    cout << endl;
}

这里我继承了std::vector并更改了push_back检测重复的方法。

但这是执行此操作的有效方法（具有复杂性 O(n)）。我们可以创建一个自定义队列，其 top, pop, empty, size, push 函数与 std::priority_queue:

template <typename T, typename C>
class Queue
{
    std::set<T, C> impl;

public:
    Queue(C compare) : impl(compare) {}

    const T &top() const { return *impl.begin(); }

    void pop() { impl.erase(impl.begin()); }

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

    std::size_t size() const { return impl.size(); }

    void push(const T &value) { impl.insert(value); }
};

int main()  //
{
    std::vector<int> data = {0, 4, 1, 2, 2, 1, 3, 4};
    std::vector<float> weight = {.3, .1, .6, .2, .5};
    auto comp = [&weight](int first, int second) { return weight[first] > weight[second]; };

    Queue<int, decltype(comp)> queue(comp);

    for (auto item : data) queue.push(item);

    while (!queue.empty())
    {
        cout << queue.top() << ", ";
        queue.pop();
    }
    cout << endl;
}

此方法使用 std::set 来保持顺序并具有更快的重复检测（具有复杂性 O(log(n))）。

如何防止优先级队列在 C++ 中有重复值

how to prevent priority queue from having duplicate values at c++

c++

stl

priority-queue