查找具有前缀字符串的容器的相等范围

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');

我想得到第一个在 "moscow" 上最后一个在 "murmansk" 之后的迭代器。

我遇到了奇怪的编译器错误。出了什么问题，我该如何解决？我无法编写正确的 lambda comporator。

Answer 1

equal_range 需要一个带有两个参数的比较函数；你正在传递一个带一个的函数。

异构调用（value 的类型与范围中的类型元素不同的调用）需要一个比较函数，该函数可以按任意顺序获取两种类型。 lambda 在这种情况下不起作用，因为它只有一个 operator() 重载。

最后，该函数必须执行小于类型的比较，而不是等于类型的比较。粗略地说，equal_range returns 从 !(element < value) 的第一个元素到 value < element.

的第一个元素的范围

Answer 2

您的错误可能是由于 strings.begin() 和 .end() 没有 sorted_。我认为您也不应该使用模板。除了错误，我建议您使用不同的 std 函数。一个更简单的解决方案是使用 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 3

答案：

编译错误的原因隐藏在从主函数“equal_range”调用的两个函数“lower_bound”和“upper_bound”中比较器的实现中。

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));
}

注意各个函数中比较器是如何产生的。看看比较器是由不同的参数序列引起的，这就是错误的原因。

LOWER_BOUND:
```
if (comp(*it, value))
```
UPPER_BOUND:
```
if (!comp(value, *it))
```

其他信息

下面我相应地复制了两个函数的实现示例

LOWER_BOUND:

```
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;
}
```

UPPER_BOUND:

```
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;
}
```

解决方案

你有两种方法来解决这个问题（也许更多）。

每个函数写两个比较器，分别调用。
将 char 参数转换为 string，为字符串编写比较器并调用 equal_range.

查找具有前缀字符串的容器的相等范围

Find equal range for container with string with prefix

c++

iterator

vector

equal-range