the correct way to delete a map

[Nick Keighley]

Hi,

I have a map containing pointers. When I destroy the map I want to
delete
all the pointers.

typedef std::map<std::string, const T*> Table;

void destroy_map ()
{
for (Table::iterator i = table_.begin(); i != table_.end(); ++i)
{
delete (*i).second;
table_.erase (i);
}
}


this crashes. Does the erase() invalidate the iterator?

This was the code I found on the net (latout fixed a bit)

for (map::iterator itr = myMap.begin(); itr != myMap.end())
{
if(itr->value == something)
myMap.erase(itr++);
else
itr++;
}

which it is claimed is from Josuttis. I suppose the fact that it
didn't compile should of made me doubt this...

 

[Nick Keighley]

Hi,

I have a map containing pointers. When I destroy the map I want to
delete
all the pointers.

typedef std::map<std::string, const T*> Table;

void destroy_map ()
{
for (Table::iterator i = table_.begin(); i != table_.end(); ++i)
{
delete (*i).second;
table_.erase (i);
}

}

this crashes. Does the erase() invalidate the iterator?

This was the code I found on the net (latout fixed a bit)

for (map::iterator itr = myMap.begin(); itr != myMap.end())
{
if(itr->value == something)
myMap.erase(itr++);
else
itr++;

}

which it is claimed is from Josuttis. I suppose the fact that it
didn't compile should of made me doubt this...

ah! more poking around on the net. erase() does invalidate the
iterator. That's why the net code does a post increment in the erase
call.
So preumably I want:-

