27

Possible Duplicate:
STL containers element destruction order

Is there a guarantee the the elements of an std::vector would be destroyed from last to first?

Community
  • 1
  • 1
shoosh
  • 76,898
  • 55
  • 205
  • 325
  • I guess that depends on if the guarantee applies to raw arrays too, as std::vector does mimic arrays. But I don't know what the standard says about that. – Klaim May 29 '11 at 17:13
  • @Klaim: `std::vector` mimics arrays only with `op[]` syntax; that says nothing about any element lifetime guarantee. – Lightness Races in Orbit May 29 '11 at 17:15

3 Answers3

18

2003:5.3.5/6 says about delete[]:

The delete-expression will invoke the destructor (if any) for the object or the elements of the array being deleted. In the case of an array, the elements will be destroyed in order of decreasing address (that is, in reverse order of the completion of their constructor; see 12.6.2).

So if your std::vector object's allocator uses delete[] then, yes, it is bound to destroy elements in reverse order.

However, there is no guarantee that your std::vector will work this way (and, in fact, it most likely does not), and I can't find any citations specific to the container.

Really, I think it's all down to your allocator and 2003:20.1.5 (which lists the requirements placed upon allocators) doesn't appear to say anything about it.

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
  • any thoughts on if it just goes out of scope and vector::~vector() is called? – Jordan May 29 '11 at 17:16
  • @Yoel: Huh? What does it matter how the `std::vector`'s destruction is invoked? We're talking about the destruction of its elements. – Lightness Races in Orbit May 29 '11 at 17:18
  • 7
    It's almost certain that `std::vector` WON'T use `delete[]`, since a reasonable implementation wants extra allocated but uninitialized space, for which the constructors have not run (and thus the destructors should not run). – Ben Voigt May 29 '11 at 17:19
  • @Tomalak Geret'kal, I mean to say if the vector goes out of scope and its destructor is called what happens to the elements the vector contains. – Jordan May 29 '11 at 17:20
  • 2
    @BenVoigt: I suppose it uses placement new quite a lot? – Lightness Races in Orbit May 29 '11 at 17:21
  • @Yoel: They are destroyed, in the manner which we are debating. I think you might be misinterpreting the question. – Lightness Races in Orbit May 29 '11 at 17:21
  • @Tomalak Geret'kal, ah I think I understand, thanks for the clarification! – Jordan May 29 '11 at 17:23
  • It would be _technically_ possible to use `new` to allocate a large buffer of `char`s, and then use placement `new`s and `reinterpret_cast`s on that buffer. – Etienne de Martel May 29 '11 at 17:24
  • 3
    @Tomalek: It uses `allocator_traits::construct` and `allocator_traits::destroy`, which by default are wrappers for placement new and explicit destructor call, respectively. – Ben Voigt May 29 '11 at 17:24
  • @Etienne: But then `delete[]` wouldn't be destroying objects, only `char`... and so you can't infer anything about how the objects are destroyed. – Ben Voigt May 29 '11 at 17:26
  • @BenVoigt: I believe that's what my answer says? That it's up to the allocator and we can make no guarantees. – Lightness Races in Orbit May 29 '11 at 17:27
  • 2
    @Tomalak: it isn't merely not guaranteed that vector will call `delete[]` on an array of T containing its elements, in fact it's guaranteed that it *won't* (in effect) do so. There's no way you can implement an allocator class that `delete[]`s the whole lot in one go, since the vector is required to `destroy` them one at a time. The get-out clause is the "as-if" rule - if the vector is using the default allocator then it *could* `delete[]` I suppose, but it would have to be as a special case depending on that instance's history, since `vector::resize()` still has to be implemented somehow. – Steve Jessop May 29 '11 at 17:28
  • @Tomalak: I was in the process of writing it when your answer got posted; I hadn't seen yours. And, like you, I thought it would be good to quote the language about raw arrays by way of contrast, instead of starting my answer with an unsupported claim.... There, clarified. – Ben Voigt May 29 '11 at 17:35
7

No, there are guarantees for arrays, where all elements are constructed is order and destroyed in the reverse order. This is somewhat consistent with how global objects are handled.

Container members, on the other hand, can be constructed and destroyed in any order using for example insert and erase member functions. To be somewhat consistent and destroy the elements in the reverse order of construction, this would require the containers to keep some kind of log over these changes. Obviously this would be expensive!

The best bet is that the container destructor calls clear(), which is defined as erase(begin(), end()), but I cannot find any requirements for that either. The standard only says "linear complexity" in table 65.

Bo Persson
  • 90,663
  • 31
  • 146
  • 203
5

They standard guarantees this for a raw array, but I can't find anything that would guarantee it for containers.

From [expr.delete] (new wording for C++0x):

If the value of the operand of the delete-expression is not a null pointer value, the delete-expression will invoke the destructor (if any) for the object or the elements of the array being deleted. In the case of an array, the elements will be destroyed in order of decreasing address (that is, in reverse order of the completion of their constructor; see 12.6.2).

std::vector (and in fact, all containers in the standard library, possibly excluding std::array) do not use delete[] to destroy the elements (they use allocator_traits<allocator_type>::destroy on each element individually), so the above guarantee doesn't apply. And I can find no restrictions on std::vector in particular or containers in general, about the order of deletion. For some containers, such a guarantee would be very expensive (e.g. std::forward_list can't iterate the elements in reverse to delete them, and std::map doesn't remember the order in which pairs were added).

From [container.requirements.general] (C++0x wording):

For the components affected by this subclause that declare an allocator_type, objects stored in these components shall be constructed using the allocator_traits::construct function and destroyed using the allocator_traits::destroy function (20.6.8.2).

Ben Voigt
  • 277,958
  • 43
  • 419
  • 720