I have a function written using std::multimap which is excruciatingly slow precisely because of the std::multimap. After analysis, I realized that I am only using the std::multimap as a heap, so I am trying to substitute it with a std::priority_queue which only allows for heap operations, in the hope it will be faster for this usage.
Of course, the element type of std::priority_queue would need to be std::pair<mmKey, mmValue>, and then I would pass a custom comparator to the std::priority_queue comparing only by the first values in the pair (which was the actual key for the std::multimap).
As everything is quite templated, I .. got quite lost and need help. I made an example code:
The example with std::multimap
template <typename Compare>
void littleTestFunction(Compare comp){
std::multimap<int,int,Compare> testMap(comp);
testMap.insert(std::make_pair(1,5));
testMap.insert(std::make_pair(1,6));
testMap.insert(std::make_pair(2,7));
for (; !testMap.empty(); ){
std::cout << testMap.begin()->second << std::endl;
testMap.erase(testMap.begin());
}
return;
}
int main(void){
littleTestFunction(std::less<int>());
}
My attempt of transforming the std::multimap to std::priority_queue
template <typename Compare>
class pqcomparison{
private:
Compare myComp;
public:
pqcomparison(Compare &cmp){
myComp = cmp;
}
bool operator() (const std::pair<int, int> &lhs,
const std::pair<int, int> &rhs){
return myComp(rhs.first, lhs.first);
}
};
template <typename Compare>
void littleTestFunction(Compare comp){
std::priority_queue<std::pair<int, int>,
std::vector<std::pair<int, int> >,
pqcomparison<Compare> >
mypq(pqcomparison<Compare>(comp));
mypq.push(std::make_pair(1,5));
mypq.push(std::make_pair(1,6));
mypq.push(std::make_pair(2,7));
for (; !mypq.empty(); ){
std::cout << mypq.top().second << std::endl;
mypq.pop();
}
return;
}
When I compile just the std::priority_queue declaration, I don't get any errors. But, when I try and compile the whole function, I get error messages regarding all the member functions of std::priority_queue.
Could somebody please suggest a solution?
