c++ - 用于排序/检索字符串的数据结构

Question

我有多个字符串数组，我使用比较函数将它们排序到优先队列中。我忽略了我需要遍历字符串的事实..

您会推荐什么其他数据结构？也许允许比较函数的东西，以便我得到一组排序的字符串

我可以有效地从优先队列中弹出元素，但这意味着在将它们推回优先队列之前我需要辅助空间

如果 vector 允许比较函数，那将是理想的。 STL“集合”会起作用吗？我有固定数量的元素(大约 450 个)。

编辑:确认 STL 的集合正在工作..即使没有定义我自己的字符串比较函数。

Answer 1

我不太确定你需要什么。我假设“我需要遍历字符串”意味着你需要以未排序的顺序遍历剩余的(不是“弹出”)字符串，此外还需要使用优先级队列(通过“弹出”)访问它们.如果您需要迭代排序序列，您应该预先对输入字符串进行排序(例如通过 std::set)而不是使用优先级队列(优先级队列不一定完全排序所有的项目，它排序序列“按需”)。

std::priority_queue 使用底层容器(默认为 std::vector)。通过继承此类，您可以访问容器。 protected member variable is defined in the standard ，这在理论上应该是安全的(尽管不要打赌它在现实生活中)。然而，inheriting STL containers is frowned upon .

另一种方法是创建您自己的优先级队列，例如基于 std::vector 和 std::make_heap , std::pop_heap和 std::push_heap . std::priority_queue 在内部使用这些函数。