CODEWITHSUNDEEP
c++11stl
Emerson Xu
Emerson Xu

Reputation: 438

What is the fastest way to Initialize a priority_queue from an unordered_set

It is said in construction of a priority queue , option (12):

template< class InputIt >
priority_queue( InputIt first, InputIt last,
                const Compare& compare = Compare(), 
                Container&& cont = Container() );

But I don't know how ot use this. I have a non-empty std::unordered_set<std::shared_ptr<MyStruct>> mySet, and I want to convert it to a priority queue. I also create a comparator struct MyComparator:

struct MyComparator {
  bool operator()(const std::shared_ptr<myStruct>& a, 
                  const std::shared_ptr<myStruct>& b){...}
};

Now how can I construct a new priority_queue myQueue in a better way? I used the following and it works:

std::priority_queue<std::shared_ptr<MyStruct>, std::deque<std::shared_ptr<MyStruct>, MyComparator> 
    myQueue(mySet.begin(), mySet.end());

I benchmarked both vector and deque, and I find deque will outperform vector when the size is relatively large (~30K). Since we have already known the size of mySet, I should create the deque with that size. But how can I create this priority_queue with my own comparator and predefined deque, say myDeque?

Upvotes: 1

Views: 890

Answers (1)

John Zwinck
John Zwinck

Reputation: 249532

Since you have already determined that std::deque gives you better performance than std::vector, I don't think there is much more you can do in terms of how you construct the priority_queue. As you have probably seen, there is no std::deque::reserve() method, so it's simply not possible to create a deque with memory allocated ahead of time. For most use cases this is not a problem, because the main feature of deque vs vector is that deque does not need to copy elements as new ones are inserted.

If you are still not achieving the performance you desire, you might consider either storing raw pointers (keeping your smart pointers alive outside), or simply changing your unordered_map to a regular map and relying on the ordering that container provides.

Upvotes: 1

Related Questions