Pattern for reference counted map elements?

[Dennis Jones]

Hello,

I would like to know if there is a known pattern for creating a map of
reference-counted objects, such that when the last reference to an object is
deleted, the element referring to that object is removed from the map.

Since Boost's shared_ptr class allows a custom deleter to be specified, I
was thinking about something like this:
std::map<int, boost::shared_ptr<SomeClass MyMap;

// add an element to the map
MyMap[ 1 ] = boost::shared_ptr<SomeClass>( new SomeClass, CustomDeleter );
Where 'CustomDeleter' would have to defined such that it could remove the
corresponding element from the map. I'm not sure if this is the best
solution, or if it would even work.

Any insight offered will be appreciated.

- Dennis

[Dennis Jones]

"Dennis Jones" <no****@nospam.comwrote in message
news:IMqwh.4910$lk3.283@trnddc04...

Where 'CustomDeleter' would have to defined such that it could remove the
corresponding element from the map. I'm not sure if this is the best
solution, or if it would even work.

It won't work because as long as the element is in the map, its reference
count will always be at least 1.

So I still need a solution. Ideas?

- Dennis

[Michael]

On Feb 1, 11:49 am, "Dennis Jones" <[e-mail]:

"Dennis Jones" <[e-mail] in message

news:IMqwh.4910$lk3.283@trnddc04...

Where 'CustomDeleter' would have to defined such that it could remove the
corresponding element from the map. I'm not sure if this is the best
solution, or if it would even work.

It won't work because as long as the element is in the map, its reference
count will always be at least 1.

So I still need a solution. Ideas?

- Dennis

Here's a suggestion:

1) Store 'raw' pointer in your map.
2) Use shared_ptr everywhere else.
3) In destructor for your object class, have it notify your map that
the object needs to be removed. This can be handled via the Observer
pattern, for example. (If this is too abstract, let me know and I can
post some sample code.)

That way, when the last non-map shared_ptr goes out of scope, the
object is destroyed, and the destructor uncouples it from your map.

This way your map is somehow special, and is not covered in the normal
shared_ptr semantics. If that's okay, this should work. That seemed
to be the implication of the question you asked, but maybe there's a
way to do it that is symmetric in map and other pointers.

Michael

[Dennis Jones]

"Michael" <mc******@aol.comwrote in message
news:11**********************@l53g2000cwa.googlegr oups.com...

Here's a suggestion:

1) Store 'raw' pointer in your map.
2) Use shared_ptr everywhere else.
3) In destructor for your object class, have it notify your map that
the object needs to be removed. This can be handled via the Observer
pattern, for example. (If this is too abstract, let me know and I can
post some sample code.)

That way, when the last non-map shared_ptr goes out of scope, the
object is destroyed, and the destructor uncouples it from your map.

This way your map is somehow special, and is not covered in the normal
shared_ptr semantics. If that's okay, this should work. That seemed
to be the implication of the question you asked, but maybe there's a
way to do it that is symmetric in map and other pointers.

Michael,

For this problem, the observer pattern is definitely overkill, but your tips
(1) and (2) gave me exactly the ammunition I needed to solve the problem.
Here's my (sample) solution:

class MyClass
{
private:
int *FInt;
public:
MyClass( const int A ) : FInt( new int(A) ) {}
~MyClass() { delete FInt; }
int Int() { return *FInt; }
};
//---------------------------------------------------------------------------

class MapElementReleaser
{
private:
std::map<int, MyClass *&FMap;
public:
explicit MapElementReleaser( std::map<int, MyClass *&AMap ) : FMap(
AMap ) {}
void operator()(MyClass *pMyClass) const { FMap.erase(
pMyClass->Int() ); }
};
//---------------------------------------------------------------------------

std::map<int, MyClass *MyMap;

boost::shared_ptr<MyClassGetInt( const int x )
{
std::map<int, MyClass *>::iterator where = MyMap.find( x );
if ( where == MyMap.end() )
{
MyMap[ x ] = new MyClass( x );
}
return boost::shared_ptr<MyClass>( MyMap[ x ],
MapElementReleaser(MyMap) );
}
//---------------------------------------------------------------------------

int main(int argc, char* argv[])
{
boost::shared_ptr<MyClassmc1;
mc1 = GetInt( 1 ); // MyMap.size() == 1
{
boost::shared_ptr<MyClassmc2;
mc2 = GetInt( 2 ); // MyMap.size() == 2
} // MyMap.size() == 1
return 0;
} // MyMap.size() == 0

