std :: equal_range с лямбдой
Допустим, у меня есть вектор строк, и я хочу найти все строки, которые начинаются с '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() во втором методе) и имеет дублирование кода.
Так можно ли реализовать функцию сравнения с общей лямбда вместо структуры с 2 методами?
Более общий вопрос, почему значение для сравнения должно быть передано в качестве аргумента std::lower_bound, std::upper_bound а также std::equal_range когда он может быть легко перехвачен лямбдой или передан в структуру сравнения, и тогда эта проблема вообще не возникнет?
Как это может работать, если 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'} );
Решение
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(); });
Другие решения
Чтобы ответить на ваш первый вопрос, может ли компаратор быть реализован с использованием общей лямбды, да, это возможно. Вам также понадобится пара вспомогательных функций, чтобы вернуть желаемый результат, учитывая char или же string аргумент.
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); };
Одна из причин, по которой компаратор не может просто захватить значение, заключается в том, что две перегрузки equal_range затем может быть неоднозначным, вам понадобится немного другое имя или какой-либо другой способ (например, аргумент тега) для устранения неоднозначности.