C++ std::set custom comparator

Question

Well, my problem is that I'm using an std::set with a custom comparator, something like:

class A
{
public:
    A(int x, int y):
        _x(x), _y(y)
    {
    }

    int hashCode(){ return (_y << 16) | _x; }

private:
    short int _y;
    short int _x;
};

struct comp
{
    bool operator() (A* g1, A* g2) const
    {
        return g1->hashCode() < g2->hashCode();
    }
};

So, I use it like

std::set<A*, comp> myset;

// Insert some data
A* a = new A(2,1);
A* b = new A(1,3);
myset.insert(a);
myset.insert(b);

Now my problem is that I would like to do this:

myset.find( (2 << 16) | 1 );

But, of course, it excepts A* not short int.

So, I know I could use std::find_if, but won't it render useless the custom comparator? It would iterate the whole list, wouldn't it? Is there any way I could use find with the hashCode rather than the object itself?

Thank you!

Answer 1

set::find takes argument of type key_type (see discussion Why is set::find not a template?). Using a std::set you have to construct a temporary object to use find.

myset.find(A(2, 1));

If A is not cheap to construct you might want to use a std::map<int, A> (or a wrapper around it) instead.

Answer 2

You can't do this with std::set, because std::set<>::find is not a (member) template; the argument must be of the key type. For simple classes like yours, it's likely that using an std::vector<A> and keeping it sorted (using std::lower_bound for lookup, and as the insertion point) will be just as fast. And with std::lower_bound, you can pass in a comparitor, and use any type you want as key. All you have to do is ensure that your comp class can handle the mixed type comparisons, e.g.:

struct Comp
{
    bool operator()( A const&, B const& ) const;
    bool operator()( A const&, int ) const;
    bool operator()( int, A const& ) const;
};

Answer 3

myset.find(&A(2, 1));

Or

A a(2, 1);
myset.find(&a);

Answer 4

You have defined a std::set<A*, comp> myset;, so std::find() must take a A* argument.

std::set<A*, comp> myset;

// Insert some data
A* a = new A(2,1);
A* b = new A(1,3);
myset.insert(a);
myset.insert(b);

Then, you need to do

myset.find(&A(2,1))

Back to your question, std::find() is not taking your custom comparator. You need, in fact, to use std::find_if.