set of T*; how to make T the key?

[crichmon]

Hi,

I have a class that maintains a set of other objects. To save space, I'd
like to have a set of pointers to other objects, as multiple things can
reference/point to a unique object. The problem I've having though is that
I want the set to to use the object as the key, not the pointer. But it
gets trickier! I'm using a custom smart pointer instead of regular pointers
to allow poor-man's garbage collection.

My class kinda looks like

#include <set>
using namespace std;

class Foo
{
public:
typedef set<SmartPtr<Bar> > BarPtrSet;
typedef set<SmartPtr<Bar> >::iterator BPSiterator;

private:
BarPtrSet other_objects;

....
};


I tried a hack by making SmartPtr's less-than operator compare dereferenced
pointers rather than pointers, but that didn't really work and it causes
problems elsewhere in my code... and I am really hoping that I don't have to
just use set<Bar>.

My first thought is that I should modify the second template parameter of
set so that it is comparing something else, but I haven't found anything
that works yet... any thoughts out there?

thanks,
crichmon

 

[red floyd]

Hi,

I have a class that maintains a set of other objects. To save space, I'd
like to have a set of pointers to other objects, as multiple things can
reference/point to a unique object. The problem I've having though is that
I want the set to to use the object as the key, not the pointer. But it
gets trickier! I'm using a custom smart pointer instead of regular pointers
to allow poor-man's garbage collection.

Write a custom comparator *for the set*, not for SmartPtr<Bar>.
Remember the STL classes take a comparator, which usually defaults to

My class kinda looks like

#include <set>

using namespace std;

class BarPtrComp : public std::binary_function<
SmartPtr<Bar>, SmartPtr<Bar>, bool>
{
public:
bool operator()(const SmartPtr<Bar>& lhs,
const SmartPtr<Bar>& rhs) const
{
return *lhs < *rhs;
}
};

class Foo
{
public:
// typedef set<SmartPtr<Bar> > BarPtrSet;
// typedef set<SmartPtr<Bar> >::iterator BPSiterator;

typedef set<SmartPtr<Bar>, BarPtrComp> BarPtrSet;
typedef BarPtrSet::iterator BPSiterator;

private:
BarPtrSet other_objects;

...
};


I tried a hack by making SmartPtr's less-than operator compare dereferenced
pointers rather than pointers, but that didn't really work and it causes
problems elsewhere in my code...

Not necessary, see above.

and I am really hoping that I don't have to

just use set<Bar>.

My first thought is that I should modify the second template parameter of
set so that it is comparing something else, but I haven't found anything
that works yet... any thoughts out there?

That's the correct solution. See above.

 

[Thierry Miceli]

class Foo

{
public:
typedef set<SmartPtr<Bar> > BarPtrSet;
typedef set<SmartPtr<Bar> >::iterator BPSiterator;

private:
BarPtrSet other_objects;

...
};

You can specify a key comparison predicate in the set template argument
list. As below:

// The predicate functor
struct lessBar
{
bool operator() (const SmartPtr<Bar>& pb1, const SmartPtr<Bar>& pb2)
const
{
return pb1->key < pb2->key; // Do the actual key comparison here
with whatever identifies you Bar instances
}
};

// Your Bar set type with the ordering predicate
typedef set< SmartPtr<Bar>, lessBar > BarPtrSet;

Hope this helps,

Thierry

 

[nmtop40]

Hi,

I have a class that maintains a set of other objects. To save space, I'd
like to have a set of pointers to other objects, as multiple things can
reference/point to a unique object. The problem I've having though is that
I want the set to to use the object as the key, not the pointer. But it
gets trickier! I'm using a custom smart pointer instead of regular pointers
to allow poor-man's garbage collection.

My class kinda looks like

#include <set>
using namespace std;

class Foo
{
public:
typedef set<SmartPtr<Bar> > BarPtrSet;
typedef set<SmartPtr<Bar> >::iterator BPSiterator;

private:
BarPtrSet other_objects;

...
};


I tried a hack by making SmartPtr's less-than operator compare dereferenced
pointers rather than pointers, but that didn't really work and it causes
problems elsewhere in my code... and I am really hoping that I don't have to
just use set<Bar>.

My first thought is that I should modify the second template parameter of
set so that it is comparing something else, but I haven't found anything
that works yet... any thoughts out there?

Yes, you modify the second parameter.

This may work:

template < typename T >
bool PtrLess( const T* left, const T* right )
{
return *left < *right;
}

If it doesn't then try this:

template < typename T >
struct PtrLess
{
bool operator()( const T* left, const T* right ) const
{
return *left < *right;
}
};

You would then declare

std::set( T*, PtrLess<T> );

You will possibly find this problem has already been addressed by
boost. (I don't think it has been by STL yet though).

 

[Rolf Magnus]

This may work:

template < typename T >
bool PtrLess( const T* left, const T* right )
{
return *left < *right;
}

If it doesn't then try this:

template < typename T >
struct PtrLess
{
bool operator()( const T* left, const T* right ) const
{
return *left < *right;
}
};

I'd always prefer the second one, because it is potentially faster.

 

[crichmon]

Yes, you modify the second parameter.

This may work:

template < typename T >
bool PtrLess( const T* left, const T* right )
{
return *left < *right;
}

If it doesn't then try this:

template < typename T >
struct PtrLess
{
bool operator()( const T* left, const T* right ) const
{
return *left < *right;
}
};

You would then declare

std::set( T*, PtrLess<T> );

do you mean

std::set< T*, PtrLess<T> > something;

?



Thanks to everyone who has helped!

You will possibly find this problem has already been
addressed by boost. (I don't think it has been by
STL yet though).

What is "boost"?

thnx,
crichmon

 

[Rolf Magnus]

What is "boost"?

A C++ library of mostly templates that has lots of functionality that is
missing in the standard library. It's likely that parts of boost will
go into the standard library in the next version of the C++ standard.

 

[crichmon]

Write a custom comparator *for the set*, not for
SmartPtr<Bar>. Remember the STL classes take a
comparator, which usually defaults to std::less<T>,
but can be overridden.

#include <set>
#include <functional>
using namespace std;

class BarPtrComp : public std::binary_function<
SmartPtr<Bar>, SmartPtr<Bar>, bool>
{
public:
bool operator()(const SmartPtr<Bar>& lhs,
const SmartPtr<Bar>& rhs) const
{
return *lhs < *rhs;
}
};

...
typedef set<SmartPtr<Bar>, BarPtrComp> BarPtrSet;
typedef BarPtrSet::iterator BPSiterator;
...

This is what I ended up implementing:

/////////////
// SmartPtr.h
#include <functional>
using namespace std;

template<class C>
class SmartPtr
{
....
};

template<class C>
class SmartPtrComp: public binary_function<
SmartPtr<C>, SmartPtr<C>, bool>
{
public:
bool operator()( const SmartPtr<C>& lhs,
const SmartPtr<C>& rhs ) const
{
return ( (*lhs) < (*rhs) );
}
};
//////////////
// OtherFile.h
#include <set>
#include "SmartPtr.h"
#include "Bar.h"
using namespace std;
....
typedef set<SmartPtr<Bar>, SmartPtrComp<Bar> > BarPtrSet;
typedef BarPtrSet::iterator BPSiterator;
....
/////////////////

it works really well, thanks for the help!
crichmon

 

[red floyd]

[redacted]

Glad I could help. The wizards here have helped me quite a bit, glad I
could return the favor to someone else.