Questions about destructors on std library containers

Discussion in 'C++' started by Ross Boylan, Feb 12, 2004.

  1. Ross Boylan

    Ross Boylan Guest

    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.
     
    Ross Boylan, Feb 12, 2004
    #1
    1. Advertising

  2. "Ross Boylan" <> 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.

    > 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?


    Absolutely. When semantics are explained, it doesn't mean that the
    implementation is precisely the same. Do not confuse semantics and
    implementation.

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

    > I'd probably only be erasing
    > the whole vector or its last element.


    Don' make no difference, they are still gonna get destroyed. Hafta.

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


    ....and when you insert or remove an element in the middle. IOW, every
    time elements get moved around.

    > 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?


    Plenty. Why not trace all the constructor and destructor calls? It's
    fun and it's educational. It's educational fun.

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

    V
     
    Victor Bazarov, Feb 12, 2004
    #2
    1. Advertising

  3. "Ross Boylan" <> wrote in message
    news:p...
    > 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.


    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.

    > 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

    > 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'd probably only be erasing
    > the whole vector or its last element.

    Which means you can call clear() and pop_back(), respectively,
    instead of erase().

    > 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?


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

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

    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
     
    Ivan Vecerina, Feb 12, 2004
    #3
  4. Ross Boylan

    Sharad Kala Guest

    "Ivan Vecerina" <> wrote in message
    news:c0f308$2ok$...
    > "Ross Boylan" <> wrote in message
    > news:p...
    > > 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.

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


    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.

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

    Best wishes,
    Sharad
     
    Sharad Kala, Feb 12, 2004
    #4
  5. "Sharad Kala" <> wrote in message
    news:c0f4jh$16a5ii$-berlin.de...
    >
    > "Ivan Vecerina" <> wrote in message
    > news:c0f308$2ok$...
    > > "Ross Boylan" <> wrote in message
    > > news:p...
    > > > 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.

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

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


    nitpick

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

    surely.

    john
     
    John Harrison, Feb 12, 2004
    #5
  6. "Sharad Kala" <> wrote in message
    news:c0f4jh$16a5ii$-berlin.de...
    |
    | "Ivan Vecerina" <> wrote in message
    | news:c0f308$2ok$...
    ....
    | > 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
     
    Ivan Vecerina, Feb 12, 2004
    #6
  7. John Harrison wrote in news:c0f8hr$16ssf0$-berlin.de:

    > nitpick
    >
    > empty() is the same as size() == 0
    >
    > surely.
    >


    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/
     
    Rob Williscroft, Feb 12, 2004
    #7
  8. "Rob Williscroft" <> wrote in message
    news:Xns948DA283E8214ukcoREMOVEfreenetrtw@195.129.110.204...
    > John Harrison wrote in news:c0f8hr$16ssf0$-berlin.de:
    >
    > > nitpick
    > >
    > > empty() is the same as size() == 0
    > >
    > > surely.
    > >

    >
    > 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/


    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
     
    John Harrison, Feb 12, 2004
    #8
  9. Ross Boylan

    Ron Natalie Guest

    "Ivan Vecerina" <> wrote in message news:c0f308$2ok$...

    > A conforming implementation of empty() is: return this->size() > 0;
    >


    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.
     
    Ron Natalie, Feb 12, 2004
    #9
  10. John Harrison wrote in
    news:c0gabm$16edm1$-berlin.de:

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


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


    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/
     
    Rob Williscroft, Feb 12, 2004
    #10
  11. > >
    > > 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
     
    John Harrison, Feb 12, 2004
    #11
  12. John Harrison wrote in
    news:c0gl26$11gmoc$-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/
     
    Rob Williscroft, Feb 12, 2004
    #12
  13. Ross Boylan

    Ross Boylan Guest

    Thanks to everyone for their replies.

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

    > "Ross Boylan" <> 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.
     
    Ross Boylan, Feb 13, 2004
    #13
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Anton
    Replies:
    1
    Views:
    369
    Peter van Merkerk
    Aug 6, 2003
  2. velthuijsen
    Replies:
    3
    Views:
    5,316
    velthuijsen
    Feb 13, 2004
  3. Replies:
    7
    Views:
    555
    Pete Becker
    Jan 25, 2008
  4. Jayden Shui
    Replies:
    5
    Views:
    209
    Jorgen Grahn
    Dec 20, 2011
  5. Sebastian Mach
    Replies:
    5
    Views:
    315
Loading...

Share This Page