Questions about destructors on std library containers

**Victor Bazarov** · Jul 22 '05, 06:31 AM

Re: Questions about destructors on std library containers

"Ross Boylan" <RossBoylan@sta nfordalumni.org > wrote...[color=blue]
> 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[/color]
the[color=blue]
> container? If yes, why is it described as having constant commplexity?
> If no, that seems like a problem too.[/color]

'empty' is not the same as 'clear'. Do not confuse the two. For C++
library containers, 'empty' is an adjective, not a verb.
[color=blue]
> 2. The standard describes clear by saying that it behaves like
> erase(begin, end). That seems as if it would erase the first element,[/color]
copying[color=blue]
> 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?[/color]

Absolutely. When semantics are explained, it doesn't mean that the
implementation is precisely the same. Do not confuse semantics and
implementation.
[color=blue]
>
> 3. Does erase call the destructor for the elements erased?[/color]

Yes.
[color=blue]
> More properly, I guess I should ask if the elements freed at the end after
> being moved over erased items are cleared.[/color]

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.
[color=blue]
> I'd probably only be erasing
> the whole vector or its last element.[/color]

Don' make no difference, they are still gonna get destroyed. Hafta.
[color=blue]
>
> 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).[/color]

....and when you insert or remove an element in the middle. IOW, every
time elements get moved around.
[color=blue]
> The rest of the
> time elements are either in use or not, with the behavior of the[/color]
assignment[color=blue]
> operator being key. Is that what's really going on?[/color]

Plenty. Why not trace all the constructor and destructor calls? It's
fun and it's educational. It's educational fun.
[color=blue]
> I'm interested both in what can and can't be inferred from the standard,[/color]
and[color=blue]
> in what current compiler practice on different platforms is--in other[/color]
words,[color=blue]
> what's safe to assume in portable code.[/color]

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

V

**Ivan Vecerina** · Jul 22 '05, 06:31 AM

Re: Questions about destructors on std library containers

"Ross Boylan" <RossBoylan@sta nfordalumni.org > wrote in message
news:pan.2004.0 2.12.00.13.04.6 15017@stanforda lumni.org...[color=blue]
> 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[/color]
the[color=blue]
> container? If yes, why is it described as having constant commplexity?
> If no, that seems like a problem too.[/color]

A conforming implementation of empty() is: return this->size() > 0;
This function does not empty the vector ( unlike clear() ): it only
returns a boolean that indicates whether the container is empty or not.
[color=blue]
> 2. The standard describes clear by saying that it behaves like
> erase(begin, end). That seems as if it would erase the first element,[/color]
copying[color=blue]
> 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?[/color]
erase() does not remove elements one by one: the whole range is "removed"
by copying/moving the following elements over it. Then the unused trailing
elements are removed.
Say if the first three elements of ABCDEFGH are erased, steps that will
typically happen are:
DEFGH are copied down using the assignment operator --> DEFGHFGH
The trailing elements are destroyed --> DEFGH
[color=blue]
> 3. Does erase call the destructor for the elements erased?[/color]
Yes.[color=blue]
> 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.[/color]
Which means you can call clear() and pop_back(), respectively,
instead of erase().
[color=blue]
> 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[/color]
assignment[color=blue]
> operator being key. Is that what's really going on?[/color]

The capacity of a vector is only allocated as raw memory.
The number of constructed objects within the vector is always equal to
the value returned by vector::size().
[color=blue]
> I'm interested both in what can and can't be inferred from the standard,[/color]
and[color=blue]
> in what current compiler practice on different platforms is--in other[/color]
words,[color=blue]
> what's safe to assume in portable code.[/color]
No 'ghost' objects can be constructed by std::vector, given than:
- the element contained in an std::vector may not have a default
constructor
- keeping hidden copies of elements that have been erased would have
unexpected effects -- and is not allowed.

hth, Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- e-mail contact form

**Sharad Kala** · Jul 22 '05, 06:31 AM

Re: Questions about destructors on std library containers

"Ivan Vecerina" <please_use_web _form@ivan.vece rina.com> wrote in message
news:c0f308$2ok $1@newshispeed. ch...[color=blue]
> "Ross Boylan" <RossBoylan@sta nfordalumni.org > wrote in message
> news:pan.2004.0 2.12.00.13.04.6 15017@stanforda lumni.org...[color=green]
> > 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[/color]
> the[color=green]
> > container? If yes, why is it described as having constant commplexity?
> > If no, that seems like a problem too.[/color]
>
> A conforming implementation of empty() is: return this->size() > 0;
> This function does not empty the vector ( unlike clear() ): it only
> returns a boolean that indicates whether the container is empty or not.[/color]

