best way to "delete" all objects in a std::vector.

[Daniel Pitts]

I have std::vector<Base *> bases;

I'd like to do something like:
std::for_each(bases.begin(), bases.end(), operator delete);

Is it possible without writing an adapter? Is there a better way? Is
there an existing adapter?

Thanks,
Daniel.

 

[acehreli]

I have std::vector<Base *> bases;

I'd like to do something like:
std::for_each(bases.begin(), bases.end(), operator delete);

Is it possible without writing an adapter? Is there a better way? Is
there an existing adapter?

Keeping plain pointers to dynamic objects is way too much trouble.
Smart pointers is the best way. boost::shared_ptr is suitable:

#include <boost/shared_prt.hpp>
/* ... */
typedef boost::shared_ptr<Base> BasePtr;
std::vector<BasePtr> bases;

This and other problems magically vanish...

Ali

 

[jason.cipriani]

I have std::vector<Base *> bases;

I'd like to do something like:
std::for_each(bases.begin(), bases.end(), operator delete);

Is it possible without writing an adapter? Is there a better way? Is
there an existing adapter?

What's wrong with:

for (std::vector<Base *>::iterator i = bases.begin(); i !=
bases.end(); ++ i)
delete *i;

It's only two lines; and it's clear what is happening. I don't think
you'll be able to beat that. If it's something you do frequently you
could write a utility function like:

template <class T> void delete_all (T &cont) {
typedef typename T::iterator iter_t;
for (iter_t i(cont.begin()); i != cont.end(); ++ i)
delete *i;
cont.clear();
}


Example:

struct A { ... };

void f () {

vector<A *> x;
list<A *> y;
set<A *> z;

x.push_back(new A);
x.push_back(new A);
y.push_back(new A);
y.push_back(new A);
z.insert(new A);
z.insert(new A);

delete_all(x);
delete_all(y);
delete_all(z);

}


Jason

 

[William Xu]

I'd like to do something like:
std::for_each(bases.begin(), bases.end(), operator delete);

Is it possible without writing an adapter? Is there a better way? Is
there an existing adapter?

Doesn't seem so... You'd better write your own my_delete:

template <class T>
struct my_delete : std::unary_function<T, void>
{
void operator()(T* t)
{
delete t;
}
};

This one:

std::for_each(bases.begin(), bases.end(), std:tr_fun(operator delete));

compiles, but doesn't work(dtor is not called)...

--
William

http://williamxu.net9.org

Underdogging:
The tendency to almost invariably side with the underdog in a
given situation. The consumer expression of this trait is the
purchasing of less successful, "sad," or failing products: "I know
these Vienna franks are heart failure on a stick, but they were so sad
looking up against all the other yuppie food items that I just had to
buy them."
-- Douglas Coupland, "Generation X: Tales for an Accelerated
Culture"

 

[Jerry Coffin]

I have std::vector<Base *> bases;

I'd like to do something like:
std::for_each(bases.begin(), bases.end(), operator delete);

Is it possible without writing an adapter? Is there a better way? Is
there an existing adapter?

Boost Pointer Container Library.

 

[James Kanze]

From Stroustrup's book.

struct Delete_ptr {
template<class T> T* operator()(T* p) const { delete p; return 0; }
};

transform(s.begin(),s.end(),s.begin(),Delete_ptr());

[To the original poster: ignore this: it is from an
obsessional nitpicker, only for expert nitpickers.]

Note that formally, the above still has undefined behavior,
since it leaves a deleted pointer in the container for a (very)
short time. The correct way of doing this would be:

struct Deleter
{
template< typename T >
void operator()( T*& p ) const
{
T* tmp = NULL ;
std::swap( p, tmp ) ;
delete tmp ;
}
} ;

...

std::for_each( s.begin(), s.end(), Deleter() ) ;

(Note that it even uses swap. Can't get much more in than
that.)

 

[jason.cipriani]

From Stroustrup's book.
struct Delete_ptr {
template<class T> T* operator()(T* p) const { delete p; return 0; }
};
...
transform(s.begin(),s.end(),s.begin(),Delete_ptr());

[To the original poster: ignore this: it is from an
obsessional nitpicker, only for expert nitpickers.]

