如何使用带有特定构造函数的STL优先队列+比较器？

Question

我希望能够做到这一点：

#include <queue>
#include <set>

class Comparator
{
   public:
   Comparator(SomeObject& rTool) : mrTools(rTool) {}

   bool operator()(const std::string& a, const std::string& b)
   {
      return mrTools.doSomething(a,b);
   }

   private:
   SomeObject& mrTools;
}

std::priority_queue<std::string, std::set<std::string>, Comparator> queue; 
//<- this doesn't compile

我该如何初始化这个队列并在构造函数中提供给比较器所需要的引用？

- angelo.mastro

Answer 1

您可以提供一个Comparator实例来构建它；否则，将使用Comparator()作为std::priority_queue构造函数的默认参数，但是Comparator没有默认构造函数。例如：

SomeObject so;
std::priority_queue<std::string, std::set<std::string>, Comparator> queue(Comparator(so)); 

顺带一提：std::set 不满足 std::priority_queue 底层容器的要求。你可以使用 std::vector 或者 std::deque 代替。

用于存储元素的底层容器类型。该容器必须满足 SequenceContainer 的要求，其迭代器必须满足 RandomAccessIterator 的要求。此外，它必须提供以下具有通常语义的函数：

• front()
• push_back()
• pop_back()

标准容器 std::vector 和 std::deque 满足这些要求。

- songyuanyao

---

“priority_queue” 的功能比 “set” 少。唯一（但可能非常好的）选择 “priority_queue” 的原因是效率。 - Arne Vogel

Answer 2

这与你的Comparator无关，而与std::set不满足SequenceContainer的要求有关。您可以使用vector或deque，或编写自己的SequenceContainer，确保实现front，push_back和pop_back，并拥有RandomAccessIterator的iterator。

- Caleth