Geek Answers Handbook

Idiomatic C ++ to find a range of strings of equal length given by a row vector (sorted by length)

given std::vector< std::string > , the vector is ordered by the length of the string, how can I find a range of the same length?

I am looking forward to an idiomatic solution in C ++.

I found this solution:

 // any idea for a better name? (English is not my mother tongue) bool less_length( const std::string& lhs, const std::string& rhs ) { return lhs.length() < rhs.length(); } std::vector< std::string > words; words.push_back("ape"); words.push_back("cat"); words.push_back("dog"); words.push_back("camel"); size_t length = 3; // this will give a range from "ape" to "dog" (included): std::equal_range( words.begin(), words.end(), std::string( length, 'a' ), less_length );

Is there a standard way to do this (beautifully)?

+4
source share
3 answers

I expect you can write a comparator like this:

 struct LengthComparator { bool operator()(const std::string &lhs, std::string::size_type rhs) { return lhs.size() < rhs; } bool operator()(std::string::size_type lhs, const std::string &rhs) { return lhs < rhs.size(); } bool operator()(const std::string &lhs, const std::string &rhs) { return lhs.size() < rhs.size(); } };

Then use it:

 std::equal_range(words.begin(), words.end(), length, LengthComparator());

I expect the third operator() overload to never be used, as the information it provides is redundant. The range must be pre-sorted, so there is no algorithm for comparing two elements from a range, it should be a comparison of elements from a range against the target that you set. But the standard does not guarantee this. [Edit: and the definition of all three means, you can use the same comparator class to first put the vector in order, which can be convenient].

This works for me (gcc 4.3.4), and although I think it will work on your implementation too, I'm not sure if it really is valid. It implements the comparisons that will be described in the equal_range description, and the result of 25.3.3 / 1 does not require that the template parameter T be exactly the same type of objects referenced by iterators. But there may be some text that I skipped that adds more restrictions, so I would do more standard trawling before using it in something important.

+5
source

Your path is definitely not uniomatic, but the need to create a dummy string with a target length does not look very elegant, and it is also not very readable.

I would probably write my own helper function (i.e. string_length_range ), encapsulating a simple, simple loop through a list of strings. There is no need to use std:: tools for everything.

+2
source

std::equal_range performs a binary search. This means that the words vector must be sorted, which in this case means that it must be non-decreasing in length.

I think that your solution is good, certainly better than writing your own binary search implementation, which, as you know, is error prone and difficult to justify.

If binary search weren’t your intention, I agree with Alexander. Just a simple cycle through words is the purest.

0
source

More articles:


All Articles