There is a correctly working pattern for finding a range of lines in the vector that start with a specific character.

template <typename RandomIt> std::pair<RandomIt, RandomIt> FindStartsWith( RandomIt range_begin, RandomIt range_end, char prefix) { std::string target1 = {prefix}; auto first = std::lower_bound(range_begin, range_end, target1); auto next = static_cast<char>(prefix + 1); std::string target2 = {next}; auto last = std::upper_bound(range_begin, range_end, target2); return std::make_pair(first, last); };

The prefix string option gives incorrect results. Tell me what could be the error.

 template <typename RandomIt> std::pair<RandomIt, RandomIt> FindStartsWith( RandomIt range_begin, RandomIt range_end, const std::string& prefix) { std::string target = prefix; auto first = std::lower_bound(range_begin, range_end, target); ++target[prefix.size() - 1]; auto last = std::upper_bound(range_begin, range_end, target); return std::make_pair(first, last); };

    2 answers 2

    And what would you not use the standard equal_range with the corresponding predicate? Something like

     #include <vector> #include <string> #include <algorithm> #include <iostream> #include <iomanip> using namespace std; vector<string> v{ "abvsd","hdvjh","hvdsg","dvass","dvahj","dv","dvar","dvb","jhkfb"}; template <typename RandomIt> std::pair<RandomIt, RandomIt> FindStartsWith(RandomIt range_begin, RandomIt range_end, const std::string& prefix) { return std::equal_range(range_begin,range_end,prefix, [&prefix](const std::string& a,const std::string& b) { return a.compare(0,prefix.length(),b.substr(0,prefix.length())) < 0; }); } int main(int argc, const char * argv[]) { sort(v.begin(),v.end()); auto f = FindStartsWith(v.begin(),v.end(),"dva"); for(auto i = f.first; i != f.second; ++i) cout << *i << endl; }
    • I tried the option with equal_range, but since I'm just starting to learn from ++ having problems with the correct predicate. so I tried to solve it head-on using lower_bound and upper_bound. Your option works great, thanks. - avtomato

    The idea is correct, but your original template has never been "correctly working", as you can easily see by searching for strings beginning with 'a' in the sequence

     { "a", "ab", "b", "bc" }

    If you want to apply an idiomatic method with increasing the desired value "slightly", then you should look for the end of the sequence after such an increase through std::lower_bound , and not through std::upper_bound like yours. Those. In your original version, both calls should be exactly std::lower_bound .

    The same applies to your second option. The idea is absolutely correct and everything will work fine (if you exclude the possibility of overflow), if you call std::lower_bound in the second case. That's all you need to fix.

    And, additionally, if you know that you obviously will copy the parameter inside the function, then it is better to pass it immediately by value (this will allow the compiler to generate more optimal code if the argument is a temporary value)

     template <typename RandomIt> std::pair<RandomIt, RandomIt> FindStartsWith( RandomIt range_begin, RandomIt range_end, std::string prefix) { auto first = std::lower_bound(range_begin, range_end, prefix); ++prefix.back(); auto last = std::lower_bound(range_begin, range_end, prefix); return { first, last }; }

    It remains only to note that the second search can be started from the iterator first already found, and not from the beginning of the original range ...

    • Yes, I have already noticed that the search for the second end of the half-interval should be started with a value not less than ++ prefix.back (), and I get it from strictly more. Thanks for the tip. - avtomato