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

Question

now I'm trying to use priority queue in c++ like this

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

but I want it to ignore any duplicate values

Is it possible using any technique to do this?

or should I build my priority_queue DS

Answer 1

The answer is creating a custom container for the 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;
}

Here I have inherited from std::vector and changed the push_back method to detect duplicates.

But this is the efficient way of doing it (has complexity O(n)). We can create a custom queue with the same top, pop, empty, size, push functions as 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;
}

This method uses std::set to keep the order and has faster duplicate detection (has complexity O(log(n))).