priority_queue 上的二进制搜索（高效插入和搜索大型字符串列表）

Question

我面临着一个巨大的字符串列表 (~50k) 的问题。每个字符串都描述了一个已经考虑过的场景。因此，当出现新场景时，如果其描述已在列表中，则将其丢弃。

我认为显而易见的选择是使用 priority_queue 个字符串来执行 binary_search。（对数插入，对数查找）。

对吗？

嗯，我找不到使用标准 C++ 库的方法。具体来说， priority_queue 似乎没有 .begin() .end() binary_search() 函数的方法。

我不能使用标准库priority_queue+binary_search吗？那还有什么用呢？

谢谢！

编辑 1. 最后经过几次测试，我可以确认这个问题的最佳选择（优于其他）是使用集合及其查找方法。这是：

set<string> consideredOptions; 
...
string newDescription = ....;
if ( consideredOptions.find(newDescription) == consideredOptions.end() ) {
  consideredOptions.insert(newDescription);
}

编辑 2. priority_queue 有一个名为 c 的受保护成员，代表项目列表。然后，使用 .begin() 和 .end().[=13 的方法很容易推导出一个新的 class =]

class MyQueue : public std::priority_queue<std::string> {
 public:
  bool contains (const std::string & what) const {
    return std::find (c.begin(), c.end(), what) != c.end();  
  }
};

Answer 1

Well, I can't find a way to do it using the standard C++ library.

您不需要队列，您只需要一个 collection，您可以在其中高效地插入和执行查找。使用 std::unordered_set。它具有 constant-time 插入和查找功能。

如果您想在事物到达队列的 "front" 时处理它们（通常将它们从队列中移除），则使用队列。根据您的描述，您不需要那个。你只关心东西在collection里不在，你不在乎它们在前面不在

使用 std::set 或 std::unordered_set，您甚至不需要费心进行查找，只需尝试插入每个字符串即可。如果它已经在容器中，那么 return 值将告诉您插入失败。如果它不在容器中，return 值会告诉您它不存在，但会在同一操作中添加它，这比查找然后插入快两倍。

unordered_set<string> consideredOptions; 
...
string newDescription = ....;
if ( consideredOptions.insert(newDescription).second ) {
  // newDescription was not in the set (but is now)
}
else {
  // newDescription was already considered
}

priority_queue 上的二进制搜索（高效插入和搜索大型字符串列表）

Binary search on a priority_queue (efficient insert and search on a large list of strings)

priority-queue

c++11