std::equal_range 使用 lambda

Question

假设我有一个字符串向量，我想找到所有以 'a' 开头的字符串，所以我可以这样做：

struct cmp {
    bool operator()( const std::string &s, char c ) const { return s.front() < c; }
    bool operator()( char c, const std::string &s ) const { return s.front() < c; }
};
std::vector<std::string> strings;
...
std::sort( strings.begin(), strings.end() );
auto range = std::equal_range( strings.begin(), strings.end(), 'a', cmp{} );
...

这种方法容易出错，容易出错（比如我觉得第二种方法应该是c < s.front()），代码重复

那么是否可以使用通用 lambda 而不是使用 2 种方法的结构来实现比较函数？

更一般的问题，为什么要比较的值必须作为参数传递给 std::lower_bound、std::upper_bound 和 std::equal_range，而它可以很容易地被 lambda 捕获或传递给比较结构，然后这个问题就完全没有了？

如果 std::equal_range 不需要值，它如何工作？

struct cmp {
    cmp( char lc ) : c( lc ) {}
    bool operator()( const std::string &s ) const { return s.front() < c; }
    char c;
};
std::vector<std::string> strings;
...
std::sort( strings.begin(), strings.end() );
auto range = std::equal_range( strings.begin(), strings.end(), cmp{'a'} );

Answer 1

要回答您的第一个问题，是否可以使用通用 lambda 实现比较器，是的，可以。在给定 char 或 string 参数的情况下，您还需要一些辅助函数来 return 期望的结果。

auto get_char(char c)               { return c; }
auto get_char(std::string const& s) { return s.front(); }
auto cmp = [](auto const& l, auto const& r) { return get_char(l) < get_char(r); };

Live demo

你不能简单地让比较器捕获值的一个原因是 equal_range 的两个重载可能会模棱两可，你需要一个稍微不同的名称或其他方式（例如，一个标签参数）来消除两者的歧义。

Answer 2

lower_bound 是

std::partition_point(strings.begin(), strings.end(),
                     [](const auto& s) { return s.front() < 'a'; });

upper_bound 是

std::partition_point(strings.begin(), strings.end(),
                     [](const auto& s) { return s.front() <= 'a'; });

是的，这意味着您必须编写两个调用才能获得 equal_range 的等价物。您可以将其包装到免费模板中：

template<class Iter, class T, class Proj>
std::pair<Iter, Iter> my_equal_range(Iter first, Iter last, const T& value, Proj proj) {
    auto b = std::partition_point(first, last, [&](const auto& s) { return proj(s) < value; });
    auto e = std::partition_point(b, last, [&](const auto& s) { return !(value < proj(s)); });
    return {b, e};
}

并将其命名为

my_equal_range(strings.begin(), strings.end(), 'a',
               [](const auto& s) { return s.front(); });

Ranges TS 工作草案将预测添加到算法中，因此您（最终）将能够做到这一点：

std::experimental::ranges::equal_range(strings, 'a', {},
                                       [](const auto& s) { return s.front(); });

std::equal_range 使用 lambda

std::equal_range with lambda

c++

lambda

generic-lambda

c++14