declaration order

[rengolin]

Hi,

I've reached a deadlock with shared_ptr and my next step will be a
complete re-think of the problem but before I'd like to share with you
my problem as probably some of you had the very problem and solved
better than me...

I want an std::set < shared_ptr<Foo> > to check duplicates and find
elements by one of Foo's attributes:

#include <iostream>
#include <set>
#include <map>
#include <string>
#include <boost/shared_ptr.hpp>

using namespace std;

struct Foo {
char c;
Foo(char s) : c(s) { cout << "ctor: " << c << endl; }
~Foo() { cout << "dtor: " << c << endl; }
};
typedef boost::shared_ptr<Foo> ptr;
struct less_by_value
{
bool operator()(const ptr f1, const ptr f2) const
{
return f1.get()->c < f2.get()->c;
}
};

int main () {
int i;
set<ptr, less_by_value> list;

// Populate map (double insert to test multiplicity)
for (i=0; i<5; i++) {
ptr foo (new Foo('A' + i));
list.insert(foo);
list.insert(foo);
}
cout << "map size: " << list.size() << " == 5 ?" << endl;

// Test find in set
set<ptr, less_by_value>::iterator it;
ptr needle (new Foo('A'));
if ((it = list.find(needle)) != list.end())
cout << (*it)->c << " == " << needle->c << endl;
else
cout << needle->c << " not found" << endl;
return 0;
}

This code works fine:
$ g++ ptr.cpp && ./a.out
ctor: A
ctor: B
ctor: C
ctor: D
ctor: E
map size: 5 == 5 ?
ctor: A
A == A
dtor: A
dtor: E
dtor: D
dtor: C
dtor: B
dtor: A

Now, here comes the problem... I want to keep a list of Foo pointers
inside Foo itself. Like in a graph, I need to keep all other nodes
connected and the distance, so I need to put the typedef before:

struct Foo;
typedef boost::shared_ptr<Foo> ptr;
struct Foo {
char c;
map<ptr, double> connections;
Foo(char s) : c(s) { cout << "ctor: " << c << endl; }
~Foo() { cout << "dtor: " << c << endl; }
};

So far, so good, but my map need also to use the same 'less' for
finding elements and I need to declare the struct 'less_by_value'
_before_ my struct:

struct Foo;
typedef boost::shared_ptr<Foo> ptr;
struct less_by_value
{
bool operator()(const ptr s1, const ptr s2) const
{
return s1.get()->c < s2.get()->c;
}
};
struct Foo {
char c;
map<ptr, double, less_by_value> connections;
Foo(char s) : c(s) { cout << "ctor: " << c << endl; }
~Foo() { cout << "dtor: " << c << endl; }
};

And because 's1.get()->c' is using the structure of 'Foo' before it's
own full declaration, GCC gives me this error message:

ptr.cpp: In member function 'bool less_by_value:perator()(ptr, ptr)
const':
ptr.cpp:14: error: invalid use of undefined type 'struct Foo'
ptr.cpp:8: error: forward declaration of 'struct Foo'
ptr.cpp:14: error: invalid use of undefined type 'struct Foo'
ptr.cpp:8: error: forward declaration of 'struct Foo'

Even if not using shared_ptr I would still need to write my own less
to compare by value in the main set to reuse the same entries
regardless of it's connections at any time.

I thought of writing my own "search_by_value" functor class with
std::find_if but I'd still not have uniqueness within the std::set and
the std::map I want.

Is there an elegant way out of this deadlock?

cheers,
--renato

 

[Alf P. Steinbach]

* rengolin:

Hi,

I've reached a deadlock with shared_ptr and my next step will be a
complete re-think of the problem but before I'd like to share with you
my problem as probably some of you had the very problem and solved
better than me...

I want an std::set < shared_ptr<Foo> > to check duplicates and find
elements by one of Foo's attributes:

#include <iostream>
#include <set>
#include <map>
#include <string>
#include <boost/shared_ptr.hpp>

using namespace std;

