Finding an object in a <set> of pointers to objects

[Martin]

Hi

I need to maintain a <set> of pointers to objects, and it must be
sorted based on the values of pointed objects, not pointer values. I
can achieve this easily by defining my own comparing predicate for the
<set>. Here is an example:

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

class A
{
public:
A(const string& Name): m_Name(Name) {}
const string& Name() const { return m_Name; }

private:
string m_Name;

// Other members
// ...
};

class ptr_less
{
public:
bool operator()(const A* lhs, const A* rhs) const
{
return lhs->Name() < rhs->Name();
}
};

int main()
{
const string Names[] = { "alpha", "omega", "gamma", "beta",
"epsilon" };

// Create objects and fill 'S'
set<A*, ptr_less> S;
for (unsigned i = 0; i < sizeof(Names)/sizeof(Names[0]); ++i)
S.insert(new A(Names));

// Use 'S' ...

// Delete objects in 'S'
set<A*, ptr_less>::const_iterator csi;
for (csi = S.begin(); csi != S.end(); ++csi)
delete *csi;
};

In this example pointers in the <set> S will be sorted according to the
ascending order of names of pointed objects.

Now I want to find an obect in 'S' with name "gamma". How must I do
that? One way is to construct a dummy object with that name, and pass
its address to 'find' method of <set>. Here is an example:

A tempA("gamma");
S.find(&tempA);

Everything works ok, but creating a dummy object only for searching
purposes looks somewhat silly. Isn't there an elegant way to accomplish
this?

Thanks in advance

Martin

 

[Mark P]

Hi

I need to maintain a <set> of pointers to objects, and it must be
sorted based on the values of pointed objects, not pointer values. I
can achieve this easily by defining my own comparing predicate for the
<set>.
[snip]

In this example pointers in the <set> S will be sorted according to the
ascending order of names of pointed objects.

Now I want to find an obect in 'S' with name "gamma". How must I do
that? One way is to construct a dummy object with that name, and pass
its address to 'find' method of <set>. Here is an example:

A tempA("gamma");
S.find(&tempA);

Everything works ok, but creating a dummy object only for searching
purposes looks somewhat silly. Isn't there an elegant way to accomplish
this?

AFAIK, no. If you use a container like set, you're basically limited to
the interface exposed by the class. All of the binary search-like
operations on a set require arguments of the key type, so you basically
have to construct that dummy object. Of course there's nothing stopping
you from writing your own function that will do the work of creating the
dummy object behind the scenes: you can derive from std::set, wrap it in
another class, or even write a free fcn. for this.

 

[Axter]

Hi

I need to maintain a <set> of pointers to objects, and it must be
sorted based on the values of pointed objects, not pointer values. I
can achieve this easily by defining my own comparing predicate for the
<set>. Here is an example:

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

class A
{
public:
A(const string& Name): m_Name(Name) {}
const string& Name() const { return m_Name; }

private:
string m_Name;

// Other members
// ...
};

class ptr_less
{
public:
bool operator()(const A* lhs, const A* rhs) const
{
return lhs->Name() < rhs->Name();
}
};

int main()
{
const string Names[] = { "alpha", "omega", "gamma", "beta",
"epsilon" };

// Create objects and fill 'S'
set<A*, ptr_less> S;
for (unsigned i = 0; i < sizeof(Names)/sizeof(Names[0]); ++i)
S.insert(new A(Names));

// Use 'S' ...

// Delete objects in 'S'
set<A*, ptr_less>::const_iterator csi;
for (csi = S.begin(); csi != S.end(); ++csi)
delete *csi;
};

In this example pointers in the <set> S will be sorted according to the
ascending order of names of pointed objects.

Now I want to find an obect in 'S' with name "gamma". How must I do
that? One way is to construct a dummy object with that name, and pass
its address to 'find' method of <set>. Here is an example:

A tempA("gamma");
S.find(&tempA);

Everything works ok, but creating a dummy object only for searching
purposes looks somewhat silly. Isn't there an elegant way to accomplish
this?

I recommend using a smart pointer that can sort by the pointee.
The following smart pointer can do just that:
http://axter.com/smartptr/

Moreover, by using a smart pointer, you don't have to worry about
memory leaks, since the smart pointer will delete the object
automatically.

 

[Salt_Peter]

Hi

I need to maintain a <set> of pointers to objects, and it must be
sorted based on the values of pointed objects, not pointer values. I
can achieve this easily by defining my own comparing predicate for the
<set>. Here is an example:

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