void destroy_map ()
{
for (Table::iterator i = table_.begin(); i != table_.end()
{
delete (*i).second;
table_.erase (i++);
}
}

since this code is actually in a DTOR and table_ is member variable
would I be better leaving the destruction of the map to the DTOR?

class Symbol_table
{
public:
Table table_;
~Symbol_table();
};

Symbol_table::~Symbol_table()
{
for (Table::iterator i = table_.begin(); i != table_.end(); ++i)
delete (*i).second;
}

should the for-loop be changed into an algorithm? for_each()?

 

[Juha Nieminen]

table_.erase (i++);

No, the standard way is: i = table_.erase(i);

Besides, there's no need to individually erase the map elements. Just
free the memory pointed by the elements and then just clear() the map,
given that you are cleaning it completely.

 

[Daniel T.]

I have a map containing pointers. When I destroy the map I want to
delete all the pointers.

typedef std::map<std::string, const T*> Table;

void destroy_map ()
{
for (Table::iterator i = table_.begin(); i != table_.end(); ++i)
{
delete (*i).second;
table_.erase (i);
}
}


this crashes. Does the erase() invalidate the iterator?

Yes. Try this instead:

void destroy_map()
{
for ( Table::iterator i = table_.begin(); i != table_.end(); ++i )
{
delete i->second;
i->second = 0; // I don't think this is strictly necessary...
}
table_.clear();
}

or if you want to have fun with algorithms:

typedef map<int, int*> Table;

template < typename T >
void delete_second( T& t ) {
delete t.second;
t.second = 0;
}

void destroy_map()
{
for_each( table_.begin(), table_.end(),
&delete_second<Table::value_type> );
table_.clear();
}

 

[Zeppe]

ah! more poking around on the net. erase() does invalidate the
iterator. That's why the net code does a post increment in the erase
call.
So preumably I want:-

void destroy_map ()
{
for (Table::iterator i = table_.begin(); i != table_.end()
{
delete (*i).second;
table_.erase (i++);
}
}

since this code is actually in a DTOR and table_ is member variable
would I be better leaving the destruction of the map to the DTOR?

It definitely would. And I'll tell you more, that if you use a smart
pointer you can also forget about the deallocation. The bad thing is
that you need to use additional libraries, such as boost.

Then you can have something as:

#include <map>
#include <boost/shared_ptr.h>

typedef boost::shared_ptr<int> ElementPtr;
typedef std::map<int, ElementPtr> Table;

int main(){
Table t;
t[1] = ElementPtr(new int(1));
t[2] = ElementPtr(new int(2));
}

this will be correctly deleted by the map destructor.

Regards,

Giuseppe

 

[Daniel T.]

ah! more poking around on the net. erase() does invalidate the
iterator. That's why the net code does a post increment in the erase
call.
So preumably I want:-

void destroy_map ()
{
for (Table::iterator i = table_.begin(); i != table_.end()
{
delete (*i).second;
table_.erase (i++);
}
}

since this code is actually in a DTOR and table_ is member variable
would I be better leaving the destruction of the map to the DTOR?

class Symbol_table
{
public:
Table table_;
~Symbol_table();
};

Symbol_table::~Symbol_table()
{
for (Table::iterator i = table_.begin(); i != table_.end(); ++i)
delete (*i).second;
}

should the for-loop be changed into an algorithm? for_each()?

Let the destructor take care of the map, unless you find yourself
putting this kind of loop in all over the place.

I showed in another post how to switch it to using for_each, but I'm not
sure of the utility. I can't think off-hand of any other uses for the
functor, so the only gain would be the removal of the loop.

If, however, you find you have to go through maps like this more than
once in your program, then you should probably write a separate function
for it.

template < typename Map >
void delete_map_ptrs( Map& m ) {
for ( Map::iterator it = m.begin(); it != m.end(); ++it )
{
delete it->second;
it->second = 0;
}
}

 

[red floyd]

No, the standard way is: i = table_.erase(i);

Besides, there's no need to individually erase the map elements. Just
free the memory pointed by the elements and then just clear() the map,
given that you are cleaning it completely.

Sorry, Juha, but map<>::erase returns void.

 

[Victor Bazarov]

Sorry, Juha, but map<>::erase returns void.

In C++0x it will return an iterator. Many library implementations
already have that. While in the currect Standard it's 'void', check
your implementation for it as a possible extension.

V

 

[James Kanze]

No, the standard way is: i = table_.erase(i);

Sorry, Juha, but for some silly reason, map<>::erase() doesn't
return an iterator. (This will be corrected in the next version
of the standard, and I think some implementations already
support it, but if you want to be portable and/or standards
conformant, you can't do it.)

Besides, there's no need to individually erase the map elements. Just
free the memory pointed by the elements and then just clear() the map,
given that you are cleaning it completely.

Formally, having a pointer to a deleted object in the map is
undefined behavior. So you really have to either erase or null
the pointer in the map before deleting, something like:
T* tmp = *i ;
table.erase( i ++ ) ;
delete tmp ;
or
T* tmp = NULL ;
std::swap( tmp, *i ) ;
delete tmp ;
(And that's really in code---using swap is definitly stylish.)

Practically, of course, I wouldn't worry about it, and would do
it as you suggest. Or use smart pointers: the case where a
container is the actual owner of an object is one of the cases
where their use is justified. (I'll admit that in my own code,
in almost 20 years of C++, I've only found one case where a
container actually owned something it pointed to. But that's a
different issue.)

 

[Nick Keighley]

Formally, having a pointer to a deleted object in the map is
undefined behavior. So you really have to either erase or null
the pointer in the map before deleting

Practically, of course, I wouldn't worry about it, and would do
it as you suggest. Or use smart pointers: the case where a
container is the actual owner of an object is one of the cases
where their use is justified. (I'll admit that in my own code,
in almost 20 years of C++, I've only found one case where a
container actually owned something it pointed to. But that's a
different issue.)

well obviously I can't disagree with your experience. But it seemed
not unusual for a container to own an object it pointed to. If you're
newing a lot of similar objects then you need to keep them somewhere.
Why not a container?

The code that prompted my original query was a symbol table.
A definition file is parsed to build the symbol table

typedef std::map<std::string,const Type*> Table;

This symbol table is then used to decode a stream of data.
The first octet read is looked up to yield the message name,
which is then looked up to find the Type. Type knows how
to parse the rest of the stream.

Other cases might be Calls in a telecommunication system.
Drawable items in a drawing program etc.

I'd have thought a container that owned things it pointed to was
very common!

 

[Daniel T.]

it seemed not unusual for a container to own an object it pointed
to. If you're newing a lot of similar objects then you need to keep
them somewhere. Why not a container?

There is some confusion here I think. When you say "you're newing" you
don't actually mean the programmer, rather some object is instantiating
some other object. Generally, the instantiating object is the owner.

 

[nmi]

Hi,

I have a map containing pointers. When I destroy the map I want to
delete
all the pointers.

typedef std::map<std::string, const T*> Table;

void destroy_map ()
{
for (Table::iterator i = table_.begin(); i != table_.end(); ++i)
{
delete (*i).second;
table_.erase (i);
}
}


this crashes.

--
Nick Keighley

This will do:

for (Table::iterator i = table_.begin(); i != table_.end(); ++i)
delete (*i).second;

table_.erase (i) is completely unnecessary.

If you want to use the map later, just put

table.clear(); after the for loop.

 

[Nick Keighley]

There is some confusion here I think. When you say "you're newing" you
don't actually mean the programmer, rather some object is instantiating
some other object. Generally, the instantiating object is the owner.

yes I meant an instantiating object was newing the Type objects.
Type is actually an abstract base class. The instantiator generates
many objects of various classes derived from Type. I can't see how
the parser *can* hold many Type objects without using a container of
some sort.

Simplifying outrageously:-

void parse_file (Token_stream& toks)
{
while (toks.more)
{
Type* type;
string name = toks.current_token;

toks.next();

// this is hidden in a factory
if (toks.current_token == "type_a")
type = new Type_a(toks);
else
if (toks.current_token == "type_b")
type = new Type_b(toks);
else
...

symbol_table.inert(name, type);
}
}

In this case the parser which built the symbol table
ceases to exist once the table is built. So it can't
own the Type objects!


this seems such a natural idiom to me and falls naturally out
of the requirement. So I'm either abusing OOP/C++ or I don't
understand
what "ownership" means.

help!

 

[Daniel T.]

yes I meant an instantiating object was newing the Type objects.
Type is actually an abstract base class. The instantiator generates
many objects of various classes derived from Type. I can't see how
the parser *can* hold many Type objects without using a container
of some sort.

In this case the parser which built the symbol table ceases to
exist once the table is built. So it can't own the Type objects!

So the object that instantiates the parser takes ownership of the Type
objects. The point is though that the container didn't create the
objects, so it doesn't own them. The object that created the parser and
used it as a surrogate, indirectly created the Type objects and therefor
owns them.

 

[James Kanze]

On 9 Nov, 09:38, James Kanze <[email protected]> wrote:

[...]

well obviously I can't disagree with your experience. But it seemed
not unusual for a container to own an object it pointed to. If you're
newing a lot of similar objects then you need to keep them somewhere.
Why not a container?

Perhaps it depends on the application, but most of the time, the
only objects I'm new'ing are entity objects, whose lifetime
depends on external phenomena. Typically, they will be in a map
(or two, or more), in the form of pointers in the map, but the
map doesn't "own" them; the map has a lifetime the same as that
of the entire program, and they remove themselves from the map
when they die.

The code that prompted my original query was a symbol table.
A definition file is parsed to build the symbol table

typedef std::map<std::string,const Type*> Table;

This symbol table is then used to decode a stream of data.

That sounds like it might be a reasonable case for the map to
own the data, yes, although it depends. I guess it's been too
long since I've worked on compilers. I did do a parser
recently, but it was for an interpreter---the data had to hang
around long after I'd finished parsing. But I can imagine
something like this when parsing XML, or something similar.

The first octet read is looked up to yield the message name,
which is then looked up to find the Type. Type knows how
to parse the rest of the stream.

Other cases might be Calls in a telecommunication system.

Calls tend to manage themselves, or be managed by one of the
termination points. One of the parties hangs up, which
generates an event, and processing this event terminates the
lifetime of the call. I can't see anyway that that would be
handled by a container.

Drawable items in a drawing program etc.

Same thing here, I think, although I'm much less familiar with
the domain. The drawable item is deleted by an erase event.

I'd have thought a container that owned things it pointed to
was very common!

I don't think so. Parsing seems to be an exception, and it
doesn't apply all of the time there.

 

[James Kanze]

There is some confusion here I think. When you say "you're
newing" you don't actually mean the programmer, rather some
object is instantiating some other object. Generally, the
instantiating object is the owner.

Generally, in an OO design (which works well in many fields of
endevor), once created, an object is on its own. The object
itself decides when it's no longer needed, and deletes itself.

 

[James Kanze]

On Nov 9, 1:34 pm, Nick Keighley <[email protected]>
wrote:

[...]

this seems such a natural idiom to me and falls naturally out
of the requirement. So I'm either abusing OOP/C++ or I don't
understand what "ownership" means.

It seems like such a natural idiom here because you have a large
group of objects, all having identity (mainly because you need
to navigate between them, so one object may have pointers to
other objects), all working together as a single entity.
Conceptually, you have a single englobing entity which owns
them---and the map. (They aren't really owned by the map
itself, only by the object which manages and owns the map.)
That makes sense.

My experience has been that such conditions just do occur that
frequently. At least in the domains I've worked in. Compilers
are probably an exception, and I did do one application where
the largest class of entity objects had a common
lifetime (infinite, but if you wanted to do a clean
shutdown...) and a single primary key. In that application, the
container mapping the primary key to the objects also managed
the larger classes of objects, and took care of the deletions.
But such cases haven't been the rule.

 

[Roland Pibinger]

I have a map containing pointers. When I destroy the map I want to
delete all the pointers.

typedef std::map<std::string, const T*> Table;

Std containers were designed only for values. They don't work with
pointers (to objects), at least not without clumsy and prohibitive
workarounds. This is one of the major reasons for the low acceptance
of STL in the real world (in contrast to the ongoing STL hype among a
small group of C++ gurus and "gurus").
So, better look for a container that works with pointers. You can even
built your own on top of an STL container.
BTW, std::string as key can introduce problems, too. Depending on your
basic_string implementation it may dynamically allocate an internal
buffer for each copy. This may be unacceptable for a real parser.

 

[Roland Pibinger]

Generally, in an OO design (which works well in many fields of
endevor), once created, an object is on its own. The object
itself decides when it's no longer needed, and deletes itself.

But not in C++. Actually, a dynamically created object cannot decide
on its own when it's no longer needed.
The classic C++ idiom is to let an 'owner object' manage dynamically
created objects, preferably by deleting them in its destructor, a.k.a.
RAII. The best working idiom in this context is 'Creator As Sole
Owner' http://www.ddj.com/184409895 .

 

[James Kanze]

But not in C++.

Very definitely in C++. It's the programmer who writes the
code, regardless of the language.

Actually, a dynamically created object cannot decide on its
own when it's no longer needed.

Why not? It registers for the relevant events, it is notifies
them, and it acts on them. Just like in any OO language.

The classic C++ idiom is to let an 'owner object' manage dynamically
created objects,

Which classic C++ idiom. When the object is conceptually
"owned" by another object, that object deletes it. When the
object doesn't have an owner, it deletes itself.

preferably by deleting them in its destructor, a.k.a.
RAII.

That works in a few limited cases, but most entity objects have
lifetimes which are independant of scope or of any other object.