struct Foo {
char c;
Foo(char s) : c(s) { cout << "ctor: " << c << endl; }
~Foo() { cout << "dtor: " << c << endl; }
};
typedef boost::shared_ptr<Foo> ptr;
struct less_by_value
{
bool operator()(const ptr f1, const ptr f2) const

Just write

bool operator()( ptr f1, ptr f2 ) const

or for efficiency

bool operator()( ptr const& f1, ptr const& f2 ) const

{
return f1.get()->c < f2.get()->c;

Why are you using "get" here?

}
};

int main () {
int i;
set<ptr, less_by_value> list;

// Populate map (double insert to test multiplicity)

Is this meant to be a set, a list or a map?

for (i=0; i<5; i++) {
ptr foo (new Foo('A' + i));
list.insert(foo);
list.insert(foo);
}
cout << "map size: " << list.size() << " == 5 ?" << endl;

// Test find in set
set<ptr, less_by_value>::iterator it;
ptr needle (new Foo('A'));
if ((it = list.find(needle)) != list.end())
cout << (*it)->c << " == " << needle->c << endl;
else
cout << needle->c << " not found" << endl;
return 0;
}

This code works fine:
$ g++ ptr.cpp && ./a.out
ctor: A
ctor: B
ctor: C
ctor: D
ctor: E
map size: 5 == 5 ?
ctor: A
A == A
dtor: A
dtor: E
dtor: D
dtor: C
dtor: B
dtor: A

Now, here comes the problem... I want to keep a list of Foo pointers
inside Foo itself. Like in a graph, I need to keep all other nodes
connected and the distance, so I need to put the typedef before:

struct Foo;
typedef boost::shared_ptr<Foo> ptr;
struct Foo {
char c;
map<ptr, double> connections;
Foo(char s) : c(s) { cout << "ctor: " << c << endl; }
~Foo() { cout << "dtor: " << c << endl; }
};

So far, so good,

It looks like you will have circular chains of shared_ptr's.

That means reference counts will never reach 0 automatically, and so no
automatic cleanup => likely memory leak.

Try instead e.g. Boost's graph library.

but my map need also to use the same 'less' for
finding elements and I need to declare the struct 'less_by_value'
_before_ my struct:

struct Foo;
typedef boost::shared_ptr<Foo> ptr;
struct less_by_value
{
bool operator()(const ptr s1, const ptr s2) const
{
return s1.get()->c < s2.get()->c;
}
};
struct Foo {
char c;
map<ptr, double, less_by_value> connections;
Foo(char s) : c(s) { cout << "ctor: " << c << endl; }
~Foo() { cout << "dtor: " << c << endl; }
};

And because 's1.get()->c' is using the structure of 'Foo' before it's
own full declaration, GCC gives me this error message:

ptr.cpp: In member function 'bool less_by_value:perator()(ptr, ptr)
const':
ptr.cpp:14: error: invalid use of undefined type 'struct Foo'
ptr.cpp:8: error: forward declaration of 'struct Foo'
ptr.cpp:14: error: invalid use of undefined type 'struct Foo'
ptr.cpp:8: error: forward declaration of 'struct Foo'

Just move the implementation of less_by_value:perator().

Note that you don't need a functor object.

A plain ole' function works just as well (or even better), as long as it
has external linkage.

Even if not using shared_ptr I would still need to write my own less
to compare by value in the main set to reuse the same entries
regardless of it's connections at any time.

I thought of writing my own "search_by_value" functor class with
std::find_if but I'd still not have uniqueness within the std::set and
the std::map I want.

Is there an elegant way out of this deadlock?

Main problem is not the circular dependencies in the code (easily
resolved, see above) but the potential circularities in the data
structure (see above).

For general graphs, don't use shared_ptr.

At least, not indiscriminately. ;-)


Cheers, & hth.,

- Alf

 

[rengolin]

It looks like you will have circular chains of shared_ptr's.

That means reference counts will never reach 0 automatically, and so no
automatic cleanup => likely memory leak.

Try instead e.g. Boost's graph library.

Hi Alf.

As I always say, ask the right question and the answer would be pretty
easy...

This is the first time I use 'graph' to describe my problem and seems
that boost already have a graph library which avoids all circular
chains, iterators and much more. I haven't thought about the reference
count deadlock, too and probably many other problems I would have re-
inventing the wheel.

Thank you for the quick answer!
--renato