c++ - 使用 std::equal_range 查找出现在字符串 vector 中的前缀范围

Question

我正在尝试提出一个 lambda，它允许 std::equal_range 返回一个范围，其中搜索的字符串作为前缀存在。由于这可能措辞不正确，例如:

给定字符串 vector :

• C:\users\andy\documents\screenshot.jpg
• C:\users\bob\desktop\file.txt
• C:\users\bob\desktop\picture.png
• C:\users\bob\desktop\video.mp4
• C:\users\john\desktop\note.txt

我希望返回的迭代器是

• C:\users\bob\desktop\file.txt 和
• C:\users\bob\desktop\video.mp4。

我如何为 std::equal_range 编写一个比较 lambda 来完成这个，或者 std::equal_range 不是完成这项工作的正确工具？

Answer 1

我认为您只需要让比较器 只比较前缀的长度和这样的元素:

std::vector<std::string> v
{
    "C:/users/andy/documents/screenshot.jpg",
    "C:/users/bob/desktop/file.txt",
    "C:/users/bob/desktop/picture.png",
    "C:/users/bob/desktop/video.mp4",
    "C:/users/john/desktop/note.txt",
};

std::sort(std::begin(v), std::end(v));

std::string const prefix = "C:/users/bob/desktop/";

auto lb = std::lower_bound(std::begin(v), std::end(v), prefix);

// For the upper bound we want to view the vector's data as if
// every element was truncated to the size of the prefix.
// Then perform a normal match.
auto ub = std::upper_bound(lb, std::end(v), prefix,
[&](std::string const& s1, std::string const& s2)
{
    // compare UP TO the length of the prefix and no farther
    if(auto cmp = std::strncmp(s1.data(), s2.data(), prefix.size()))
        return cmp < 0;

    // The strings are equal to the length of the prefix so
    // behave as if they are equal. That means s1 < s2 == false
    return false;
});

// make the answer look like we used std::equal_range
// (if that's what's needed)
auto range = std::make_pair(lb, ub);

for(auto itr = range.first; itr != range.second; ++itr)
    std::cout << *itr << '\n';

输出:

C:/users/bob/desktop/file.txt
C:/users/bob/desktop/picture.png
C:/users/bob/desktop/video.mp4

为了解释为什么这行得通，想象一下获取 vector 并对它进行排序。然后想象访问每个元素并将它们截断到前缀的长度。您将得到一个已排序的 vector ，其中的元素都不长于前缀。那时一个简单的 std::equal_range 就可以满足您的要求。因此，我们需要做的就是构造一个比较器，其行为就好像容器元素已被截断为前缀的长度，并在我们的 中使用该比较器std::equal_range 搜索(或孪生 std::lower_bound/upper_bound 搜索)。