Josuttis in his book "The C++ standard library" recommends empty() over
container.size( ) > 0. He says it is _usually_ more efficient.
Given this implementation this might not be true.
[color=blue][color=green]
> > 2. The standard describes clear by saying that it behaves like
> > erase(begin, end). That seems as if it would erase the first element,[/color]
> copying[color=green]
> > 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?[/color]
> erase() does not remove elements one by one: the whole range is "removed"
> by copying/moving the following elements over it. Then the unused trailing
> elements are removed.
> Say if the first three elements of ABCDEFGH are erased, steps that will
> typically happen are:
> DEFGH are copied down using the assignment operator --> DEFGHFGH
> The trailing elements are destroyed --> DEFGH[/color]
hmm..IIRC, they are not.
One must take care to erase the trailing elements (i.e FGH).

Best wishes,
Sharad

**John Harrison** · Jul 22 '05, 06:31 AM

Re: Questions about destructors on std library containers

"Sharad Kala" <no.spam_sharad k_ind@yahoo.com > wrote in message
news:c0f4jh$16a 5ii$1@ID-221354.news.uni-berlin.de...[color=blue]
>
> "Ivan Vecerina" <please_use_web _form@ivan.vece rina.com> wrote in message
> news:c0f308$2ok $1@newshispeed. ch...[color=green]
> > "Ross Boylan" <RossBoylan@sta nfordalumni.org > wrote in message
> > news:pan.2004.0 2.12.00.13.04.6 15017@stanforda lumni.org...[color=darkred]
> > > I am trying to understand under what circumstances destructors get[/color][/color][/color]
called[color=blue][color=green][color=darkred]
> > > with std::vector. I have an application in which I will put real[/color][/color][/color]
objects,[color=blue][color=green][color=darkred]
> > > not just pointers, in the vector.
> > >
> > > 1. The standard says that empty() has constant complexity. If it[/color][/color][/color]
actually[color=blue][color=green][color=darkred]
> > > called the destructor for each object, it seems to me it would have
> > > linear complexity. Does empty() call the destructor for each object[/color][/color][/color]
in[color=blue][color=green]
> > the[color=darkred]
> > > container? If yes, why is it described as having constant[/color][/color][/color]
commplexity?[color=blue][color=green][color=darkred]
> > > If no, that seems like a problem too.[/color]
> >
> > A conforming implementation of empty() is: return this->size() > 0;
> > This function does not empty the vector ( unlike clear() ): it only
> > returns a boolean that indicates whether the container is empty or not.[/color]
>
> Josuttis in his book "The C++ standard library" recommends empty() over
> container.size( ) > 0. He says it is _usually_ more efficient.
> Given this implementation this might not be true.
>[/color]

nitpick

empty() is the same as size() == 0

surely.

john

**Ivan Vecerina** · Jul 22 '05, 06:31 AM

Re: Questions about destructors on std library containers

"Sharad Kala" <no.spam_sharad k_ind@yahoo.com > wrote in message
news:c0f4jh$16a 5ii$1@ID-221354.news.uni-berlin.de...
|
| "Ivan Vecerina" <please_use_web _form@ivan.vece rina.com> wrote in message
| news:c0f308$2ok $1@newshispeed. ch...
....
| > A conforming implementation of empty() is: return this->size() > 0;
^^^^^^^^^^
Note that my comment was about behavior, not performance or style.

| Josuttis in his book "The C++ standard library" recommends empty() over
| container.size( ) > 0. He says it is _usually_ more efficient.
| Given this implementation this might not be true.
Indeed, his advice is not universally true. Some implementations of
vector::empty() are definitely implemented by calling vector::size().

However, style-wise, I would concur that calling empty() is better
than comparing size() to zero. ( just as I recommended calling
clear() and pop_back() instead of erase(), when applicable )

| > > 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?
| > erase() does not remove elements one by one: the whole range is
"removed"
| > by copying/moving the following elements over it. Then the unused
trailing
| > elements are removed.
| > Say if the first three elements of ABCDEFGH are erased, steps that will
| > typically happen are:
| > DEFGH are copied down using the assignment operator --> DEFGHFGH
| > The trailing elements are destroyed --> DEFGH
| hmm..IIRC, they are not.
| One must take care to erase the trailing elements (i.e FGH).
Not correct.

In the context of the OP, it seemed clear that this discussion was about
the vector::erase member function. This member function is not to be
confused with the non-member std::erase algorithm (to which your
comment would applly).

C++ standard 23.2.4.3/4 (about vector::erase):
Complexity: The destructor of T is called the number of times equal to the
number of the elements erased, but the assignment operator of T is called
the number of times equal to the number of elements in the vector after the
erased elements.

Regards,
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- e-mail contact form

**Rob Williscroft** · Jul 22 '05, 06:32 AM

Re: Questions about destructors on std library containers

John Harrison wrote in news:c0f8hr$16s sf0$1@ID-196037.news.uni-berlin.de:
[color=blue]
> nitpick
>
> empty() is the same as size() == 0
>
> surely.
>[/color]

With some implementations of std::list<> this is not the case.