Note that formally, the above still has undefined behavior,
since it leaves a deleted pointer in the container for a (very)
short time. The correct way of doing this would be:

What has undefined behavior? If you are talking about the transform
over all, or the () operator, neither are undefined. It is well-
defined that it leaves an invalid pointer in the container for a very
short time. What's undefined is if something attempts to dereference
that pointer during that time.

 

[James Kanze]

I have std::vector<Base *> bases;
I'd like to do something like:
std::for_each(bases.begin(), bases.end(), operator delete);
Is it possible without writing an adapter? Is there a better
way? Is there an existing adapter?
From Stroustrup's book.
struct Delete_ptr {
template<class T> T* operator()(T* p) const { delete p; return 0; }
};
...
transform(s.begin(),s.end(),s.begin(),Delete_ptr());

[To the original poster: ignore this: it is from an
obsessional nitpicker, only for expert nitpickers.]
Note that formally, the above still has undefined behavior,
since it leaves a deleted pointer in the container for a (very)
short time. The correct way of doing this would be:

What has undefined behavior? If you are talking about the
transform over all, or the () operator, neither are undefined.
It is well- defined that it leaves an invalid pointer in the
container for a very short time. What's undefined is if
something attempts to dereference that pointer during that
time.

A pointer, after delete, may not even be read or copied (since
one of the effects of delete could be to render its value
"trapping"). Which means that it is not Copiable, and thus,
you've violated the requirements of the standard containers.

In practice, of course, there are very, very few implementations
where it might actually trap: to do so means 1) that the
hardware can trap on such pointers (Intels IA-32 is the only one
I know of where this might currently be a problem), 2) that the
library actually does free the memory in a way that unmaps it
(none that I know of do---they all keep the memory mapped to the
process for potential future use), 3) that the compiler actually
does the copy in such a way that might trap (I think some Intel
compilers do), and 4) that std::vector actually does try to copy
it. That last point is, of course, the ultimate guarantee;
std::vector will normally only copy anything if you try to
increase the size of the vector.

But the standard still says that all of the elements must be
copiable, even if there's no earthly reason for the vector to
copy.

 

[Jerry Coffin]

[ ... ]

The implementation I presented doesn't read or copy any pointers after
the delete. The object is deleted, then the pointer is assigned NULL. If
the code I presented is "technically undefined" then so is:

delete p;
p = NULL;

Not so. An item in a container is required to be copyable. _We_ all know
that in a vector, for example, the contents are only ever copied in
reaction to things YOU do, such as a push_back when it's used up all the
memory already reserved. Nonetheless, the standard requires that all
items in a collection _always_ be copyable and assignable, even if you
_don't_ do anything that would force copying of the contents while it's
not copyable. Of course, the same goes for assignment.

In your snippet above, p is (apparently) not in a container, so the
container requirements don't apply.

 

[Jerry Coffin]

[ ... ]

AFAIK, the implementation I presented is guaranteed by the standard not
to read or copy any pointers after the delete.

I don't see any such guarantee, though I'll admit I might have missed
it.

In any case, pointers are
defined as copyable by the standard. I don't see the problem.

They're not copyable (or assignable) after you've deleted what the point
at -- at that point the _only_ thing you can safely do with a pointer is
assign a new value to it.

 

[Kai-Uwe Bux]

[ ... ]

AFAIK, the implementation I presented is guaranteed by the standard not
to read or copy any pointers after the delete.

I don't see any such guarantee, though I'll admit I might have missed
it.

Maybe you missed it because you snipped it. So, let's look at it:


struct Delete_ptr {
template<class T> T* operator()(T* p) const { delete p; return 0; }
};

...

transform(s.begin(),s.end(),s.begin(),Delete_ptr());


Note:

a) Delete_ptr:perator() returns 0.
b) The proposed solution uses transform and not foreach.


Best

Kai-Uwe

 

[James Kanze]

[ ... ]

AFAIK, the implementation I presented is guaranteed by the
standard not to read or copy any pointers after the delete.

I don't see any such guarantee, though I'll admit I might
have missed it.

Maybe you missed it because you snipped it. So, let's look at it:

struct Delete_ptr {
template<class T> T* operator()(T* p) const { delete p; return 0; }
};