class A
{
public:
A(const string& Name): m_Name(Name) {}
const string& Name() const { return m_Name; }

private:
string m_Name;

// Other members
// ...
};

class ptr_less
{
public:
bool operator()(const A* lhs, const A* rhs) const
{
return lhs->Name() < rhs->Name();
}
};

int main()
{
const string Names[] = { "alpha", "omega", "gamma", "beta",
"epsilon" };

// Create objects and fill 'S'
set<A*, ptr_less> S;
for (unsigned i = 0; i < sizeof(Names)/sizeof(Names[0]); ++i)
S.insert(new A(Names));

// Use 'S' ...

// Delete objects in 'S'
set<A*, ptr_less>::const_iterator csi;
for (csi = S.begin(); csi != S.end(); ++csi)
delete *csi;
};

In this example pointers in the <set> S will be sorted according to the
ascending order of names of pointed objects.

Now I want to find an obect in 'S' with name "gamma". How must I do
that? One way is to construct a dummy object with that name, and pass
its address to 'find' method of <set>. Here is an example:

A tempA("gamma");
S.find(&tempA);

Everything works ok, but creating a dummy object only for searching
purposes looks somewhat silly. Isn't there an elegant way to accomplish
this?

No, you need the dummy. Whats more, is you need op==(...).
Which can get nasty if you...say...use smart pointers.
Thankfully, boost::shared_ptr is equipped with an op== overload to
pointee.
So load the dummy into a smart pointer. and voila!

Another option is a std::map< A, shared_ptr<A> > in which case the key
can uses the default predicate. If i were you, i'ld go that way.

#include <iostream>
#include <set>
#include <iterator>
#include <boost/shared_ptr.hpp>

class A
{
std::string m_Name;
public:
A(const std::string& Name): m_Name(Name) {}
A(const A& copy) { m_Name = copy.m_Name; }
const std::string& Name() const { return m_Name; }
friend std:stream&
operator<<(std:stream& os, const A& r_a)
{
return os << r_a.m_Name;
}
};

typedef boost::shared_ptr< A > SharedPtrA;

class ptr_less
{
public:
bool operator()(const SharedPtrA& lhs,
const SharedPtrA& rhs) const
{
return lhs->Name() < rhs->Name();
}
};

int main()
{
const char* Names[] = { "alpha",
"omega",
"gamma",
"beta",
"epsilon" };

// Create objects and fill 'S'
std::set< SharedPtrA, ptr_less > S;
for (size_t i = 0; i < sizeof(Names)/sizeof(*Names); ++i)
{
A a(Names);
S.insert( SharedPtrA(new A(a)) );
std::cout << a << std::endl;
}

typedef std::set< SharedPtrA, ptr_less >::iterator SIter;
SIter siter = S.find(SharedPtrA(new A("gamma")));
if(siter != S.end())
{
std::cout << "found = " << *(*siter);
std::cout << " at " << *siter << std::endl;
}
else
{
std::cout << "name not found!\n";
}
}

/*
alpha
omega
gamma
beta
epsilon
found = gamma at 0x5051a0
*/

 

[Mark P]

No, you need the dummy. Whats more, is you need op==(...).
Which can get nasty if you...say...use smart pointers.
Thankfully, boost::shared_ptr is equipped with an op== overload to
pointee.
So load the dummy into a smart pointer. and voila!

Why do you say he needs op==? In a std::set, two keys are equal if
neither compares less than the other.

 

[Salt_Peter]

Why do you say he needs op==? In a std::set, two keys are equal if
neither compares less than the other.

Because find requires it. Ordering relation is not the same as the
equivalence relation.

Keys are equal depending on what "equal" means to the programmer. The
keys here are pointers and the pointer's value is *not* used to order
the set.
The pointers are ordered by the values held by a pointee's member.
Which itself needs to be unique to satisfy the set's requirements.
Consider that all initialized allocation pointers are unique except for
Null pointers. Thats the OP's issue. How do you load and compare the
dummy for equivalence?
Shared_ptr solves that issue because it has an op== that compares the
dereferenced values for equality. You could overload an op== to compare
A& dummy and a shared_ptr< A >&, but there is no need to, just load the
dummy in a shared_ptr and voila!.

 

[Mark P]

Because find requires it. Ordering relation is not the same as the
equivalence relation.

No it doesn't and, for a std::set, yes it is.