Questions about destructors on std library containers

[Ross Boylan]

I am trying to understand under what circumstances destructors get called
with std::vector. I have an application in which I will put real objects,
not just pointers, in the vector.

1. The standard says that empty() has constant complexity. If it actually
called the destructor for each object, it seems to me it would have
linear complexity. Does empty() call the destructor for each object in the
container? If yes, why is it described as having constant commplexity?
If no, that seems like a problem too.

2. The standard describes clear by saying that it behaves like
erase(begin, end). That seems as if it would erase the first element, copying
all succedding elements over it, and so on, which is obviously very
inefficient. Is it safe to assume something more reasonable is happening
under the covers?

3. Does erase call the destructor for the elements erased?
More properly, I guess I should ask if the elements freed at the end after
being moved over erased items are cleared. I'd probably only be erasing
the whole vector or its last element.

As I'm writing this I realize I may have a basic confusion, and that
constructors and destructors are only called at the beginning and end
of the vector's life (and when its capacity expands). The rest of the
time elements are either in use or not, with the behavior of the assignment
operator being key. Is that what's really going on?
I'm interested both in what can and can't be inferred from the standard, and
in what current compiler practice on different platforms is--in other words,
what's safe to assume in portable code.

[John Harrison]

> >

But since you brought up the topic I think that the standard requires
size() to be O(1) and allows splice on different lists to be O(n).

In a note (bottom of 23.1 Table 65) it says size() "should have
constant complexity", it requires that splice has complexity
"Contant Time" 23.2.2.4/6

So I was wrong splice() is required to be O(1), I was under the
impression that this was upto the implementor, but this is the first
time I've checked the standard.

Rob.
--
http://www.victim-prime.dsl.pipex.com/

23.2.2.4/14 is the exception that allows linear time for splice in certain
circumstances.

john

[Rob Williscroft]

John Harrison wrote in
news:c0******** *****@ID-196037.news.uni-berlin.de:

>
> But since you brought up the topic I think that the standard
> requires size() to be O(1) and allows splice on different lists to
> be O(n).
>
In a note (bottom of 23.1 Table 65) it says size() "should have
constant complexity", it requires that splice has complexity
"Contant Time" 23.2.2.4/6

So I was wrong splice() is required to be O(1), I was under the
impression that this was upto the implementor, but this is the first
time I've checked the standard.

23.2.2.4/14 is the exception that allows linear time for splice in
certain circumstances.

Thanks, I should have read further ;)

Rob.
--
http://www.victim-prime.dsl.pipex.com/

[Ross Boylan]

Thanks to everyone for their replies.

On Thu, 12 Feb 2004 04:55:14 +0000, Victor Bazarov wrote:

"Ross Boylan" <Ro********@sta nfordalumni.org > wrote...

I am trying to understand under what circumstances destructors get called
with std::vector. I have an application in which I will put real objects,
not just pointers, in the vector.

1. The standard says that empty() has constant complexity. If it actually
called the destructor for each object, it seems to me it would have
linear complexity. Does empty() call the destructor for each object in the

container? If yes, why is it described as having constant commplexity?
If no, that seems like a problem too.

'empty' is not the same as 'clear'. Do not confuse the two. For C++
library containers, 'empty' is an adjective, not a verb.

Oops. I didn't read closely enough, and am used to smalltalk where it
would be isEmpty.

....

3. Does erase call the destructor for the elements erased?

Yes.

More properly, I guess I should ask if the elements freed at the end after
being moved over erased items are cleared.

I am not sure I completely understand the sentence, but elements can
be freed even in the middle of erasing, during the move. std::vector
is a tricky container, it has to reallocate and move things all the
time, so the old elements will get destroyed right after new copies of
them are made.

Minor explanation: Suppose you have a 5 element vector and erase the
3rd element. My first wording implied the destructor would be called
on the 3rd element; my refinement acknowledged that 3rd and 4th get
assigned to while the 5th is the one that would be destroyed.

.....
Why not trace all the constructor and destructor calls? It's
fun and it's educational. It's educational fun.
But it won't tell me what's in the standard or what the range of
actual implementations are.

I'm interested both in what can and can't be inferred from the standard,

and

in what current compiler practice on different platforms is--in other

words,

what's safe to assume in portable code.

Nothing is safe to assume except what's said in the Standard.

In my experience, not even that, since there are many non-conforming
implementations .

I missed the section 23.2.4.3 about destructors being called that Ivan
so helpfully cited. Unfortunately, that is in a discussion of
complexity; read narrowly, it is thus no guarantee of sematics. I
wish there were an explicit statement about the semantics of erase and
similar operations that shrink the collection size calling
destructors.