a) Delete_ptr:perator() returns 0.
b) The proposed solution uses transform and not foreach.

And... Where do you have a guarantee that std::transform
doesn't read through the pointer a second time, after having
called the fucntional object? Or that
std::vector::iterator:perator*() doesn't read the object
before returning an lvalue to it.

I very heavily stressed in my original posting that this was for
nitpickers, because, of course, no implementation will do such
things, and we all know it. But the fact remains that the
standard requires that all objects in a container be copyiable,
at all times (even if no member function is called). And
between the delete in the operator(), above, and the moment
transform assigns the result of the operator to its target,
there is a deleted pointer in the container, which is undefined
behavior.

 

[Kai-Uwe Bux]

[ ... ]
AFAIK, the implementation I presented is guaranteed by the
standard not to read or copy any pointers after the delete.
I don't see any such guarantee, though I'll admit I might
have missed it.

Maybe you missed it because you snipped it. So, let's look at it:

struct Delete_ptr {
template<class T> T* operator()(T* p) const { delete p; return 0; }
};



a) Delete_ptr:perator() returns 0.
b) The proposed solution uses transform and not foreach.

And... Where do you have a guarantee that std::transform
doesn't read through the pointer a second time, after having
called the fucntional object? Or that
std::vector::iterator:perator*() doesn't read the object
before returning an lvalue to it.

Those are valid points.

I very heavily stressed in my original posting that this was for
nitpickers, because, of course, no implementation will do such
things, and we all know it. But the fact remains that the
standard requires that all objects in a container be copyiable,
at all times (even if no member function is called). And
between the delete in the operator(), above, and the moment
transform assigns the result of the operator to its target,
there is a deleted pointer in the container, which is undefined
behavior.

If that was true in this generality, I would consider it a defect in the
standard because it decidedly interferes with generic programming. E.g.,

delete_and_set_null ( T* & p_ref ) {
delete p_ref;
p_ref = 0;
}

would be undefined when v[0] is passed into it because between the two
statements, although no member function of the container can be called,
there is a non-copiable object in the container. Instead one would have to
use your swap proposal to implement a safe delete_and_set_null (at the
point the reference is passed, no template magic will be able to detect
that is comes from a container). Clearly, that makes you pay for stuff you
don't use.

BTW, with regard to the "at all times (even if no member function is
called)", the standard is not at all clear. [23.1/3] requires the "type of
objects stored in these components" to satisfy the CopyConstructible and
Assignable requirements, which in turn are only defined for types and not
for objects. This is also emphasized in [20.1/1] which implies that
CopyConstructible is a requirement for types used to instantiate template
arguments not a requirement for objects. The type "T*" clearly satisfies
those requirements. That individual objects of type T* may at times have
invalid values does not change that. However, other rules kick in and say
that reading such values is undefined. In that regard, your objections from
the first paragraph are valid. However, that can only happen when member
functions of the container are called triggering the read. Mere existence
of an object with invalid value within a container might not necessarily
entail undefined behavior (at least of the top of my head, I don't see the
provisions that would imply that).


Best

Kai-Uwe Bux

 

[Daniel T.]

(e-mail address removed) says...

They're not copyable (or assignable) after you've deleted what the point
at -- at that point the _only_ thing you can safely do with a pointer is
assign a new value to it.

Either pointers are copyable, or they are not. What you are saying is
that the standard doesn't allow for pointers to be in containers at
all.

 

[James Kanze]

Jerry Coffin wrote:

[ ... ]
AFAIK, the implementation I presented is guaranteed by the
standard not to read or copy any pointers after the delete.
I don't see any such guarantee, though I'll admit I might
have missed it.
Maybe you missed it because you snipped it. So, let's look at it:
struct Delete_ptr {
template<class T> T* operator()(T* p) const { delete p; return 0; }
};
...
transform(s.begin(),s.end(),s.begin(),Delete_ptr());
Note:
a) Delete_ptr:perator() returns 0.
b) The proposed solution uses transform and not foreach.

And... Where do you have a guarantee that std::transform
doesn't read through the pointer a second time, after having
called the fucntional object? Or that
std::vector::iterator:perator*() doesn't read the object
before returning an lvalue to it.

Those are valid points.

