I’ve been trying to use std::binary_search
and std::lower_bound
on std::array<unique_ptr<int>>
just to get to grips with it. I was having trouble with the following :
#include <array>
#include <memory>
#include <algorithm>
int main() {
std::array<std::unique_ptr<int>, 3> a = {std::make_unique<int>(1),
std::make_unique<int>(2), std::make_unique<int>(5)};
auto t = std::binary_search(a.begin(), a.end(), 5, []
(std::unique_ptr<int> x, std::unique_ptr<int> y) {
return x.get() < y.get();
});
return 0;
}
I’m trying to put my own comparison here, similar to how it would be done with something like std::sort
. However when compiling this I have an error cannot convert argument 1 from 'const _Ty' to 'std::unique_ptr<int,std::default_delete<int>>'
What should I change to make this work?
EDIT : complete error message from Visual Studio
Severity Code Description Project File Line Suppression State Details
Error C2664 'bool thng_already::<lambda_1>::operator ()(std::unique_ptr<int,std::default_delete<int>>,std::unique_ptr<int,std::default_delete<int>>) const': cannot convert argument 1 from 'const _Ty' to 'std::unique_ptr<int,std::default_delete<int>>'
with
[
_Ty=int
] Proj C:Program FilesMicrosoft Visual Studio2022CommunityVCToolsMSVC14.39.33519includealgorithm 7028
When replacing 5 with std::make_unique<int>(5)
we have a different error
Severity Code Description Project File Line Suppression State Details
Error C2280 'std::unique_ptr<int,std::default_delete<int>>::unique_ptr(const std::unique_ptr<int,std::default_delete<int>> &)': attempting to reference a deleted function Proj C:Program FilesMicrosoft Visual Studio2022CommunityVCToolsMSVC14.39.33519includealgorithm 7028
2
Answers
There are three issues:
Your lambda takes its parameters by value. This implies that the
binary_search
implementation has to copy the arguments when passing them to the lambda. Can you copyunique_ptr
? No. That’s why it’s not working. Take the arguments by const reference instead.The lambda cannot accept
5
as one of its arguments since 5 is not aunique_ptr<int>
You Compare
x.get() < y.get()
.get()
returns the raw pointer to the integer, so you compare pointers, not the values that these pointers point to. I assume you mean*x < *y
to compare the integers insteadFeel free to shorten the lambda declaration to
[](const auto& x, const auto& y)
and rely on type deduction.Avoiding the temporary allocation
Calling
make_unique<int>(5)
does a temporary allocation that is not strictly necessary. To avoid it, we need to augment the comparator to acceptint
andstd::unique_ptr<int>
as its arguments in either order. This is probably the easiest approach to do so:The predicate will be used to compare elements in the array with the to be found value, ie you can think of it like this
Then the algorithm will do something along the line of:
This has two issues:
5
is not astd::unique_ptr<int>
. And you cannot pass thestd::unique_ptr
s by value. Unique pointers cannot be copied. You should pass them by reference.For more details and a more accurate possible implementation I refer you to https://en.cppreference.com/w/cpp/algorithm/binary_search.