Find equal range for container with string with prefix

Question

I am having 2 iterators range_begin,range_end, which are my container. I need to find all string which start with char prefix. Here is my code:

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

For example, for

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

I want to get iterator with first on "moscow" and last after "murmansk".

I am getting strange compilier errors. What is wrong and how can I solve this?I cannot write correct lambda comporator.

Answer 1

Your errors might be due to strings.begin() and .end() which do not have sorted_. I do not think you should use a template either. Errors aside, I recommend you use a different std function. A simpler solution is to use 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;
}

Definitely could use a refactor, but I'm assuming you need to implement it in the FindStartsWith for some other reason...

Thanks for posting, this taught me a lot about equal_range :)

Answer 2

ANSWER:

The reason for your compile error is hidden in the implementations of comparators in two functions "lower_bound" and "upper_bound" which call from the main function "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));
   }
   

Make attention to how the comparator is caused in each function. Look that comparators are caused by different sequences of arguments and this is the reason for the error.

2. LOWER_BOUND:

   if (comp(*it, value))
   

3. UPPER_BOUND:

   if (!comp(value, *it))
   

ADDITIONAL INFOMATION

Below I copied an example of implementations of two functions accordingly.

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

SOLUTION

You have two ways to solve this problem (maybe more).

1. Write two comparators for each function and call each other separatively.
2. Convert char argument to string, write comparator for strings and call equal_range.

Answer 3

equal_range expects a comparison function that takes two parameters; you are passing a function taking one.

A heterogeneous call (one where the type of value is not the same as the type elements in the range) requires a comparison function that can take the two types in either order. A lambda won't work in this case as it only has one operator() overload.

Finally, the function must perform a less-than type of comparison, not an equals one. Roughly, equal_range returns a range from the first element for which !(element < value) to the first element for which value < element.