If that was true in this generality, I would consider it a
defect in the standard because it decidedly interferes with
generic programming. E.g.,

delete_and_set_null ( T* & p_ref ) {
delete p_ref;
p_ref = 0;
}

would be undefined when v[0] is passed into it because between
the two statements, although no member function of the
container can be called, there is a non-copiable object in the
container.

Instead one would have to use your swap proposal to implement
a safe delete_and_set_null (at the point the reference is
passed, no template magic will be able to detect that is comes
from a container). Clearly, that makes you pay for stuff you
don't use.

Yep. Formally, I think that's actually the situation.
Practically, for starters, we can be 100% sure that none of the
standard containers do anything with any of the elements they
contain when none of their functions are being called. I don't
think the wording of the standard gives enough leeway to
guarantee this, but I do think that one could argue that it was
the intent; that if the standard doesn't give this guarantee,
it's because it never occured to anyone that the opposite could
be true. Beyond that, I think it reasonable to suppose that a
container doesn't copy or assign except in cases where it is
required to, and that you can leave uncopiable values in a
container for short instances, as long as you do nothing which
might "perturb" the container (although I'll admit that that is
very, very vague).

With regards to your "pay for stuff you don't use", of course,
it would be a pretty poor optimizer which didn't detect that the
tmp in my code using swap didn't cease to be live immediately,
and generate pretty much the same code as it does for what
you've written, above (supposing std::swap inline, of course).

BTW, with regard to the "at all times (even if no member
function is called)", the standard is not at all clear.
[23.1/3] requires the "type of objects stored in these
components" to satisfy the CopyConstructible and Assignable
requirements, which in turn are only defined for types and not
for objects.

This is a more general problem; the standard really doesn't
define very well what it means by "CopyConstructible". But for
a type to be CopyConstructible, it seems clear that the ability
to copy must not depend on the value of objects of the type.

This is also emphasized in [20.1/1] which implies that
CopyConstructible is a requirement for types used to
instantiate template arguments not a requirement for objects.

You're raising a very interesting point. Formally, for a type T
to be CopyConstructible, the expression T(u) must be valid.
Where u is a const value of type T. Not a particular const
value, but any const value.

The type "T*" clearly satisfies those requirements. That
individual objects of type T* may at times have invalid values
does not change that.

There are two different issues concerned here (and I don't think
that the standard makes this very clear). The first is that
every value of the type T must be copiable, otherwise the type
is not CopyConstructible, and you cannot have a collection which
contains it. I find that rather clear, but maybe I'm reading
more into things than I should. The second is that space
declared as a T may still not contain a value of type T; if you
delete a pointer, or call the destructor on an object, then you
no longer have a value of that object type. In this regard,
using the Delete_ptr above falls into the same category as
using a functional object something like:

struct MessThingsUp
{
template< typename T >
void operator()( T& obj )
{
obj.~T() ;
}
} ;

The result in both cases is that you've left something in the
container which is no longer a valid object of type T. (Note
that in the case of Delete_ptr, of course, the type T in
question is in fact a pointer type.) You can get away with it
in the case of pointers only because the standard allows using
the raw memory of a POD object as a POD, as long as there is no
lvalue to rvalue conversion.

However, other rules kick in and say that reading such values
is undefined. In that regard, your objections from the first
paragraph are valid. However, that can only happen when member
functions of the container are called triggering the read.
Mere existence of an object with invalid value within a
container might not necessarily entail undefined behavior (at
least of the top of my head, I don't see the provisions that
would imply that).

You're arguing from a common sense point of view, and not from
the standard.

I think it's a somewhat awkward question, since I think that the
entire specification of the standard library "assumes" that all
objects in a container are valid. There are no special rules
for cases where an "object" is temporarily invalid, or
temporarily "uncopiable". So we really don't know. When all is
said and done, however, the standard clearly doesn't make any
distinction on the requirements depending on what you do with
the container. If you can legally leave an invalid pointer in a
container for the shortest instance, you can legally do anything
which the container supports even if it contains an invalid
pointer.

FWIW: the discussion is largely accademic with regards to
pointers, since architectures on which reading an invalid
pointer doesn't work are really rare. I've actually had
problems along these lines with iterators, however; an iterator
constructed with the default constructor, or one which has been
invalidated by some operation on the container, is not copiable,
g++ complains if you try to copy it, and I've had it complain
because I've left such iterators in a container.

