Find a value in a set of shared_ptr

Question

I have a set of shared_ptr and would like to find a value in it:

typedef std::shared_ptr<int> IntPtr;

struct Compare {
  bool operator() (const IntPtr& a, const IntPtr& b) {
    return *a < *b;
  }
};
std::set<IntPtr, Compare> s;

auto x = std::make_shared<int>(3);
s.insert(x);

bool found = s.find(std::make_shared<int>(3)) != s.end();

It's working, but not efficient - it need to new a temp pointer every time when trying to find a value.

Is there any other way for it?

Looks like Searching in a set of shared_ptr<QString> has some ideas that might help?

_"it need to new a temp pointer every time when trying to find a value."_ What do mean? — Simon Kraemer, Sep 16 '15 at 13:51
There's also `std::find_if`, and eventually you could use an unordered set? — Daniel Jour, Sep 16 '15 at 13:56
@DanielJour: `std::find_if` does a linear search, whereas `std::set::find` does a binary search (`O(n)` vs `O(log(n)`)). — Jarod42, Sep 16 '15 at 14:45
@Jarod42 Indeed, my concern was more to find out whether the allocation is the main issue here. — Daniel Jour, Sep 16 '15 at 15:00
@DanielJour That's a good point. I always find it it difficult to choose between simpler code or more efficient code. — Deqing, Sep 16 '15 at 23:54

score 18 · Accepted Answer · edited May 23 '17 at 11:58

18

(In C++14) Make your comparator a transparent one and define additional logic for comparing stored shared_ptrs with ints:

struct Compare 
{
    using is_transparent = void;
    //    ~~~~~~~~~~~~~^

    bool operator() (const IntPtr& a, const IntPtr& b) const
    {
        return *a < *b;
    }

    bool operator() (const IntPtr& a, int b) const
    {
        return *a < b;
    }

    bool operator() (int a, const IntPtr& b) const
    {
        return a < *b;
    }
};

DEMO

edited May 23 '17 at 11:58

Community

1
1

answered Sep 16 '15 at 13:52

Piotr Skotnicki

46,953
7
118
160

1

Thanks, upvoted, learned something new today. That is, I'd read about transparent comparators but it didn't stick. I did not associate it with any practical use case. – Cheers and hth. - Alf Sep 16 '15 at 14:00

score 0 · Answer 2 · answered Sep 16 '15 at 13:53

With a single-threaded program you can reduce the overhead to a single global allocation:

using Int_ptr_set = std::set<IntPtr, Compare>;

auto find( int const v, Int_ptr_set const& values )
    -> bool
{
    static IntPtr p = std::make_shared<int>( 0 );
    *p = v;
    return values.find( p ) != values.end();
}

Disclaimer: code not touched by compiler's hands.

For threading you might consider making the above a method of a class, with p as a member, then make a thread-local static of that class.

Wouldn't it make more sense to create the int with `v` instead of `0` and avoid the `*p = v;` statement? — Alexis Wilke, May 29 '21 at 16:20

Find a value in a set of shared_ptr

2 Answers2