在 std::map 中查找具有给定前缀的键或在 std::set 中查找元素的优雅方法

Question

我有地图，键是std::string。我想在地图中找到那些以 "DUPA/" 前缀开头的元素。找到下界很容易，但上界有点问题。我写了这样一段代码：

const char* prefix = "DUPA/";
const char* firstAfterPrefix = "DUPA0";
auto prefixedBeginIt = myMap.upper_bound(prefix);
auto prefixedEndIt = myMap.lower_bound(firstAfterPrefix);

代码工作正常，但我认为它不够优雅，因为必须知道 0 在 ASCII table 中紧挨着 /。第二种方法是复制前缀并增加最后一个符号。你知道更优雅的解决方案吗？

Answer 1

我觉得你说的方案已经是最优雅的了。 KISS方式损失了很多性能，即每次都要检查key：

while(prefixedBeginIt->first == prefix)
{
 //...
 ++prefixedBeginIt;
}

因此我认为计算下一个字符是最好的方法：

std::string firstAfterPrefix = prefix;
++firstAfterPrefix[firstAfterPrefix.length() - 1];
auto prefixedEndIt = myMap.lower_bound(firstAfterPrefix);

Answer 2

如果您可以假设 CHAR_MAX 不是字符串中的有效字符，那么您可以通过附加 CHAR_MAX（或您的字符类型的最大值）来创建 firstAfterPrefix如果不是 char).

std::string prefix = "DUPA/";

constexpr auto char_max = std::numeric_limits<decltype(prefix)::value_type>::max();
std::string firstAfterPrefix = prefix + char_max;

auto prefixedBeginIt = myMap.lower_bound(prefix);
auto prefixedEndIt = myMap.lower_bound(firstAfterPrefix);

请注意对两个边界使用 lower_bound。和 Gill 一样，我使用 std::string 来简化说明。

如果您可以使用 C++14 并指定容器的 Compare 模板参数，那么另一种方法是使用自定义探测对象：

struct PrefixProbe { std::string_view prefix; };
bool operator<(PrefixProbe a, std::string_view b) { return a.prefix < b.substr(0, a.prefix.size()); }
bool operator<(std::string_view a, PrefixProbe b) { return a.substr(0, b.prefix.size()) < b.prefix; }

std::map<std::string, myValue, std::less<>> myMap;
//                             ^~~~~~~~~~~
//                             where the magic happens

auto prefixBegin = myMap.lower_bound(PrefixProbe { prefix });
auto prefixEnd = myMap.upper_bound(PrefixProbe { prefix });

std::string_view 是 C++17，但不需要完成这项工作。

equal_range 会将最后两行缩减为一行：

auto [ prefixBegin, prefixEnd ] = myMap.equal_range(PrefixProbe { prefix });

如果您准备使用 STL 算法而不是容器成员函数，则可以在不更改容器类型的情况下完成此操作，但效率较低：

auto prefixBegin = std::lower_bound(cbegin(myMap), cend(myMap), PrefixProbe { prefix }, std::less<>{});
auto prefixEnd = std::upper_bound(cbegin(myMap), cend(myMap), PrefixProbe { prefix }, std::less<>{});

auto [ prefixBegin, prefixEnd ] = std::equal_range(cbegin(myMap), cend(myMap), PrefixProbe { prefix }, std::less<>{});

在 std::map 中查找具有给定前缀的键或在 std::set 中查找元素的优雅方法

Elegant way to find keys with given prefix in std::map or elements in std::set

c++

stdmap

prefix

stdset