Anyway, I wouldn't mind it if the standard did clarify this, but
I don't consider it a serious issue, because the only time it
really seems to occur is this particular case, we all know that
in practice, it will work, and there is a simple work-around.
And I don't see any easy wording which would make legal what we
all know will work, but still make illegal all of the more
dubious cases.

(If comp.std.c++ were active, I'd raise the issue there, but I'm
a bit hesitant about raising it on the committee mailing lists;
I don't think it's a concrete problem in practice, and the
committee has more than enough to keep it busy without such hair
splitting.)

 

[James Kanze]

Either pointers are copyable, or they are not. What you are
saying is that the standard doesn't allow for pointers to be
in containers at all.

Pointer values are copyable. After the delete, however, you no
longer have a pointer value; just raw memory which is declared
as a pointer.

Although not an exact equivalent, deleting a pointer is in some
ways the same as calling the destructor on an object, except
that it affects all pointers with the same value (and not just
the pointer in the delete expression), and that because pointers
are POD's, you can assign to an invalid (uninitialized) pointer.

A more interesting case is that of iterators. You can't copy an
iterator if it was constructed using the default constructor,
nor an invalid iterator, so I believe that, strictly
interpreted, you cannot have a container of iterators. (The
difference, of course, is that the "invalid iterator" is still
an object of type iterator if the iterator has class type, since
the destructor hasn't been called.)

 

[Kai-Uwe Bux]

Jerry Coffin wrote:

[ ... ]
AFAIK, the implementation I presented is guaranteed by the
standard not to read or copy any pointers after the delete.
I don't see any such guarantee, though I'll admit I might
have missed it.
Maybe you missed it because you snipped it. So, let's look at it:
struct Delete_ptr {
template<class T> T* operator()(T* p) const { delete p; return 0;
}
};
...
transform(s.begin(),s.end(),s.begin(),Delete_ptr());
Note:
a) Delete_ptr:perator() returns 0.
b) The proposed solution uses transform and not foreach.
And... Where do you have a guarantee that std::transform
doesn't read through the pointer a second time, after having
called the fucntional object? Or that
std::vector::iterator:perator*() doesn't read the object
before returning an lvalue to it.

Those are valid points.

If that was true in this generality, I would consider it a
defect in the standard because it decidedly interferes with
generic programming. E.g.,

delete_and_set_null ( T* & p_ref ) {
delete p_ref;
p_ref = 0;
}

would be undefined when v[0] is passed into it because between
the two statements, although no member function of the
container can be called, there is a non-copiable object in the
container.

Instead one would have to use your swap proposal to implement
a safe delete_and_set_null (at the point the reference is
passed, no template magic will be able to detect that is comes
from a container). Clearly, that makes you pay for stuff you
don't use.

Yep. Formally, I think that's actually the situation.
Practically, for starters, we can be 100% sure that none of the
standard containers do anything with any of the elements they
contain when none of their functions are being called. I don't
think the wording of the standard gives enough leeway to
guarantee this, but I do think that one could argue that it was
the intent; that if the standard doesn't give this guarantee,
it's because it never occured to anyone that the opposite could
be true.

True, and maybe that should be codified.

Beyond that, I think it reasonable to suppose that a
container doesn't copy or assign except in cases where it is
required to, and that you can leave uncopiable values in a
container for short instances, as long as you do nothing which
might "perturb" the container (although I'll admit that that is
very, very vague).

Common sense. But I agree that there is no language in the standard that
would make it clear.

With regards to your "pay for stuff you don't use", of course,
it would be a pretty poor optimizer which didn't detect that the
tmp in my code using swap didn't cease to be live immediately,
and generate pretty much the same code as it does for what
you've written, above (supposing std::swap inline, of course).

BTW, with regard to the "at all times (even if no member
function is called)", the standard is not at all clear.
[23.1/3] requires the "type of objects stored in these
components" to satisfy the CopyConstructible and Assignable
requirements, which in turn are only defined for types and not
for objects.