- Dennis

[Thomas J. Gritzan]

Dennis Jones schrieb:

"Dennis Jones" <no****@nospam.comwrote in message
news:IMqwh.4910$lk3.283@trnddc04...

>Where 'CustomDeleter' would have to defined such that it could remove the
corresponding element from the map. I'm not sure if this is the best
solution, or if it would even work.

It won't work because as long as the element is in the map, its reference
count will always be at least 1.

So I still need a solution. Ideas?

Store a boost::weak_ptr in the map.

--
Thomas
http://www.netmeister.org/news/learn2quote.html

[Dennis Jones]

"Thomas J. Gritzan" <Ph*************@gmx.dewrote in message
news:ep**********@newsreader3.netcologne.de...

Store a boost::weak_ptr in the map.

I am not familiar with weak_ptr, but from what I read, it just sets the
pointer to NULL when the last reference (via shared_ptr) has been deleted.
Unfortunately, this does not accomplish my intended goal, which is to have
the map element removed.

- Dennis

[Greg Herlihy]

On Feb 1, 12:37 pm, "Dennis Jones" <[e-mail]:

"Michael" <[e-mail] in message:

Here's a suggestion:

1) Store 'raw' pointer in your map.
2) Use shared_ptr everywhere else.
3) In destructor for your object class, have it notify your map that
the object needs to be removed. This can be handled via the Observer
pattern, for example. (If this is too abstract, let me know and I can
post some sample code.)

That way, when the last non-map shared_ptr goes out of scope, the
object is destroyed, and the destructor uncouples it from your map.

This way your map is somehow special, and is not covered in the normal
shared_ptr semantics. If that's okay, this should work. That seemed
to be the implication of the question you asked, but maybe there's a
way to do it that is symmetric in map and other pointers.

Michael,

For this problem, the observer pattern is definitely overkill, but your tips
(1) and (2) gave me exactly the ammunition I needed to solve the problem.
Here's my (sample) solution:

...
std::map<int, MyClass *MyMap;

boost::shared_ptr<MyClassGetInt( const int x )
{
std::map<int, MyClass *>::iterator where = MyMap.find( x );
if ( where == MyMap.end() )
{
MyMap[ x ] = new MyClass( x );
}
return boost::shared_ptr<MyClass>( MyMap[ x ],
MapElementReleaser(MyMap) );
}

This GetInt() routine has a serious flaw. GetInt() initializes a
shared_ptr with a raw pointer each time the routine is called.
Therefore none of the shared_ptrs that GetInt() returns for a
particular MyClass entry in the map, knows that any of the other
shared_ptrs previously returned by GetInt() to that same object exist.
So the first shared_ptr that goes out of scope will free its MyClass
pointer - no matter how many other shared_ptrs may also be holding
that same MyClass pointer. In other words, the program could easily
wind up with shared_ptrs that point to deallocated objects, and have
shared pointers attempt to delete pointers to objects that have
already been freed (or free pointers to new objects found at old
addresses that should not be freed).

A program should assign a raw pointer to a shared_ptr only once. After
that point, the program simply uses the shared_ptr - and never uses
the raw pointer again. Now, it is possible to create multiple
shared_ptrs from the same raw pointer as GetInt() does, just as long
as the object that the pointer points to is a subclass of
std::tr1::enable_shared_from_this.

A better solution in this case, it seems to me, would be to store a
MyClass weak_pointer instead of a MyClass raw pointer in the map.
Storing a weak_pointer enables GetInt() to return shared_ptrs that
will actually share their pointers. In this way, the program willl not
free the MyClass object until the last - instead of the first -
shared_ptr goes out of scope.

Greg

[Dennis Jones]

"Greg Herlihy" <gr****@pacbell.netwrote in message
news:11**********************@s48g2000cws.googlegr oups.com...

Thanks Greg, for your comments. Will you allow me to pick your brain?

>std::map<int, MyClass *MyMap;

boost::shared_ptr<MyClassGetInt( const int x )
{
std::map<int, MyClass *>::iterator where = MyMap.find( x );
if ( where == MyMap.end() )
{
MyMap[ x ] = new MyClass( x );
}
return boost::shared_ptr<MyClass>( MyMap[ x ],
MapElementReleaser(MyMap) );
}

