Найти равный диапазон для контейнера со строкой с префиксом

Question

У меня есть 2 итератора range_begin,range_end, которые являются моим контейнером. Мне нужно найти все строки, которые начинаются с префикса char. Вот мой код:

template <typename RandomIt>
pair<RandomIt, RandomIt> FindStartsWith(
RandomIt range_begin, RandomIt 
range_end,char prefix){
auto it=equal_range(range_begin,range_end,prefix,
[prefix](const string& city){return city[0]==prefix;});
return it;}

Например, для

const vector<string> sorted_strings = {"moscow", "murmansk", "vologda"};
auto it=FindStartsWith(strings.begin(),strings.end(),'m');

Я хочу получить итератор с первым на "москве" и последним после "мурманска".

Я получаю странные ошибки компилятора. Что не так и как я могу это решить? Я не могу написать правильный лямбда-компоратор.

Answer 1

Ваши ошибки могут быть связаны с strings.begin() и.end(), которые не имеют sorted_. Я не думаю, что вы также должны использовать шаблон. Помимо ошибок, я рекомендую использовать другую стандартную функцию. Более простое решение - использовать foreach:

#include <algorithm>
#include <iterator>
#include <list>
#include <string>
#include <utility>
#include <vector>

typedef std::vector<std::string>::const_iterator RandomIt;

std::vector<std::string> FindStartsWith(RandomIt start, RandomIt end, const char prefix) {
    std::vector<std::string> result;

    std::for_each(start, end, [&](auto city) {
        if (city.front() == prefix) {
          result.push_back(city);
        }
    });

    return result;
}

int main(int argc, char* argv[]) {
    const std::vector<std::string> sorted_strings = { "moscow", "murmansk", "vologda" };
    auto prefix_cities = FindStartsWith(sorted_strings.begin(), sorted_strings.end(), 'm');

    return 0;
}

Определенно можно использовать рефакторинг, но я предполагаю, что вам нужно реализовать его в FindStartsWith по какой-то другой причине...

Спасибо за публикацию, это многому научило меня по equal_range:)

Answer 2

equal_range ожидает функцию сравнения, которая принимает два параметра; Вы передаете функцию, взяв одну.

Разнородный вызов (тот, где тип value не совпадает с элементами типа в диапазоне) требует функции сравнения, которая может принимать два типа в любом порядке. Лямбда не будет работать в этом случае, поскольку она имеет только один operator() перегрузки.

Наконец, функция должна выполнять сравнение с типом меньше, а не равным. Грубо говоря, equal_range возвращает диапазон от первого элемента, для которого !(element < value) к первому элементу, для которого value < element,

Answer 3

ОТВЕЧАТЬ:

Причина вашей ошибки компиляции скрыта в реализациях компараторов в двух функциях "lower_bound" и "upper_bound", которые вызываются из основной функции "equal_range".

1. EQUAL_RANGE

           template<class ForwardIt, class T, class Compare>
   pair<ForwardIt,ForwardIt> 
       equal_range(ForwardIt first, ForwardIt last,
                   const T& value, Compare comp)
   {
       return make_pair(lower_bound(first, last, value, comp),
                             upper_bound(first, last, value, comp));
   }
   

Обратите внимание на то, как компаратор вызывается в каждой функции. Посмотрите, что компараторы вызываются разными последовательностями аргументов, и это является причиной ошибки.

2. НИЖНЯЯ_ГРАНИЦА :

           if (comp(*it, value))
   

3. ВЕРХНЯЯ_ГРАНИЦА :

           if (!comp(value, *it))
   

ДОПОЛНИТЕЛЬНАЯ ИНФОРМАЦИЯ

Ниже я скопировал пример реализации двух функций соответственно.

НИЖНЯЯ ГРАНИЦА:

      ```
template<class ForwardIt, class T, class Compare>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
    ForwardIt it;
    typename std::iterator_traits<ForwardIt>::difference_type count, step;
    count = std::distance(first, last);
 
    while (count > 0) {
        it = first;
        step = count / 2;
        std::advance(it, step);
        if (comp(*it, value)) {
            first = ++it;
            count -= step + 1;
        }
        else
            count = step;
    }
    return first;
}
```

ВЕРХНЯЯ ГРАНИЦА:

      ```
template<class ForwardIt, class T, class Compare>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
    ForwardIt it;
    typename std::iterator_traits<ForwardIt>::difference_type count, step;
    count = std::distance(first, last);
 
    while (count > 0) {
        it = first; 
        step = count / 2;
        std::advance(it, step);
        if (!comp(value, *it)) {
            first = ++it;
            count -= step + 1;
        } 
        else
            count = step;
    }
    return first;
}
```

РЕШЕНИЕ

У вас есть два способа решить эту проблему (может быть, больше).

1. Напишите два компаратора для каждой функции и вызывайте друг друга по отдельности.
2. Преобразуйте аргумент char в строку , напишите компаратор для строк и вызовите equal_range.