This is a more general problem; the standard really doesn't
define very well what it means by "CopyConstructible". But for
a type to be CopyConstructible, it seems clear that the ability
to copy must not depend on the value of objects of the type.

This is also emphasized in [20.1/1] which implies that
CopyConstructible is a requirement for types used to
instantiate template arguments not a requirement for objects.

You're raising a very interesting point. Formally, for a type T
to be CopyConstructible, the expression T(u) must be valid.
Where u is a const value of type T. Not a particular const
value, but any const value.

That interpretations has very interesting and unfortunate consequences.
Consider:

std::vector< T* > t_vector;
t_vector.push_back( new T );
T* dummy = new T;
delete dummy;

at this point, there exists an invalid value of type T* outside the
container and the type T*, according to your reading of the standard is no
longer CopyConstructible. Since there is a vector<T*> object violating its
conceptual requirements, the program has undefined behavior. Ouch.

There are two different issues concerned here (and I don't think
that the standard makes this very clear). The first is that
every value of the type T must be copiable, otherwise the type
is not CopyConstructible, and you cannot have a collection which
contains it. I find that rather clear, but maybe I'm reading
more into things than I should.

See above for the dire consequences of your interpretation.

The second is that space
declared as a T may still not contain a value of type T; if you
delete a pointer, or call the destructor on an object, then you
no longer have a value of that object type. In this regard,
using the Delete_ptr above falls into the same category as
using a functional object something like:

struct MessThingsUp
{
template< typename T >
void operator()( T& obj )
{
obj.~T() ;
}
} ;

The result in both cases is that you've left something in the
container which is no longer a valid object of type T. (Note
that in the case of Delete_ptr, of course, the type T in
question is in fact a pointer type.) You can get away with it
in the case of pointers only because the standard allows using
the raw memory of a POD object as a POD, as long as there is no
lvalue to rvalue conversion.

Hm. Objects of type T* are regions of memory and are to be distinguised from
their values. I am not so sure that the standard defines "invalid object".
It defines lifetimes, values, and types; and it is not very clear about
whether a container can contain objects beyond their lifetime. Now, of
course, there is no way to use such a container afterwards, and one cannot
even destruct it, but whether the mere existence of something like that
entails UB is far from clear.

You're arguing from a common sense point of view, and not from
the standard.

I think it's a somewhat awkward question, since I think that the
entire specification of the standard library "assumes" that all
objects in a container are valid.

Without any clear statement of that assumption in the standard, I think it
is _you_ who argues from common sense and not from the standard.

There are no special rules
for cases where an "object" is temporarily invalid, or
temporarily "uncopiable". So we really don't know. When all is
said and done, however, the standard clearly doesn't make any
distinction on the requirements depending on what you do with
the container. If you can legally leave an invalid pointer in a
container for the shortest instance, you can legally do anything
which the container supports even if it contains an invalid
pointer.

I am not so sure about that. If the effects clause tells you that a certain
member function will entail a read, then other provisions of the standard
will tell you that this is UB. Whether operations that do not have such
statements in their effects clause entail UB because of the conceptual
requirements, I don't know. Whether not doing anything with the container
entails UB is again a different matter. Why the answer to all of them
should be assumed to be the same is beyond me.

FWIW: the discussion is largely accademic with regards to
pointers, since architectures on which reading an invalid
pointer doesn't work are really rare. I've actually had
problems along these lines with iterators, however; an iterator
constructed with the default constructor, or one which has been
invalidated by some operation on the container, is not copiable,
g++ complains if you try to copy it, and I've had it complain
because I've left such iterators in a container.

Anyway, I wouldn't mind it if the standard did clarify this, but
I don't consider it a serious issue, because the only time it
really seems to occur is this particular case, we all know that
in practice, it will work, and there is a simple work-around.
And I don't see any easy wording which would make legal what we
all know will work, but still make illegal all of the more
dubious cases.

One could specify in the effects clauses, which operations on objects of
type T can be triggered by a particular member function and guarantee that
no other operations will happen.

(If comp.std.c++ were active, I'd raise the issue there, but I'm
a bit hesitant about raising it on the committee mailing lists;
I don't think it's a concrete problem in practice, and the
committee has more than enough to keep it busy without such hair
splitting.)

But isn't it fun?




Best

Kai-Uwe Bux