This GetInt() routine has a serious flaw. GetInt() initializes a
shared_ptr with a raw pointer each time the routine is called.
Therefore none of the shared_ptrs that GetInt() returns for a
particular MyClass entry in the map, knows that any of the other
shared_ptrs previously returned by GetInt() to that same object exist.
So the first shared_ptr that goes out of scope will free its MyClass
pointer - no matter how many other shared_ptrs may also be holding
that same MyClass pointer. In other words, the program could easily
wind up with shared_ptrs that point to deallocated objects, and have
shared pointers attempt to delete pointers to objects that have
already been freed (or free pointers to new objects found at old
addresses that should not be freed).

Ah yes, I see. My little test was too narrowly focused to expose that flaw.

A program should assign a raw pointer to a shared_ptr only once. After
that point, the program simply uses the shared_ptr - and never uses
the raw pointer again.

Okay, so I should be creating the shared_ptr only when I am initially adding
an element to the map (which occurs only once)?

A better solution in this case, it seems to me, would be to store a
MyClass weak_pointer instead of a MyClass raw pointer in the map.
Storing a weak_pointer enables GetInt() to return shared_ptrs that
will actually share their pointers. In this way, the program willl not
free the MyClass object until the last - instead of the first -
shared_ptr goes out of scope.

As I stated in another post, I am not at all familiar with weak_ptr's and
don't really have any idea what changes would be necessary to use them in my
contrived sample program. But I'll start by changing the map definition:

typedef boost::weak_ptr<MyClassMyClassPtr_t;

std::map<int, MyClassPtr_tMyMap;
....and then modifying GetInt() to create a shared_ptr only once per map
element:

boost::shared_ptr<MyClassGetInt( const int x )
{
std::map<int, MyClassPtr>::iterator where = MyMap.find( x );
if ( where == MyMap.end() )
{
MyMap[ x ] = boost::shared_ptr<MyClass>( new MyClass( x ),
MapElementReleaser(MyMap) );
}
return MyMap[ x ].lock(); // is this correct?
}
The above compiles...but I have a couple of questions:

1) Is it okay to directly assign a shared_ptr to a weak_ptr as I have done
above, or do I need to be more explicit by creating a weak_ptr first and
assigning it to the map afterward?
2) Am I thinking correctly about the return value? It is still a shared_ptr
(which I still what I want, right?), and lock() returns a shared_ptr and
increments its reference count (as if I were copying it)?
Now what is the correct way to write the custom deleter? The custom deleter
below compiles and functions as expected when MyClassPtr is a raw ptr, but
not when it is a weak_ptr:

class MapElementReleaser
{
private:
std::map<int, MyClassPtr&FMap;
public:
explicit MapElementReleaser( std::map<int, MyClassPtr&AMap )
: FMap( AMap ) {}

void operator()(MyClassPtr pMyClass) const
{
for ( std::map<int, MyClassPtr>::iterator map_end( FMap.end() ),
map_iter( FMap.begin() );
map_iter != map_end;
++map_iter )
{
if ( map_iter->second == pMyClass )
{
FMap.erase( map_iter->first );
break;
}
}
}
};

The idea behind the operator() here is that it must remove the element in
the map that contains the weak_ptr identified by 'MyClassPtr pMyClass.' I
thought perhaps I could do something like:

if ( map_iter->second.lock().get() == pMyClass.lock().get() )

....but that won't compile (and the error messages don't make any sense to
me!). Furthermore, it seems to me that it would increment the reference
count on the very shared_ptr that is currently being deleted via the custom
deleter (which can only occur when its reference count has already reached
zero)! So, what is the best way to find and remove the appropriate element?

Thanks,

- Dennis

[Greg Herlihy]

On 2/2/07 10:19 AM, in article CgLwh.5740$WI6.1099@trnddc04, "Dennis Jones"
<no****@nospam.comwrote:

>
"Greg Herlihy" <gr****@pacbell.netwrote in message

>A better solution in this case, it seems to me, would be to store a
MyClass weak_pointer instead of a MyClass raw pointer in the map.
Storing a weak_pointer enables GetInt() to return shared_ptrs that
will actually share their pointers. In this way, the program willl not
free the MyClass object until the last - instead of the first -
shared_ptr goes out of scope.

As I stated in another post, I am not at all familiar with weak_ptr's and
don't really have any idea what changes would be necessary to use them in my
contrived sample program. But I'll start by changing the map definition:

typedef boost::weak_ptr<MyClassMyClassPtr_t;

std::map<int, MyClassPtr_tMyMap;
...and then modifying GetInt() to create a shared_ptr only once per map

element:

boost::shared_ptr<MyClassGetInt( const int x )
{
std::map<int, MyClassPtr>::iterator where = MyMap.find( x );
if ( where == MyMap.end() )
{
MyMap[ x ] = boost::shared_ptr<MyClass>( new MyClass( x ),
MapElementReleaser(MyMap) );
}
return MyMap[ x ].lock(); // is this correct?
}
The above compiles...but I have a couple of questions:

1) Is it okay to directly assign a shared_ptr to a weak_ptr as I have done
above, or do I need to be more explicit by creating a weak_ptr first and
assigning it to the map afterward?

There is still one more change to make to GetInt(). The GetInt() routine has
to be very careful (when adding a new entry to the map) not to let the only
shared_ptr holding the MyClass pointer to go out of scope (since that would
delete the pointer). Unfortunately, the GetInt() routine does allow the
shared_ptr to go out of scope before it obtains another pointer to return to
its caller (by which time it is too late since the pointer will have been
deleted).

Therefore I recommend that GetInt() declare a shared_ptr<MyClassat the
very start of the routine (and have GetInt() return this shared_ptr as its
result). Now GetInt() will either assign this shared_ptr an existing entry
(if it finds one in the map) or a pointer to new MyClass object that it
allocates and adds to the map.

2) Am I thinking correctly about the return value? It is still a shared_ptr
(which I still what I want, right?), and lock() returns a shared_ptr and
increments its reference count (as if I were copying it)?

Returning a shared_ptr is fine - it becomes the caller's responsibility for
deciding how long to keep the shared_ptr around.

Now what is the correct way to write the custom deleter? The custom deleter
below compiles and functions as expected when MyClassPtr is a raw ptr, but
not when it is a weak_ptr:

class MapElementReleaser
{
private:
std::map<int, MyClassPtr&FMap;
public:
explicit MapElementReleaser( std::map<int, MyClassPtr&AMap )
: FMap( AMap ) {}

void operator()(MyClassPtr pMyClass) const
{
for ( std::map<int, MyClassPtr>::iterator map_end( FMap.end() ),
map_iter( FMap.begin() );
map_iter != map_end;
++map_iter )
{
if ( map_iter->second == pMyClass )
{
FMap.erase( map_iter->first );
break;
}
}
}
};

In this case, just search for the first NULL weak_ptr (by calling lock())
and remove its entry from the map. Since the NULL weak_ptr should correspond
to the MyClass object that was just deleted.

I would also consider a std::set instead of a map (and store the int key
inside MyClass) for improved efficiency when removing the entry from the
map.

Greg

[Dennis Jones]

"Greg Herlihy" <gr****@pacbell.netwrote in message
news:C1******************@pacbell.net...

There is still one more change to make to GetInt(). The GetInt() routine
has
to be very careful (when adding a new entry to the map) not to let the
only
shared_ptr holding the MyClass pointer to go out of scope (since that
would
delete the pointer). Unfortunately, the GetInt() routine does allow the
shared_ptr to go out of scope before it obtains another pointer to return
to
its caller (by which time it is too late since the pointer will have been
deleted).

You're absolutely right, Greg -- thank you for pointing that out. Can you
tell I'm still learning the nuances of shared_ptr usage? :-)

>Now what is the correct way to write the custom deleter?

In this case, just search for the first NULL weak_ptr (by calling lock())
and remove its entry from the map. Since the NULL weak_ptr should
correspond
to the MyClass object that was just deleted.

Oh, okay, that makes sense (I think!). Can I use:

lock() == NULL

or should I use:

lock().get() == NULL ?

I would also consider a std::set instead of a map (and store the int key
inside MyClass) for improved efficiency when removing the entry from the
map.

Well, I need the key-value lookup that a map provides. The key portion is
not a member of the class like it was in one of my previous posts (which
made it easy to erase from the map!), though I may be able to put the key in
the class -- I'm just not sure yet. This won't be a large map anyway
(probably on the order of 20-30 elements), and the frequency of deletions
will be such that iterating over the map shouldn't be too bad at all.

Now, having implemented your suggestions, I now have something that appears
to work the way I want it to, EXCEPT that the MyClass destructor is never
called. My modified code is given below. What is wrong? Have I forgotten
something else, or have I run into a compiler bug?

class MyClass
{
private:
int *FInt;
public:
MyClass( const int A )
: FInt( new int(A) )
{
}
~MyClass()
{
delete FInt; // NEVER CALLED!!!
}
};
//---------------------------------------------------------------------------

typedef boost::weak_ptr<MyClassMyClassPtr;

class MapElementEraser
{
private:
std::map<int, MyClassPtr&FMap;
public:
explicit MapElementEraser( std::map<int, MyClassPtr&AMap )
: FMap( AMap ) {}

void operator()(MyClass *pMyClass) const
{
for ( std::map<int, MyClassPtr>::iterator map_end( FMap.end() ),
map_iter( FMap.begin() );
map_iter != map_end;
++map_iter )
{
if ( map_iter->second.lock().get() == NULL )
{
FMap.erase( map_iter->first );
break;
}
}
}
};
//---------------------------------------------------------------------------

std::map<int, MyClassPtrMyMap;

boost::shared_ptr<MyClassGetInt( const int x )
{
boost::shared_ptr<MyClassresult;

std::map<int, MyClassPtr>::iterator where = MyMap.find( x );
if ( where == MyMap.end() )
{
result = boost::shared_ptr<MyClass>( new MyClass( x ),
MapElementEraser(MyMap) );
MyMap[ x ] = result;
}
else
{
result = MyMap[ x ].lock();
}
return result;
}
//---------------------------------------------------------------------------

#pragma argsused
int main(int argc, char* argv[])
{
boost::shared_ptr<MyClassmc1;
mc1 = GetInt( 1 );
{
boost::shared_ptr<MyClassmc2;
mc2 = GetInt( 2 );
}
boost::shared_ptr<MyClassmc3;
mc3 = GetInt( 1 );
return 0;
}

Thank you for your generous help.

- Dennis

[Greg Herlihy]

On Feb 2, 9:54 pm, "Dennis Jones" <[e-mail]:

"Greg Herlihy" <[e-mail] in message

news:C1******************@pacbell.net...

Now what is the correct way to write the custom deleter?

In this case, just search for the first NULL weak_ptr (by calling lock())
and remove its entry from the map. Since the NULL weak_ptr should
correspond
to the MyClass object that was just deleted.

Oh, okay, that makes sense (I think!). Can I use:

lock() == NULL

or should I use:

lock().get() == NULL ?

I can't really think of a reason to recommend one over the other. The
former syntax requires less typing, but some may find the latter
syntax more clear.

Now, having implemented your suggestions, I now have something that appears
to work the way I want it to, EXCEPT that the MyClass destructor is never
called. My modified code is given below. What is wrong? Have I forgotten
something else, or have I run into a compiler bug?

class MyClass
{
private:
int *FInt;
public:
MyClass( const int A )
: FInt( new int(A) )
{
}
~MyClass()
{
delete FInt; // NEVER CALLED!!!
}};

//------------------------------------------------------------------------- --

typedef boost::weak_ptr<MyClassMyClassPtr;

class MapElementEraser
{
private:
std::map<int, MyClassPtr&FMap;
public:
explicit MapElementEraser( std::map<int, MyClassPtr&AMap )
: FMap( AMap ) {}

void operator()(MyClass *pMyClass) const
{
for ( std::map<int, MyClassPtr>::iterator map_end( FMap.end() ),
map_iter( FMap.begin() );
map_iter != map_end;
++map_iter )
{
if ( map_iter->second.lock().get() == NULL )
{
FMap.erase( map_iter->first );
break;
}
}
}};

Since the program provides its own, custom deleter - the custom
deleter alone is responsible for deleting the pointer (should the
pointer need to be freed). Therefore add the following line of code to
MapElementEraser::operator():

...
if ( map_iter->second.lock().get() == NULL )
{
FMap.erase( map_iter->first );
delete pMyClass; // new line added
break;
}
...

With that one line addition, the MyClass object should be removed from
the map and deleted once no reference to that object (outside of its
map) exists anywhere in the program.

Greg

[Dennis Jones]

"Greg Herlihy" <gr****@pacbell.netwrote in message
news:11**********************@q2g2000cwa.googlegro ups.com...

Since the program provides its own, custom deleter - the custom
deleter alone is responsible for deleting the pointer

Duh! Thank you. Sometimes the obvious is just too obvious!

- Dennis