In these implementations size() is calculated (std::distance( ... ))
every time it is called, empty() just needs to check wether the list
is empty or not. So its constant-time vs. O(n).

With these implementations splice() is faster because they don't
maintain a seperate size member.

Rob.
--

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

**John Harrison** · Jul 22 '05, 06:32 AM

Re: Questions about destructors on std library containers

"Rob Williscroft" <rtw@freenet.RE MOVE.co.uk> wrote in message
news:Xns948DA28 3E8214ukcoREMOV Efreenetrtw@195 .129.110.204...[color=blue]
> John Harrison wrote in news:c0f8hr$16s sf0$1@ID-196037.news.uni-berlin.de:
>[color=green]
> > nitpick
> >
> > empty() is the same as size() == 0
> >
> > surely.
> >[/color]
>
> With some implementations of std::list<> this is not the case.
>
> In these implementations size() is calculated (std::distance( ... ))
> every time it is called, empty() just needs to check wether the list
> is empty or not. So its constant-time vs. O(n).
>
> With these implementations splice() is faster because they don't
> maintain a seperate size member.
>
> Rob.
> --
> http://www.victim-prime.dsl.pipex.com/[/color]

Well I wasn't talking about efficiency I was just correcting the obvious
mistake that 'empty() is that same as size() > 0' which two posters had
made.

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).

john

**Ron Natalie** · Jul 22 '05, 06:32 AM

Re: Questions about destructors on std library containers

"Ivan Vecerina" <please_use_web _form@ivan.vece rina.com> wrote in message news:c0f308$2ok $1@newshispeed. ch...
[color=blue]
> A conforming implementation of empty() is: return this->size() > 0;
>[/color]

Actually, that is specific NOT conforming for containers in general.
As alluded to in the original post, empty has constant complexity.
size() may take longer.

**Rob Williscroft** · Jul 22 '05, 06:32 AM

Re: Questions about destructors on std library containers

John Harrison wrote in
news:c0gabm$16e dm1$1@ID-196037.news.uni-berlin.de:
[color=blue][color=green]
>> With some implementations of std::list<> this is not the case.
>>
>> In these implementations size() is calculated (std::distance( ... ))
>> every time it is called, empty() just needs to check wether the list
>> is empty or not. So its constant-time vs. O(n).
>>
>> With these implementations splice() is faster because they don't
>> maintain a seperate size member.
>>[/color][/color]
[color=blue]
>
> Well I wasn't talking about efficiency I was just correcting the
> obvious mistake that 'empty() is that same as size() > 0' which two
> posters had made.
>
> 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).
>[/color]

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/

**John Harrison** · Jul 22 '05, 06:32 AM

Re: Questions about destructors on std library containers

> >[color=blue][color=green]
> > 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).
> >[/color]
>
> 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/[/color]

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

john

**Rob Williscroft** · Jul 22 '05, 06:32 AM

Re: Questions about destructors on std library containers

John Harrison wrote in
news:c0gl26$11g moc$1@ID-196037.news.uni-berlin.de:
[color=blue][color=green][color=darkred]
>> >
>> > 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).
>> >[/color]
>>
>> 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.
>>[/color][/color]
[color=blue]
> 23.2.2.4/14 is the exception that allows linear time for splice in
> certain circumstances.
>[/color]

Thanks, I should have read further ;)

Rob.
--

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

**Ross Boylan** · Jul 22 '05, 06:33 AM

Re: Questions about destructors on std library containers

Thanks to everyone for their replies.

On Thu, 12 Feb 2004 04:55:14 +0000, Victor Bazarov wrote:
[color=blue]
> "Ross Boylan" <RossBoylan@sta nfordalumni.org > wrote...[color=green]
>> 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[/color]
> the[color=green]
>> container? If yes, why is it described as having constant commplexity?
>> If no, that seems like a problem too.[/color]
>
> 'empty' is not the same as 'clear'. Do not confuse the two. For C++
> library containers, 'empty' is an adjective, not a verb.[/color]

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

....
[color=blue][color=green]
>> 3. Does erase call the destructor for the elements erased?[/color]
>
> Yes.
>[color=green]
>> More properly, I guess I should ask if the elements freed at the end after
>> being moved over erased items are cleared.[/color]
>
> 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.[/color]

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.

.....[color=blue]
>
> Why not trace all the constructor and destructor calls? It's
> fun and it's educational. It's educational fun.[/color]

But it won't tell me what's in the standard or what the range of
actual implementations are.
[color=blue]
>[color=green]
>> I'm interested both in what can and can't be inferred from the standard,[/color]
> and[color=green]
>> in what current compiler practice on different platforms is--in other[/color]
> words,[color=green]
>> what's safe to assume in portable code.[/color]
>
> Nothing is safe to assume except what's said in the Standard.[/color]

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.

Questions about destructors on std library containers

Questions about destructors on std library containers

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment