If the goal is constant time for the look up, I don't think that
there is a solution.
std::unordered_set<std::unique_ptr<MyClass>>::find
requires an
std::unique_ptr<MyClass>
as argument. You will have to either change
the container, or change the contained type.
One possibility might be to replace std::unique_ptr
with
std::shared_ptr
, and change the rest of the code so that all
MyClass
are put into a shared_ptr as soon as they are created,
and are only manipulated through shared pointers. Logically,
this is probably more coherent anyway: unique_ptr
pretty much
implies (by its name, as well as its semantics) that there
aren't other pointers to the object. On the other hand, you may
not be able to use shared_ptr, if e.g. MyClass
has pointers to
other MyClass
, which may build a cycle.
Otherwise, if you can accept O(lg n) access, rather than
constant access (the difference generally doesn't become
noticeable until the tables are fairly large), you can use an
std::vector<MyClass>
, using std::lower_bound
to keep it
sorted. Unlike std::unordered_set<>::find
, std::lower_bound
does not require the target value to have the same type as the
value_type
of the sequence; all you have to do is to ensure
that they are comparable, say by providing a Compare
object
along the lines of:
class MyClassPtrCompare
{
std::less<MyClass const*> cmp;
public:
bool operator()( std::unique_ptr<MyClass> const& lhs,
std::unique_ptr<MyClass> const& rhs ) const
{
return cmp( lhs.get(), rhs.get() );
}
bool operator()( MyClass const* lhs,
std::unique_ptr<MyClass> const& rhs ) const
{
return cmp( lhs, rhs.get() );
}
bool operator()( std::unique_ptr<MyClass> const& lhs,
MyClass const* rhs ) const
{
return cmp( lhs.get(), rhs );
}
bool operator()( MyClass const* lhs,
MyClass const* rhs ) const
{
return cmp( lhs, rhs );
}
};
Insertion may involve a number of moves, but moving
a std::unique_ptr
should be fairly cheap, and the improved
locality of this solution might offset the additional runtime
costs it otherwise imposes.