CODEWITHSUNDEEP
c++vector
Jannat Arora
Jannat Arora

Reputation: 2989

Creating a priority queue containing unique elements

I want to create a priority queue containing unique elements. I could find that a queue containing unique vector elements can be created as follows: 

template <typename T>
class queue1 {
private:
    std::queue<T> m_queue;
    std::set<T> m_set;
public:
    bool push(const T& t) {
        if (m_set.insert(t).second) {
            m_queue.push(t);
            return true;
        }
        return false;
    }
};

queue1<vector<unsigned> > queueUnique;

But my requirement is in addition to the queue containing unique vector elements it should be a priority queue as each vector in my queue has a score associated with it. I tried to create this queue using:

priority_queue<queueUnique, vector<queueUnique>, ComparisonFunction> pq;

However this seems to be incorrect as it gives a queue of queue.

I am not getting as to how should I associate score with each vector, such that the resulting queue which I get is a priority queue with unique vector elements. For example if my queue is:

struct myDS{
  vector<unsigned> vec;
  double score;
};
queue<myDS> myqueue;
vector<unsigned> dummyVec1;
dummyVec1.push_back(5);
myDS obj;
obj.vec=dummyVec1;
obj.score=0.9;
vector<unsigned> dummyVec2;
dummyVec2.push_back(5);
myDS obj2;
obj2.vec=dummyVec2;
obj2.score=0.9; //with duplicate values score is always same so can be eliminated

Then how can I create a priority queue which is ordered on obj.score and yet does not contain duplicate elements. For example, myqueue above should contain "5" only once.

Upvotes: 4

Views: 8372

Answers (2)

thayne
thayne

Reputation: 1038

As Galik commented - what you're looking for is an ordered set:

#include <set>

struct ComparableThingy{
  ComparableThingy(std::string const& n, unsigned v):name(n),value(v){}
  std::string name;
  unsigned value;
  bool operator <(ComparableThingy const& other)const{return value<other.value;}
};

inline std::ostream& operator<<(std::ostream& out, std::set<ComparableThingy> const& s){
   for(auto const& v:s) out << v.name << "," << v.value << " ";
   return out;
}

int main()
{
 std::set<ComparableThingy> s;

 s.emplace("a",3);
 s.emplace("b",2);
 s.emplace("c",3);
 s.emplace("d",1);

 std::cout << s << "\n";

 // Equivalent to "pop"
 std::cout << "pop...\n";
 s.erase(s.begin());

 std::cout << s << "\n";
}

Output:

d,1 b,2 a,3   
pop...
b,2 a,3

Upvotes: 0

Galik
Galik

Reputation: 48605

Given that the score associated with each std::vector is unique it should be sufficient to add a comparator function to your struct myDS so that the std::priority_queue can determine the ordering:

Something like this:

struct myDS
{
    std::vector<unsigned> vec;
    double score;

    // Comparison function for ordering
    // based on score 
    bool operator<(const myDS& rhs) const
    {
        return score < rhs.score;
    }
};

template<typename T>
class queue1
{
private:

    std::priority_queue<T> m_queue;
    std::set<T> m_set;
public:
    bool push(const T& t)
    {
        if(m_set.insert(t).second)
        {
            m_queue.push(t);
            return true;
        }
        return false;
    }
};

queue1<myDS> queueUnique;

Upvotes: 3

Related Questions