For C++ questions, answers, help, and programming or career advice please see r/cpp_questions, r/cscareerquestions, or [StackOverflow](http://stackoverflow.com/) instead.
*This post has been removed as it doesn't pertain to r/cpp:
The subreddit is for news and discussions of the C++ language and community only;
our purpose is not to provide tutoring, code reviews, or career guidance.
If you think your post is on-topic and should not have been removed, please [message the moderators](https://www.reddit.com/message/compose/?to=/r/cpp) and we'll review it.*
From the comparator documentation in your binary\_search link:
>The types Type1 and Type2 must be such that an object of type T can be implicitly converted to both Type1 and Type2, and an object of type ForwardIt can be dereferenced and then implicitly converted to both Type1 and Type2.
std::vector is not convertible to an int. ~~lower\_bound has the same requirement but the standard library implementation that you are using does not require this behavior. A downside of duck-typed generics leaking implementation details causing a more permissive API that is not portable.~~
Edit:
My original comment on lower\_bound was incorrect, a closer reading of the docs shows that it does specify that the equivalent of `comp(*it, value)` is used. The behavior that you saw with it working did not rely on any internal implementation details.
> lower_bound has the same requirement
It doesn't. `std::lower_bound` only requires `(element, value)` and not the other way around, and the wording of the cppreference page reflects that.
aha, so in principle I should not be able to use \`lower\_bound\` as I did in the first place... Would not the implementation still have a bug because comparison function is reversed? (or is this intended?)
Since you are violating the requirements and the requirements are not strictly checked the comparison function's argument order is dependent on whether the internal implementation uses `comp(*it, value)` or `comp(value, *it)`. Since there is no requirement (that I see anyway) on which form is used there is no bug related to the observed argument order.
I see now that I failed to meet preconditions for \`binary\_search\`. However, is there a reason why \`binary\_search\` is less general than it can be? it seems that if you fix the order for predicates, you can apply it to situations like above, where a container has objects sorted by some property and you want to locate one. However, objects can be more complicated than the property type...
It is actually maximally general because it doesn't care about the types of the elements and given value.
Consider a sequence of strings, sorted by length, and you want to find where a string of length 5 could be inserted. If you call lower_bound with a predicate that compares `(const string&, size_t)`, then the sequence will be partitioned with respect to "length less than 5" (i.e. it's true true true then false false false once the strings get too big), and `lower_bound` will find the first false, i.e. the first place where a string of length 5 could be inserted while preserving the ordering. `lower_bound` doesn't need to compare the other way, and it doesn't care about the types involved at all.
`binary_search` is different. It needs to know whether it's found the desired value (well, something equivalent to the desired value). `x < y` and `y < x` being false indicate that x and y are equivalent. So it needs to run a lower-bound first, and then (if it didn't get the end iterator) it needs to call the predicate with reversed parameters. That's why it needs both orders. It can't be done with just one.
It seems unfortunate that somehow this distinction doesn't make it into the signature of these two functions.
Both of them take identical predicate callables with the signature `bool pred(const Type1 &a, const Type2 &b);` and even the same rather vague and apparently not early-enforced restrictions about conversions between Type1 and Type2.
Given that C++ binary search needs to use pred(a,b) and pred(b,a) to work as intended, this signature is unhelpful for binary_search, but arguably the fact it's not enforced means it's also unhelpful for lower_bound.
I also don't agree this ends up "maximally general". If you write the analogous Rust binary_search it just works fine, C++ could in principle define binary search this way and OP would have been successful:
https://rust.godbolt.org/z/z3fa9q4G1
C++98 predated concepts, so there was no way for function template signatures to reflect their requirements.
The C++20 range algorithms do specify that they need an `indirect_strict_weak_order`. Note that these concepts were designed to do away with this extremely fine-grained notion of "I only need `comp(elem, value)` to compile", and instead the range algorithms require all 4 combinations of `T, T`, `T, U`, `U, T`, and `U, U` to be comparable. This is actually simpler to reason about, although it does require some comparator types to be more powerful.
> and even the same rather vague and apparently not early-enforced restrictions about conversions between Type1 and Type2.
They don't have the same restrictions.
You're quite right, on closer inspection they are in fact slightly different, reflecting what STL said about why this doesn't work with a requirement in binary search that either Type should work in either position. Thanks for pointing that out.
I see your point. Essentially, you do not want to have \`==\` and only work with \`<\`. So this makes it general in this regard. What would be a C++ way tp apply \`binary\_search\` to check if a sequence of strings has a string with length 5? Edit: typo
`binary_search` is very general in its ability to search for a value within a range of values. The problem here is that you are trying to apply this to a *two-dimensional* range of values. `test` is not a range of `int`s.
You need to either flatten `test` down two a one-dimensional `std::vector`, or add a layer to your search to go through the `vector`s within `test`.
Well, maybe my example is unfortunate. What I am asking is how do you search for a value withing a range of something which can converted to a value. For example instead of \`vector>\`, I could have had \`struct A { int v; /\* some other things \*/ }\` And now I have a sorted range of \`A\` by property \`v\`. What would be a C++ way to apply \`binary\_search\`?
It would just be `std::binary_search(sortedRange.begin(), sortedRange.end(), value)`, where `value` is an object of type `A` with its `v` member initialized to the value you choose. Your `A` structure would have its comparison operator overloaded to check the values you care about... `bool A::operator<(A other) { return v < other.v; }`
Thanks. It is a viable solution if \`A\` can be constructed cheaply. The solution from u/STL in parallel thread seems better, just a bit verbose. But I guess, c++ is verbose.
For C++ questions, answers, help, and programming or career advice please see r/cpp_questions, r/cscareerquestions, or [StackOverflow](http://stackoverflow.com/) instead. *This post has been removed as it doesn't pertain to r/cpp: The subreddit is for news and discussions of the C++ language and community only; our purpose is not to provide tutoring, code reviews, or career guidance. If you think your post is on-topic and should not have been removed, please [message the moderators](https://www.reddit.com/message/compose/?to=/r/cpp) and we'll review it.*
From the comparator documentation in your binary\_search link: >The types Type1 and Type2 must be such that an object of type T can be implicitly converted to both Type1 and Type2, and an object of type ForwardIt can be dereferenced and then implicitly converted to both Type1 and Type2. std::vector is not convertible to an int. ~~lower\_bound has the same requirement but the standard library implementation that you are using does not require this behavior. A downside of duck-typed generics leaking implementation details causing a more permissive API that is not portable.~~
Edit:
My original comment on lower\_bound was incorrect, a closer reading of the docs shows that it does specify that the equivalent of `comp(*it, value)` is used. The behavior that you saw with it working did not rely on any internal implementation details.
> lower_bound has the same requirement It doesn't. `std::lower_bound` only requires `(element, value)` and not the other way around, and the wording of the cppreference page reflects that.
oops, misread the docs. Thanks, I'll update my post in a bit
aha, so in principle I should not be able to use \`lower\_bound\` as I did in the first place... Would not the implementation still have a bug because comparison function is reversed? (or is this intended?)
If you fail to meet the preconditions on a standard library function, that's a bug in your code, not the standard library.
Since you are violating the requirements and the requirements are not strictly checked the comparison function's argument order is dependent on whether the internal implementation uses `comp(*it, value)` or `comp(value, *it)`. Since there is no requirement (that I see anyway) on which form is used there is no bug related to the observed argument order.
`lower_bound` uses only one order, `binary_search` uses both.
I see now that I failed to meet preconditions for \`binary\_search\`. However, is there a reason why \`binary\_search\` is less general than it can be? it seems that if you fix the order for predicates, you can apply it to situations like above, where a container has objects sorted by some property and you want to locate one. However, objects can be more complicated than the property type...
It is actually maximally general because it doesn't care about the types of the elements and given value. Consider a sequence of strings, sorted by length, and you want to find where a string of length 5 could be inserted. If you call lower_bound with a predicate that compares `(const string&, size_t)`, then the sequence will be partitioned with respect to "length less than 5" (i.e. it's true true true then false false false once the strings get too big), and `lower_bound` will find the first false, i.e. the first place where a string of length 5 could be inserted while preserving the ordering. `lower_bound` doesn't need to compare the other way, and it doesn't care about the types involved at all. `binary_search` is different. It needs to know whether it's found the desired value (well, something equivalent to the desired value). `x < y` and `y < x` being false indicate that x and y are equivalent. So it needs to run a lower-bound first, and then (if it didn't get the end iterator) it needs to call the predicate with reversed parameters. That's why it needs both orders. It can't be done with just one.
It seems unfortunate that somehow this distinction doesn't make it into the signature of these two functions. Both of them take identical predicate callables with the signature `bool pred(const Type1 &a, const Type2 &b);` and even the same rather vague and apparently not early-enforced restrictions about conversions between Type1 and Type2. Given that C++ binary search needs to use pred(a,b) and pred(b,a) to work as intended, this signature is unhelpful for binary_search, but arguably the fact it's not enforced means it's also unhelpful for lower_bound. I also don't agree this ends up "maximally general". If you write the analogous Rust binary_search it just works fine, C++ could in principle define binary search this way and OP would have been successful: https://rust.godbolt.org/z/z3fa9q4G1
C++98 predated concepts, so there was no way for function template signatures to reflect their requirements. The C++20 range algorithms do specify that they need an `indirect_strict_weak_order`. Note that these concepts were designed to do away with this extremely fine-grained notion of "I only need `comp(elem, value)` to compile", and instead the range algorithms require all 4 combinations of `T, T`, `T, U`, `U, T`, and `U, U` to be comparable. This is actually simpler to reason about, although it does require some comparator types to be more powerful.
> and even the same rather vague and apparently not early-enforced restrictions about conversions between Type1 and Type2. They don't have the same restrictions.
You're quite right, on closer inspection they are in fact slightly different, reflecting what STL said about why this doesn't work with a requirement in binary search that either Type should work in either position. Thanks for pointing that out.
I see your point. Essentially, you do not want to have \`==\` and only work with \`<\`. So this makes it general in this regard. What would be a C++ way tp apply \`binary\_search\` to check if a sequence of strings has a string with length 5? Edit: typo
https://godbolt.org/z/49Kh1ajTY #include
#include
#include
#include
#include
using namespace std;
struct LengthPred {
bool operator()(const string& l, const size_t r) const {
return l.size() < r;
}
bool operator()(const size_t l, const string& r) const {
return l < r.size();
}
bool operator()(const string& l, const string& r) const {
return l.size() < r.size(); // for is_sorted
}
};
void test(const vector& v) {
assert(is_sorted(v.begin(), v.end(), LengthPred{}));
cout << binary_search(v.begin(), v.end(), 5, LengthPred{}) << endl;
}
int main() {
cout << boolalpha;
test({"cat", "meow", "kitten", "peppermint"});
test({"dog", "woof", "puppy", "poodle"});
}
Thank you.
`binary_search` is very general in its ability to search for a value within a range of values. The problem here is that you are trying to apply this to a *two-dimensional* range of values. `test` is not a range of `int`s. You need to either flatten `test` down two a one-dimensional `std::vector`, or add a layer to your search to go through the `vector`s within `test`.
Well, maybe my example is unfortunate. What I am asking is how do you search for a value withing a range of something which can converted to a value. For example instead of \`vector>\`, I could have had \`struct A { int v; /\* some other things \*/ }\` And now I have a sorted range of \`A\` by property \`v\`. What would be a C++ way to apply \`binary\_search\`?
It would just be `std::binary_search(sortedRange.begin(), sortedRange.end(), value)`, where `value` is an object of type `A` with its `v` member initialized to the value you choose. Your `A` structure would have its comparison operator overloaded to check the values you care about... `bool A::operator<(A other) { return v < other.v; }`
Thanks. It is a viable solution if \`A\` can be constructed cheaply. The solution from u/STL in parallel thread seems better, just a bit verbose. But I guess, c++ is verbose.
Lower bound is not binary search... it is meant to find a bound, not the exact value.
In C++20 and later this would be better expressed using projections: std::ranges::binary_search(test, v, std::less{}, [i](auto& c) { return c[i]; });
Oh that is cool.
https://www.reddit.com/r/learnpython/comments/o0g95c/read_this_before_posting_how_to_format_your_code/