将std :: multimap转换为std :: priority_queue [英] Transform a std::multimap into std::priority_queue

问题描述

我有一个函数使用 std :: multimap ，这是令人难以置信的，正是因为 std :: multimap 。经过分析，我意识到我只使用 std :: multimap 作为堆，所以我试图用 std :: priority_queue 这只允许堆操作，希望这将更快的使用。

当然， std :: priority_queue 的元素类型需要 std :: pair< mmKey，mmValue> 然后我会传递一个自定义比较器到 std :: priority_queue 只比较的第一个值（这是 std的实际键:: multimap ）。

由于一切都模板化，我失去了需要帮助。我创建了一个示例代码：

std :: multimap p>

 模板< typename比较> 
 void littleTestFunction（比较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（testingMap.begin（））; 
} 
 return; 
} 
 
 int main（void）{
 littleTestFunction（std :: less< int>（））; 
} 
  

我尝试转换 std： ：multimap 到 std :: priority_queue

 code> template< typename Compare> 
 class pqcomparison {
 private：
比较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）; 
} 
}; 
 
模板< typename比较> 
 void littleTestFunction（比较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; 
} 
  

当我只编译 std :: priority_queue 声明，我没有得到任何错误。但是，当我尝试编译整个函数时，我会收到关于 std :: priority_queue 的所有成员函数的错误消息。

有人可以请建议一个解决方案吗？

解决方案

这很好掩盖 most vexing parse case。只是改变这行
std :: priority_queue< std :: pair< int，int>，
std :: vector< std :: pair< int，int& >，
pqcomparison< Compare> >
mypq（pqcomparison< Compare>（comp））;

至：
std :: priority_queue< std :: pair< int，int>，
std :: vector< std :: pair< int，int& >，
pqcomparison< Compare> >请注意，我已经更改了（）
mypq {pqcomparison< Compare>（comp）};



< 与 {} 。如果你不使用C ++ 11，你应该放置额外的括号，即使它 mypq（（pqcomparison< Compare>（comp）））

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?

解决方案

It's quite well masked most vexing parse case. Just change this line std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, pqcomparison<Compare> > mypq(pqcomparison<Compare>(comp));

to: std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, pqcomparison<Compare> > mypq{pqcomparison<Compare>(comp)};

Notice that I have changed () with {}. In case when you are not using C++11 you should just put extra parenthesis, i.e. make it mypq((pqcomparison<Compare>(comp)))

这篇关于将std :: multimap转换为std :: priority_queue的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！