skip to Main Content

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


  1. There are three issues:

    1. 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 copy unique_ptr? No. That’s why it’s not working. Take the arguments by const reference instead.

    2. The lambda cannot accept 5 as one of its arguments since 5 is not a unique_ptr<int>

    3. 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 instead

    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(),
                std::make_unique<int>(5),
                [](const std::unique_ptr<int>& x, const std::unique_ptr<int>& y) {
            return *x < *y;
        });
        return 0;
    }
    

    Feel 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 accept int and std::unique_ptr<int> as its arguments in either order. This is probably the easiest approach to do so:

        struct Compare {
            bool operator()(const std::unique_ptr<int>& left, int right) const
            { return *left < right; }
            bool operator()(int left, const std::unique_ptr<int>& right) const
            { return left < *right; }
        };
        auto t = std::binary_search(begin, end, val, Compare{});
    
    Login or Signup to reply.
  2. 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

    auto comp =  [] (std::unique_ptr<int> x, std::unique_ptr<int> y) {
        return x.get() < y.get();
    };
    
    auto value = 5;
    

    Then the algorithm will do something along the line of:

    for (const auto& x : a) { 
        if (comp(x,value)) ...
    

    This has two issues: 5 is not a std::unique_ptr<int>. And you cannot pass the std::unique_ptrs 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.

    Login or Signup to reply.
Please signup or login to give your own answer.
Back To Top
Search